अंतरिक्ष जटिलता पिछले

Question

कई प्रणालियों में, head.reverse अंतरिक्ष सूची के आकार के अनुपात में होती है, जबकि last निरंतर स्थान की आवश्यकता होती आवश्यकता है।

वहाँ प्रणाली इस तरह के एक परिवर्तन प्रदर्शन करने के लिए कर रहे हैं? इसी प्रकार reverse.take n.reverse के लिए?

संपादित करें: मैं अपना प्रश्न विस्तारित करना चाहता हूं: मैं एक ठोस परिवर्तन के बाद नहीं हूं — मैं इस अंत तक अनुकूलन के बाद हूं।

Answer 1

आप इस के लिए एक सरल पुनर्लेखन नियम लिख सकते हैं।

http://www.haskell.org/haskellwiki/Playing_by_the_rules

फ्यूजन नियम यह भी पकड़ सकता है, निर्भर करता है कि रिवर्स एन्कोड किया गया है।

Answer 2

हम ड्रॉप और पिछले

>>> last [1..10^5] 
100000 
(0.01 secs, 10496736 bytes) 
>>> last [1..10^6] 
1000000 
(0.05 secs, 81968856 bytes) 
>>> last [1..10^7] 
10000000 
(0.32 secs, 802137928 bytes) 


>>> drop (10^5-1) [1..10^5] 
[100000] 
(0.01 secs, 10483312 bytes) 
>>> drop (10^6-1) [1..10^6] 
[1000000] 
(0.05 secs, 82525384 bytes) 
>>> drop (10^7-1) [1..10^7] 
[10000000] 
(0.32 secs, 802142096 bytes) 

हम अंतरिक्ष और समय में इसी तरह के प्रदर्शन को प्राप्त करने की तुलना करें, मैं मानता चाहिए कि मैं क्योंकि यहाँ हम सूची की अवधि की गणना करने की जरूरत नहीं है एक छोटा सा धोखा दिया। वैसे भी मुझे विश्वास है कि यह अंतरिक्ष में कोई मुद्दा नहीं होना चाहिए। फिर आपके रिवर्स। लिया । रिवर्स ड्रॉप और लंबाई का उपयोग करके व्यक्त किया जा सकता है।

---

साइड नोट के रूप में मैंने अन्य कामकाज का परीक्षण किया है और नतीजा खराब है। खाली सूचियों शून्य हैं, और conses succ हैं:

takeLastN = foldl' (.) id . flip replicate tail 

lastN = foldl' (.) last . flip replicate init 

Answer 3

आप एक विशेष रूप से कुंठित आलसी प्राकृतिक संख्या के रूप में अपनी सूची का इलाज द्वारा reverse . take n . reverse बदल सकता है। सूचियों के रूप में एन्कोड आलसी प्राकृतिक की तुलना के लिए, घटाव drop है:

type LazyNat a = [a] 

lengthLazy :: [a] -> LazyNat a 
lengthLazy = id 

dropLazy :: LazyNat a -> [b] -> [b] 
dropLazy [] xs = xs 
dropLazy (_:n) (_:xs) = dropLazy n xs 
dropLazy _ _ = [] 

-- like Prelude.subtract, this is flip (-) 
subtractLazy :: Int -> LazyNat a -> LazyNat a 
subtractLazy = drop 

अब हम आसानी से "ले पिछले n" समारोह को लागू कर सकते हैं:

takeLast n xs = dropLazy (subtractLazy n (lengthLazy xs)) xs 

... और आप को पता है कि खुश हो जाएगा केवल n किसी भी समय पर विपक्ष को स्मृति में होना आवश्यक है। विशेष रूप से, takeLast 1 (या वास्तव में किसी भी takeLast N शाब्दिक N के लिए) लगातार स्मृति में चला सकते हैं। आप की तुलना क्या होता है जब आप क्या होता है जब आप GHCi में (reverse . take 5 . reverse) [1..] चलाने के साथ takeLast 5 [1..] चलाने कर इसकी पुष्टि कर सकते हैं।

बेशक

, मैं ऊपर बहुत विचारोत्तेजक नाम का उपयोग करने की कोशिश की है, लेकिन कोई वास्तविक कार्यान्वयन में आप सब बकवास ऊपर इनलाइन सकता है:

takeLast n xs = go xs (drop n xs) where 
    go lastn [] = lastn 
    go (_:xs) (_:n) = go xs n 
    go _  _  = []