كيف أحفظ دالة عودية في Lisp؟

Question

أنا مبتدئ في اللثغة.أحاول حفظ دالة عودية لحساب عدد المصطلحات في ملف تسلسل كولاتز (للمشكلة 14 في مشروع أويلر).الكود الخاص بي حتى الآن هو:

(defun collatz-steps (n)
  (if (= 1 n) 0
       (if (evenp n) 
           (1+ (collatz-steps (/ n 2)))
           (1+ (collatz-steps (1+ (* 3 n)))))))

(defun p14 ()
  (defvar m-collatz-steps (memoize #'collatz-steps))
  (let 
      ((maxsteps (funcall m-collatz-steps 2))
       (n 2)
       (steps))
    (loop for i from 1 to 1000000
          do 
          (setq steps (funcall m-collatz-steps i))
          (cond 
            ((> steps maxsteps) 
             (setq maxsteps steps)
             (setq n i))
            (t ())))
    n))


(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind 
              (result exists)
            (gethash args cache)
          (if exists
              result
              (setf (gethash args cache)
                    (apply fn args)))))))

وظيفة الحفظ هي نفس الوظيفة الواردة في ملف على ليسب كتاب.

لا يعطي هذا الرمز في الواقع أي تسريع مقارنة بالإصدار غير المحفوظ.أعتقد أن ذلك يرجع إلى المكالمات المتكررة التي تستدعي النسخة غير المحفوظة من الوظيفة، وهو ما يتعارض مع الغرض.وفي هذه الحالة ما هي الطريقة الصحيحة للقيام بالحفظ هنا؟هل هناك أي طريقة لجعل كافة الاستدعاءات للوظيفة الأصلية تستدعي النسخة المحفوظة نفسها، مما يزيل الحاجة إلى رمز m-collatz-steps الخاص؟

يحرر:تصحيح الكود لديك

(defvar m-collatz-steps (memoize #'collatz-steps))

وهو ما كان لدي في الكود الخاص بي.قبل التعديل كنت قد وضعت خطأً:

(defvar collatz-steps (memoize #'collatz-steps))

رؤية هذا الخطأ أعطاني فكرة أخرى، وحاولت استخدام أداة defvar الأخيرة نفسها وتغيير الاستدعاءات المتكررة إلى

       (1+ (funcall collatz-steps (/ n 2)))
       (1+ (funcall collatz-steps (1+ (* 3 n))))

يبدو أن هذا يؤدي إلى الحفظ (التسريع من حوالي 60 ثانية إلى 1.5 ثانية)، ولكنه يتطلب تغيير الوظيفة الأصلية.هل هناك حل أنظف لا يتضمن تغيير الوظيفة الأصلية؟

Answer 1

وأفترض أنك تستخدم المشتركة، اللثغة، التي لديها مساحات منفصلة لأسماء متغير وظيفة. من أجل memoize وظيفة يسميه رمزا، كنت بحاجة إلى تغيير وظيفة لها صفة الإلزام، من خلال استرجاع `fdefinition ':

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

(defun p14 ()
  (let ((mx 0) (my 0))
    (loop for x from 1 to 1000000
          for y = (collatz-steps x)
          when (< my y) do (setf my y mx x))
    mx))

Answer 2

وشيء من هذا القبيل:

(setf collatz-steps (memoize lambda (n)
  (if (= 1 n) 0
    (if (evenp n) 
        (1+ (collatz-steps (/ n 2)))
        (1+ (collatz-steps (1+ (* 3 n))))))))

وIOW: (غير memoized) الدالة الأصلية مجهولة، وتعطيها اسما فقط لنتيجة memoizing ذلك

Answer 3

وهنا هي وظيفة memoize أن rebinds وظيفة رمز:

(defun memoize-function (function-name)
  (setf (symbol-function function-name)
    (let ((cache (make-hash-table :test #'equal)))
         #'(lambda (&rest args)
             (multiple-value-bind 
                 (result exists)
                (gethash args cache)
               (if exists
                   result
                   (setf (gethash args cache)
                         (apply fn args)))))))

هل ثم تفعل شيئا مثل هذا:

(defun collatz-steps (n)
  (if (= 1 n) 0
      (if (evenp n) 
          (1+ (collatz-steps (/ n 2)))
          (1+ (collatz-steps (1+ (* 3 n)))))))

(memoize-function 'collatz-steps)

وسأترك الأمر متروك لكم لجعل وظيفة unmemoize.

Answer 4

وتغيير وظيفة "الأصلية" ضرورية، لأنه، كما تقول، وليس هناك طريقة أخرى لدعوة متكررة (ق) إلى تحديث لاستدعاء إصدار memoized.

لحسن الحظ، ويعمل ثغة طريقة للعثور على وظيفة <م> بالاسم كل الوقت الذي تحتاجه ليتم استدعاؤها. وهذا يعني أنه يكفي ليحل محل وظيفة الربط مع الإصدار memoized وظيفة، بحيث دعوات متكررة سوف تبدو تلقائيا وإعادة إدخال من خلال التحفيظ.

وكود هواى يوان ليظهر خطوة رئيسية:

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

وكما تعمل هذه الخدعه في بيرل. بلغة مثل C، ومع ذلك، يجب أن تكون مشفرة نسخة memoized وظيفة على حدة.

وبعض التطبيقات ثغة توفر نظام يسمى "المشورة"، الذي يوفر هيكل موحد لاستبدال وظائف مع إصدارات محسنة من أنفسهم. بالإضافة إلى ترقيات وظيفية مثل التحفيظ، وهذا يمكن أن يكون مفيدا للغاية في التصحيح عن طريق إدراج طباعة التصحيح (أو كليا وقف وإعطاء موجه continuable) دون تعديل التعليمات البرمجية الأصلية.

Answer 5

لاحظ بعض الأشياء:

(defun foo (bar)
   ... (foo 3) ...)

أعلاه هي وظيفة لديها استدعاء لنفسها.

في Common Lisp، يمكن لمترجم الملف أن يفترض أن FOO لا يتغير.لن يتم استدعاء FOO المحدث لاحقًا.إذا قمت بتغيير ربط وظيفة FOO، فسيستمر استدعاء الوظيفة الأصلية في الانتقال إلى الوظيفة القديمة.

لذا فإن حفظ وظيفة العودية الذاتية لن ينجح في الحالة العامة.خاصة إذا كنت تستخدم مترجمًا جيدًا.

يمكنك حل هذه المشكلة للانتقال دائمًا عبر الرمز على سبيل المثال:(فونكال 'فو 3)

(DEFVAR...) هو نموذج المستوى الأعلى.لا تستخدمه داخل الوظائف.إذا قمت بتعريف متغير، فقم بتعيينه باستخدام SETQ أو SETF لاحقًا.

بالنسبة لمشكلتك، سأستخدم فقط جدول التجزئة لتخزين النتائج المتوسطة.

Answer 6

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

وانظر الشكل 3 (وظيفة "الحالوب ') من الورقة الأصلية له على التحفيظ (" استخدام التحفيظ الآلي كأداة هندسة البرمجيات في أنظمة AI العالم الحقيقي ").

وهكذا انا التخمين، حتى إذا كنت تحصل على اليات العمل التحفيظ، فإنه لن تسريع حقا حتى في هذه الحالة.

Answer 7

وفترة كتبت قبل روتين التحفيظ القليل عن خطة التي تستخدم سلسلة من الإغلاقات لتتبع الدولة memoized:

(define (memoize op)
  (letrec ((get (lambda (key) (list #f)))
           (set (lambda (key item)
                  (let ((old-get get))
                    (set! get (lambda (new-key)
                                (if (equal? key new-key) (cons #t item)
                                    (old-get new-key))))))))
    (lambda args
      (let ((ans (get args)))
        (if (car ans) (cdr ans)
            (let ((new-ans (apply op args)))
              (set args new-ans)
              new-ans))))))

وهذا يحتاج إلى أن تستخدم مثل ذلك:

(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

وأنا متأكد من أن هذا يمكن أن استدار إلى المفضلة لديك نكهة يسب راقب مفرداتيا بكل سهولة.

Answer 8

وربما كنت تفعل شيئا مثل:

(let ((memo (make-hash-table :test #'equal)))
  (defun collatz-steps (n)
    (or (gethash n memo)
    (setf (gethash n memo)
          (cond ((= n 1) 0)
            ((oddp n) (1+ (collatz-steps (+ 1 n n n))))
            (t (1+ (collatz-steps (/ n 2)))))))))

وانها ليست لطيفة وظيفية، ولكن، بعد ذلك، انها ليست الكثير من المتاعب وأنه لا عمل. الجانب السلبي هو أنك لا تحصل على نسخة unmemoized مفيد لاختبار مع ومسح ذاكرة التخزين المؤقت غير المطلة على "صعبة للغاية".