Hiệu quả: đệ quy vs vòng lặp

Question

Đây chỉ là sự tò mò về phía tôi, nhưng hiệu quả hơn, đệ quy hay vòng lặp là gì?

Với hai chức năng (sử dụng lisp phổ biến):

(defun factorial_recursion (x) 
    (if (> x 0) 
     (* x (factorial_recursion (decf x))) 
     1)) 

và

(defun factorial_loop (x) 
    (loop for i from 1 to x for result = 1 then 
     (* result i) finally 
     (return result))) 

Đó là hiệu quả hơn?

Answer 1

Tôi thậm chí không phải đọc mã của bạn.

Vòng lặp hiệu quả hơn cho giai thừa. Khi bạn đệ quy, bạn có tối đa x các cuộc gọi chức năng trên ngăn xếp.

Bạn gần như không bao giờ sử dụng đệ quy vì lý do hiệu suất. Bạn sử dụng đệ quy để làm cho vấn đề đơn giản hơn.

Answer 2

Nếu bạn có thể viết hàm đệ quy một cách như vậy mà các cuộc gọi đệ quy là điều cuối cùng thực hiện (và chức năng là như vậy đuôi-đệ quy) và ngôn ngữ và trình biên dịch/phiên dịch bạn đang sử dụng hỗ trợ đệ quy đuôi, sau đó hàm đệ quy có thể (thường) được tối ưu hóa thành mã thực sự lặp lại và nhanh như phiên bản lặp của cùng một hàm.

Sam I Am là chính xác, các hàm lặp thường nhanh hơn các đối tác đệ quy của chúng. Nếu hàm đệ quy là nhanh như hàm lặp lại thực hiện cùng một điều, bạn phải dựa vào trình tối ưu hóa.

Lý do cho điều này là một cuộc gọi hàm là nhiều hơn đắt hơn một bước nhảy, cộng với bạn tiêu thụ không gian ngăn xếp, một (rất) tài nguyên hữu hạn.

Hàm bạn cung cấp không phải là đệ quy đuôi vì bạn gọi factorial_recursion và sau đó nhân nó với x. Một ví dụ về một phiên bản đuôi-đệ quy sẽ

(defun factorial-recursion-assist (x cur) 
    (if (> x 1) 
     (factorial-recursion-assist (- x 1) (+ cur (* (- x 1) x))) 
     cur)) 

(defun factorial-recursion (x) 
    (factorial-recursion-assist x 1)) 

(print (factorial-recursion 4)) 

Answer 3

Dưới đây là một thừa đuôi-đệ quy (tôi nghĩ):

(defun fact (x) 
    (funcall (alambda (i ret) 
      (cond ((> i 1) 
        (self (1- i) (* ret i))) 
        (t 
        ret))) 
      x 1)) 

Answer 4

Mu.

Nghiêm túc bây giờ, điều đó không quan trọng. Không cho các ví dụ kích thước này. Cả hai đều có cùng một phức tạp. Nếu mã của bạn không đủ nhanh cho bạn, đây có lẽ là một trong những địa điểm cuối cùng bạn xem.

Bây giờ, nếu bạn thực sự muốn biết cái nào nhanh hơn, hãy đo chúng. Trên SBCL, bạn có thể gọi từng hàm trong một vòng lặp và đo thời gian. Vì bạn có hai hàm đơn giản, time là đủ. Nếu chương trình của bạn phức tạp hơn, thì profiler sẽ hữu ích hơn. Gợi ý: nếu bạn không cần một profiler cho phép đo của bạn, bạn có thể không cần phải lo lắng về hiệu suất.

Trên máy tính của tôi (SBCL 64 bit), tôi chạy chức năng của bạn và nhận điều này:

CL-USER> (time (loop repeat 1000 do (factorial_recursion 1000))) 
Evaluation took: 
    0.540 seconds of real time 
    0.536034 seconds of total run time (0.496031 user, 0.040003 system) 
    [ Run times consist of 0.096 seconds GC time, and 0.441 seconds non-GC time. ] 
    99.26% CPU 
    1,006,632,438 processor cycles 
    511,315,904 bytes consed 

NIL 
CL-USER> (time (loop repeat 1000 do (factorial_loop 1000))) 
Evaluation took: 
    0.485 seconds of real time 
    0.488030 seconds of total run time (0.488030 user, 0.000000 system) 
    [ Run times consist of 0.072 seconds GC time, and 0.417 seconds non-GC time. ] 
    100.62% CPU 
    902,043,247 processor cycles 
    511,322,400 bytes consed 

NIL 

Sau khi đưa chức năng của bạn trong một tập tin với (declaim (optimize speed)) ở phía trên, lần đệ quy giảm xuống còn 504 mili giây và thời gian vòng lặp giảm xuống còn 475 mili giây.

Và nếu bạn thực sự muốn biết điều gì đang xảy ra, hãy thử dissasemble về chức năng của bạn và xem những gì trong đó.

Một lần nữa, điều này có vẻ không phải vấn đề với tôi. Cá nhân, tôi cố gắng sử dụng Common Lisp như một ngôn ngữ kịch bản để tạo mẫu, sau đó lược tả và tối ưu hóa các phần chậm. Bắt từ 500ms đến 475ms là không có gì. Ví dụ, trong một số mã cá nhân, tôi nhận được một vài đơn đặt hàng tăng tốc độ lớn bằng cách thêm một loại phần tử vào một mảng (do đó làm cho mảng lưu trữ 64 lần nhỏ hơn trong trường hợp của tôi). Chắc chắn, về lý thuyết nó sẽ nhanh hơn để tái sử dụng mảng đó (sau khi làm cho nó nhỏ hơn) và không phân bổ nó hơn và hơn. Nhưng chỉ cần thêm :element-type bit vào đó là đủ cho tình huống của tôi - nhiều thay đổi hơn sẽ đòi hỏi nhiều thời gian hơn cho rất ít lợi ích bổ sung. Có lẽ tôi cẩu thả, nhưng 'nhanh' và 'chậm' không có ý nghĩa gì với tôi. Tôi thích 'đủ nhanh' và 'quá chậm'. Cả hai chức năng của bạn là 'đủ nhanh' trong hầu hết các trường hợp (hoặc cả hai đều 'quá chậm' trong một số trường hợp) nên không có sự khác biệt thực sự giữa chúng.