تسلسلات كسول "تتطلع إلى الأمام" لمشكلة مشروع أولر 14

Question

أحاول الحل مشكلة مشروع أولر 14 بطريقة كسول. لسوء الحظ ، قد أحاول القيام بالمستحيل: إنشاء تسلسل كسول كسول ، ولكن أيضًا "يبحث إلى الأمام" للقيم التي لم يتم حسابها بعد.

كانت النسخة غير الباردة التي كتبتها لاختبار الصواب:

(defn chain-length [num]
  (loop [len 1
         n  num]
(cond
  (= n 1) len 
  (odd? n) (recur (inc len) (+ 1 (* 3 n)))
  true     (recur (inc len) (/ n 2)))))

الذي يعمل ، لكنه بطيء حقًا. بالطبع يمكنني أن أذكر ذلك:

(def memoized-chain
   (memoize
     (fn [n]
       (cond
        (= n 1) 1 
         (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
         true     (+ 1 (memoized-chain (/ n 2)))))))

ومع ذلك ، فإن ما أردت فعله حقًا هو خدش حكة لي لفهم حدود التسلسلات البطيئة ، وكتابة وظيفة مثل هذه:

(def lazy-chain
     (letfn [(chain [n] (lazy-seq
                         (cons (if (odd? n)
                                 (+ 1 (nth lazy-chain (dec (+ 1 (* 3 n)))))
                                 (+ 1 (nth lazy-chain (dec (/ n 2)))))
                               (chain (+ n 1)))))]
       (chain 1)))

سيؤدي سحب العناصر من هذا إلى حدوث تدفق مكدس لـ N> 2 ، وهو أمر مفهوم إذا كنت تفكر في سبب حاجة إلى البحث "في المستقبل" في n = 3 لمعرفة قيمة العنصر العاشر في القائمة البطيئة لأن (+ 1 (* 3 N)) = 10.

نظرًا لأن القوائم الكسول لديها أقل بكثير من المذكرات ، أود أن أعرف ما إذا كان هذا النوع من الأشياء ممكنًا بطريقة أو بأخرى من خلال التقييم أو التصوير المتأخر؟

Answer 1

فيما يلي تعطيني تسلسل كسول من قيم collatz. على Microbenchmarks على الجهاز الخاص بي ، فإنه يتفوق بشكل معتدل على محلول المذكرات. على الجانب السلبي ، يتكرر أيضًا بعمق شديد للعثور على مليون أطوال سلسلة كولاتز ، وتفيض المكدس في مكان ما بين العنصر البالغ 100000 و 1،000،000 ، ولكن يمكن حلها بقليل من العمل recur.

 (defn collatz [n cache]
   (if-let [v (cache n)]
     [v cache]
     (let [[p cache] (if (odd? n)
                       (collatz (+ 1 (* 3 n)) cache)
                       (collatz (/ n 2) cache))]
       [(inc p) (assoc cache n (inc p))])))

 (def lazy-collatz
      (map first (iterate (fn [[v cache n]]
                            (concat (collatz n cache) [(inc n)]))
                          [1 {1 1} 2])))

ومع ذلك ، لا يزال ما أردت: هذه الوظيفة نفسها بدون هاشماب. بالتفكير في تعليق ميشال الممتاز ومفهوم بناء شجرة عودية ، أعتقد أن ما أردت هنا ليس أ كسول التسلسل ، ولكن كسول عودية بنية البيانات من نوع ما ، ربما شجرة. هل توجد تقنيات تدفق البيانات هذه؟

كانت فكرتي الأصلية هي بناء سلاسل من "التأخير" من القيمة غير المعروفة (N) التي تستمر في التكرار حتى تصل إلى رقم معروف (مثل 1) ، ثم الاسترخاء ، وتملأ بنية البيانات الكسولة مع القيم الفعلية مع الاسترخاء. إذا فكرنا في تسلسل كسول باعتباره قائمة مرتبطة كسول ، فإن ما أردته هو متجه أو شجرة بطول كسول لا حصر له من شأنه أن يكتشف تبعيات البيانات تلقائيًا باستخدام قاعدة Collatz. كافية لهذه المشكلة ، ولكنها إلى حد ما تقريبا تقريب ما أردت: ناقل البيانات البطيئة مع قاعدة تطبق على كيفية ملء العناصر في المتجه.

تحدي صعب إضافي: هل يمكن لأي شخص أن يفكر في طريقة لتمثيل هذه الشجرة/المتجه كسول بسهولة دون استخدام hashmap؟

Answer 2

Seq "النظر في المستقبل"

مثال على SEQ غير تقليدي الذي يبحث في المستقبل قد يبدو هكذا:

(def funky-seq
     (let [substrate (atom ())]
       (letfn [(funk [n] (delay (if (odd? n) n @(nth @substrate (inc n)))))]
         (reset! substrate (map funk (range))))
       (map deref @substrate)))

user> (take 10 funky-seq)
(1 1 3 3 5 5 7 7 9 9)

(ملف تعريف الارتباط لمن يصنع هذا أبسط دون كسره. :-))

بالطبع إذا كان تحديد قيمة العنصر قد ينطوي على النظر إلى عنصر "مستقبلي" يعتمد على عنصر آخر يدعو إلى حساب عنصر أكثر بعيدة ... لا يمكن مساعدة الكارثة.

أولر 14

المشكلة الأساسية في مخطط "النظر في المستقبل" من السؤال من السؤال الذي يحاول توظيف جانبا ، هذا النهج لا يحل المشكلة حقًا ، لأنه إذا قررت البدء من 1 وارتفع إلى الأعلى, ، تحتاج إلى أخذ المتفرعة في الاعتبار: أ 10 في سلسلة collatz يمكن الوصول إليها من خلال تطبيق أي من القاعدة ( n / 2 القاعدة المطبقة على 20 أو ال 3n + 1 القاعدة تبدأ من 3). أيضًا ، إذا كنت ترغب في بناء سلاسلك لأعلى ، فيجب عليك عكس القواعد وإما أن تتضاعف 2 أو طرح 1 وتقسيم 3 (تطبيق ، في كل خطوة ، تلك القاعدة التي تنتج عددًا صحيحًا - أو ربما كلاهما إذا كان كلاهما).

بالطبع يمكنك بناء أ شجرة, ، بدلاً من قائمة كسول ، لكن ذلك لن يبدو شيئًا مثل رسم الرمز في السؤال وأتوقع منك أن ينتهي بك الأمر في نهاية المطاف بتذكير الشيء.

ما سبق هو أن تكون مؤهلاً مع ملاحظة مفادها أنه قد يكون لديك تخمين حول "قاعدة بناء السلسلة" من المحتمل أن تولد أطول سلسلة تبدأ من 1 أثناء إبقاء الإدخال النهائي أقل من الحد المحدد. إذا كان هذا هو الحال ، فيجب عليك على الأرجح إثبات أنه صحيح ثم تنفيذها مباشرة (من خلال loop / recur يبدأ من 1) ؛ بدون دليل ، لا يمكنك أن تدعي حقًا حل المشكلة.

Answer 3

أظن iterate و take-while يمكن أن يكون بعض المساعدة (على الرغم من أن هذا الرمز لا ينظر إلى المستقبل):

(defn next-collatz [n]
  (cond
    (= n 1) 1
    (odd? n) (+ 1 (* 3 n))
    true (/ n 2)))

(defn collatz-seq [n]
  (iterate next-collatz n))

(defn collatz [n]
    (take-while #(not (= % 1)) (collatz-seq n)))

user> (collatz 100)
=> (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2)