تسلسلات كسول Clojure التي هي متجهات

Question

لقد لاحظت أن التسلسلات البطيئة في clojure يبدو أنها ممثلة داخليًا كقوائم مرتبطة (أو على الأقل يتم التعامل معها كتسلسل مع وصول متسلسل فقط إلى العناصر). حتى بعد أن تم تخزينه مؤقتًا في الذاكرة ، يمكنك الوصول إلى وقت عبر الكسول مع nth هو o (ن) ، وليس الوقت المستمر كما هو الحال مع المتجهات.

;; ...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"

كيف يمكنني الحصول على بحث مستمر في الوقت أو إنشاء متجه كسول بشكل تدريجي في Clojure؟

تخيل أنه أثناء توليد المتجه الكسول ، يكون كل عنصر وظيفة لجميع العناصر السابقة لها ، وبالتالي يصبح الوقت الذي يقضيه عبور القائمة عاملاً مهمًا.

أسئلة ذات صلة فقط أظهرت مقتطف Java غير المكتمل:تصميم ناقل كسول: مشكلة مع كونست

Answer 1

نعم ، يتم وصف تسلسلات في clojure على أنها "قوائم منطقية" مع ثلاث عمليات (أولاً ، التالي وسلبيات).

التسلسل هو في الأساس إصدار clojure من ايتراتور (على الرغم من أن clojure.org يصر على أن التسلسلات ليست متكررين ، لأنها لا تحتفظ بحالة إيتينال) ، ولا يمكنها التحرك إلا من خلال مجموعة الدعم بطريقة خطية من الأمام إلى النهاية.

ناقلات كسول غير موجودة ، على الأقل ليس في clojure.

إذا كنت ترغب في البحث عن الوقت المستمر على مجموعة من الفهارس ، دون حساب العناصر الوسيطة التي لا تحتاجها ، يمكنك استخدام وظيفة تحسب النتيجة أثناء الطيران. بالاقتران مع المذكرات (أو تخزين النتائج في تجزئة ARG-to-Result بنفسك) ، ستحصل على نفس التأثير إلى حد كبير كما أفترض أنك تريد من المتجه الكسول.

من الواضح أن هذا يعمل فقط عندما تكون هناك خوارزميات يمكنها حساب F (n) بشكل مباشر أكثر من المرور عبر جميع F (0) ... F (N-1). إذا لم يكن هناك مثل هذه الخوارزمية ، عندما تعتمد نتيجة كل عنصر على النتيجة لكل عنصر سابق ، لا يمكنك أن تفعل أفضل من التسلسل المتسلسل في أي حال.

يحرر

راجع للشغل ، إذا كان كل ما تريده هو أن تكون النتيجة متجهًا ، لذا يمكنك الحصول على بحث سريع بعد ذلك ، ولا تمانع في إنشاء العناصر بالتتابع في المرة الأولى ، وهذا بسيط بما فيه الكفاية.

فيما يلي تطبيق Fibonacci باستخدام ناقل:

(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 إرجاع تسلسل كسول) ، ولكن يتم جمع النتائج وإعادتها في ناقل.

ينمو المتجه حسب الحاجة ، نضيف فقط العناصر حتى آخر واحد طلب ، وبمجرد حسابها ، يكون البحث المستمر وقتًا.

هل كان الأمر كهذا كان يدور في ذهنك؟