क्लोजर आलसी अनुक्रम जो वेक्टर

Question

मैंने देखा है कि क्लोजर में आलसी अनुक्रम आंतरिक रूप से लिंक्ड सूचियों के रूप में प्रदर्शित किए जाते हैं (या कम से कम उन्हें तत्वों के लिए अनुक्रमिक पहुंच के अनुक्रम के रूप में माना जा रहा है)। स्मृति में कैश होने के बाद भी, nth के साथ आलसी-सीक पर पहुंच का समय ओ (एन) है, वैक्टर के साथ निरंतर समय नहीं है।

;; ...created my-lazy-seq here and used the first 50,000 items 

(time (nth my-lazy-seq 10000)) 
"Elapsed time: 1.081325 msecs" 

(time (nth my-lazy-seq 20000)) 
"Elapsed time: 2.554563 msecs" 

मैं निरंतर समय के लुकअप कैसे प्राप्त करूं या क्लोजर में आलसी रूप से आलसी वेक्टर कैसे बना सकता हूं?

कल्पना कीजिए कि आलसी वेक्टर की पीढ़ी के दौरान, प्रत्येक तत्व इसके पिछले सभी तत्वों का एक कार्य है, इसलिए सूची में घुसने का समय एक महत्वपूर्ण कारक बन जाता है।

संबंधित प्रश्न केवल यह अधूरा जावा कर दिया स्निपेट: Designing a lazy vector: problem with const

Answer 1

हाँ, Clojure में दृश्यों "logical lists" के रूप में तीन आपरेशन (प्रथम, अगले और विपक्ष) के साथ बताया गया है।

एक अनुक्रम अनिवार्य रूप से एक पुनरावर्तक का क्लोजर संस्करण है (हालांकि clojure.org जोर देता है कि अनुक्रम नहीं हैं, क्योंकि वे इटर्नल स्टेटस नहीं रखते हैं), और केवल एक रैखिक फ्रंट-इन में बैकिंग संग्रह को स्थानांतरित कर सकते हैं फैशन प्रदान करें।

आलसी वैक्टर मौजूद नहीं हैं, कम से कम क्लोजर में नहीं।

यदि आप इंडेक्स की एक श्रृंखला पर लगातार समय लुकअप चाहते हैं, तो इंटरमीडिएट तत्वों की गणना किए बिना, आपको फ्लाई पर परिणाम की गणना करने वाले फ़ंक्शन का उपयोग कर सकते हैं। ज्ञापन के साथ संयुक्त (या अपने आप पर एक तर्क-परिणाम-परिणाम हैश में परिणामों को कैश करना) आपको बहुत ही प्रभाव मिलता है जैसा कि मुझे लगता है कि आप आलसी वेक्टर से चाहते हैं।

यह स्पष्ट रूप से ही काम करता है जब वहाँ एल्गोरिदम कि च (एन) की गणना कर सकता सभी पूर्ववर्ती च (0) ... f (n-1) के माध्यम से जा रहे हैं की तुलना में अधिक सीधे। यदि ऐसा कोई एल्गोरिदम नहीं है, तो प्रत्येक तत्व के परिणाम प्रत्येक पिछले तत्व के परिणाम पर निर्भर करते हैं, तो आप किसी भी मामले में अनुक्रम पुनरावर्तक से बेहतर नहीं कर सकते हैं।

संपादित

BTW, अगर सभी आप चाहते है परिणाम एक वेक्टर ताकि आप जल्दी लुकअप बाद में मिलता है, और आप कोई आपत्ति नहीं है कि तत्वों क्रमिक रूप से पहली बार बनाई गई हैं के लिए, कि काफी सरल है ।

यहाँ एक वेक्टर का उपयोग कर एक फाइबोनैचि दिया गया है:

(defn vector-fib [v] 
    (let [a (v (- (count v) 2)) ; next-to-last element 
     b (peek v)] ; last element 
    (conj v (+ a b)))) 

(def fib (iterate vector-fib [1 1])) 

(first (drop 10 fib)) 
    => [1 1 2 3 5 8 13 21 34 55 89 144] 

यहाँ हम एक आलसी अनुक्रम का उपयोग कर रहे समारोह को स्थगित करने के लिए कॉल जब तक के लिए कहा (iterate एक आलसी अनुक्रम रिटर्न), लेकिन परिणाम एकत्र और लौटा दिए जाते हैं एक वेक्टर में।

वेक्टर के रूप में की जरूरत है, हम केवल तत्वों पिछले एक को जोड़ने के लिए कहा, और एक बार गणना की यह एक निरंतर समय देखने है बढ़ता है।

क्या ऐसा कुछ ऐसा था जो आपको दिमाग में था?