كيفية تحسين هذه القطعة من التعليمات البرمجية؟

Question

حلا بلدي ل التمرين 1.11. من SICP هو:

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

كما هو متوقع، يستغرق التقييم مثل (F 100) وقتا طويلا. كنت أتساءل عما إذا كانت هناك طريقة لتحسين هذا الرمز (دون إدراج العودية)، و / أو الاستفادة من مربع متعدد النواة. أنا أستخدم "مخطط ميت".

Answer 1

لست متأكدا من أفضل السبل لرمزه في مخطط، ولكن تقنية مشتركة لتحسين السرعة على شيء مثل هذا سيكون في استخدامه memoization.. وبعد باختصار، تتمثل الفكرة في التخزين المؤقت نتيجة f (p) (ربما لكل ع شاهدها، أو ربما آخر قيم N) بحيث تكون في المرة القادمة التي تسمونها f (p)، يتم إرجاع النتيجة المحفوظة، بدلا من أن تكون إعادة حساب. بشكل عام، ستكون ذاكرة التخزين المؤقت خريطة من Tuple (تمثل حجج الإدخال) إلى نوع الإرجاع.

Answer 2

يخبرك التمرين كتابة وظيفتين، واحد يحسب f "عن طريق عملية متكررة"، وآخر يحسب f "عن طريق عملية تكرارية". لقد فعلت واحد العودية. لأن هذه الوظيفة تشبه إلى حد كبير fib الوظيفة المقدمة في أمثلة القسم الذي ترتبط به، يجب أن تكون قادرا على معرفة ذلك من خلال النظر إلى الأمثلة المتكررة والتكرارية لل fib وظيفة:

; Recursive
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; Iterative
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

في هذه الحالة سوف تحدد f-iter وظيفة التي سوف تأخذ a, b, ، و c الحجج وكذلك count جدال.

هنا هو f-iter وظيفة. لاحظ التشابه ل fib-iter:

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

ومن خلال تجربة القليل والخطأ، وجدت ذلك a, b, ، و c يجب تهيئة ل 2, 1, ، و 0 على التوالي، والذي يتبع أيضا نمط fib وظيفة تهيئة a و b ل 1 و 0. وبعد وبالتالي f يشبه هذا:

(define (f n)
  (f-iter 2 1 0 n))

ملحوظة: f-iter لا يزال العودية وظيفة ولكن بسبب طريقة عمل المخطط، فإنه يعمل كتقادم معالجة ويعمل في O(n) وقت و O(1) مساحة، على عكس التعليمات البرمجية الخاصة بك والتي ليست فقط وظيفة متكررة ولكن عملية متكررة. أعتقد أن هذا هو ما تبحث عنه مؤلف مؤلف التمرين.

Answer 3

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

تحرير: عفوا، لم يروا أنك قلت مقابل التخلص من العودية. في هذه الحالة، خياراتك أكثر محدودة.

Answer 4

يرى هذه المقالة للحصول على برنامج تعليمي جيد حول تطوير وظيفة Fibonacci سريعة مع البرمجة الوظيفية. يستخدم LISP المشترك، وهو مختلفا قليلا عن المخطط في بعض الجوانب، ولكن يجب أن تكون قادرا على الحصول عليها. تنفيذك يعادل bogo-fig وظيفة بالقرب من الجزء العلوي من الملف.

Answer 5

بعبارة أخرى:

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

يتم تضمين مكالماتك العودية في التعبيرات * و +، لذلك فهي ليست مكالمات الذيل (نظرا لأن * و + يتم تقييمها بعد المكالمة العودية.)

إصدار جيريمي روتين من f-iter هل الذيل العريض بدلا من التكرار (أي يبدو وكأنه إجراء متكرر ولكنه فعال مثل المكافئ التكراري).

ومع ذلك يمكنك جعل التكرار صريح:

(define (f n)
  (let iter
    ((a 2) (b 1) (c 0) (count n))
    (if (<= count 0)
      c
      (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

أو

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))

Answer 6

يمكن حل هذا التمرينات المعينة باستخدام Recursion الذيل - بدلا من انتظار كل مكالمة متكررة للعودة (كما هو الحال في الحل المستقبلي الذي تقدمه)، يمكنك تجميع الإجابة في معلمة، وبهذه الطريقة التي يتصرف فيها العودية بالضبط نفس التكرار من حيث المساحة التي يستهلكها. على سبيل المثال:

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))