Hiệu suất của kiểu đệ quy và ắc quy

Question

Chúng ta có hai hàm tính toán giai thừa của một số đã cho. Cái đầu tiên, !, sử dụng kiểu tích lũy. Thứ hai, fact, sử dụng đệ quy tự nhiên.

(define (! n0) 
    (local (;; accumulator is the product of all natural numbers in [n0, n) 
     (define (!-a n accumulator) 
     (cond 
      [(zero? n) accumulator] 
      [else (!-a (sub1 n) (* n accumulator))]))) 
    (!-a n0 1))) 

và

(define (fact n) 
    (cond 
    [(= 0 n) 1] 
    [else (* n (fact (- n 1)))])) 

Ở dưới cùng của Mục 31, HtDP khẳng định rằng phiên bản đệ quy một cách tự nhiên thường là nhanh nếu không nhanh hơn so với phiên bản accumulator, nhưng không nêu rõ lý do tại sao. Tôi đã làm một số đọc về điều này và có vẻ như câu trả lời là 'tail call optimization/elimination', nhưng bài viết Wikipedia dường như là mâu thuẫn với những gì HtDP nói, ít nhất là đối với hiệu suất. Tại sao cái này rất?

---

Tại nơi làm việc, kiểu đệ quy nhanh hơn. Ở nhà, phong cách tích lũy nhanh hơn. Có không có heuristic chung để hướng dẫn một sự lựa chọn như là phong cách thường được ưa thích? Tôi hiểu rằng phong cách tích lũy là hiệu quả bộ nhớ hơn, nhưng nếu chúng ta hạn chế các cuộc thảo luận để thực hiện một mình, nó là không rõ ràng, ít nhất là với tôi, đó là sự lựa chọn tốt hơn.

---

Tôi đã nghĩ về điều này một chút nữa, và sẽ phải sang bên kia với bài viết trên Wikipedia về tính ưu việt của đệ quy ắc-style trong trường hợp chung. Nó không chỉ làm giảm việc sử dụng không gian stack/heap, truy cập bộ nhớ luôn ở phía sau quyền truy cập đăng ký và chỉ có thể được hiển thị rõ ràng hơn khi đa lõi ở đây. Tuy nhiên, HtDP chứng minh rằng việc kiểm tra thực tế là bắt buộc trong mọi trường hợp.

Answer 1

Câu trả lời sẽ tùy thuộc vào chi tiết của hệ thống Vợt. Đây là của tôi về nó.

Có hai sự khác biệt chính giữa phiên bản đệ quy tự nhiên và phiên bản bộ tích lũy. Đầu tiên, phiên bản tích lũy được viết theo kiểu thời trang cho phép tối ưu hóa cuộc gọi đuôi. Điều này giúp làm cho phiên bản tích lũy nhanh hơn, vì cần phải tạo ít khung ngăn xếp hơn. Nhưng điều đó trái ngược với những gì được thảo luận trong HtDP và bạn đã thấy trên máy tính của bạn.

Sự khác biệt khác là thứ tự nhân. Phiên bản bội đệ quy một cách tự nhiên những con số từ 1 đến 20 trong thứ tự tăng dần, đó là

((((1 * 2) * 3) * … * 19) * 20) 

phiên bản ắc nhân với số cùng thứ tự giảm dần, đó là

((((20 * 19) * 18) * … * 2) * 1) 

Về mặt toán học, đây là những giống nhau và hai hàm giai thừa sẽ cho kết quả tương tự. Tuy nhiên, sự khác biệt này có thể quan trọng.Đặc biệt, ở bất kỳ phép nhân trung gian nào, kết quả trung gian sẽ lớn hơn cho phép tính sau hơn phép tính trước đây.

Giai thừa 20 là một số lớn. Nó sẽ không vừa với số nguyên 32 bit. Điều đó có nghĩa rằng vợt sẽ cần phải sử dụng một số nguyên chiều dài tùy ý (một "bignum") để đại diện cho câu trả lời, và một số kết quả trung gian. Số học chính xác tùy ý, bao gồm phép nhân liên quan đến bignums, chậm hơn so với số học chính xác cố định.

Vì các kết quả trung gian trong phiên bản bộ tích lũy luôn lớn hơn phiên bản đệ quy tự nhiên, nên phiên bản bộ nạp sẽ yêu cầu một bản bignum sớm hơn phiên bản đệ quy. Tóm lại, trong khi cả hai phiên bản yêu cầu cùng một số phép nhân, phiên bản tích lũy đòi hỏi nhiều phép nhân chính xác hơn. Điều này làm cho phiên bản ắc quy chậm hơn. Rõ ràng, chi phí bổ sung của số học vượt quá mức tiết kiệm từ việc giảm số lượng khung ngăn xếp.

Vậy tại sao xu hướng tương tự sẽ không hiển thị trên máy tính ở nhà của bạn? Bạn nói đó là một chiếc iMac của Intel, vì vậy nó có lẽ là một hệ thống 64 bit. Trong khi 20! là một số lớn, nó là nhỏ so với những gì sẽ phù hợp trong một số nguyên 64 bit, do đó, máy tính ở nhà của bạn không làm bất kỳ số học chính xác tùy ý và thứ tự không quan trọng. HtDP đủ lớn để sử dụng hệ thống 32 bit, giống như Windows XP trên máy tính của bạn.

Hữu ích hơn để khám phá sự khác biệt sẽ là một chức năng cho phép tính sản phẩm của một danh sách các số, hoặc

(define (product numlist) 
    (* (car numlist) (product (cdr numlist))) 

hoặc một phiên bản accumulator. Sau đó, bạn có thể nạp các số theo thứ tự tăng dần hoặc giảm dần, không phụ thuộc vào việc bạn đang sử dụng phương pháp tiếp cận dựa trên đệ quy hay dựa trên tự nhiên.

Answer 2

Tôi không biết người dùng trình biên dịch Racket, nhưng tôi sẽ suy đoán.

Cuộc gọi đuôi thường đắt hơn cuộc gọi thông thường (điều này đúng trong .NET, chậm hơn 7 lần), nhưng trong một số trường hợp, cuộc gọi đuôi có thể bị xóa và kết thúc là vòng lặp kiểu while(1) { ... } C do đó sẽ không có cuộc gọi thêm để thực hiện, chỉ cần một bước nhảy đơn giản địa phương, có hiệu quả loại bỏ phí ứng dụng thủ tục.

Answer 3

Trình biên dịch tốt sẽ biến phe đệ qui thành đuôi đệ quy. Vì vậy, không nên có sự khác biệt trong mã được biên dịch.

Answer 4

Nhiều điểm tốt ở trên. Tôi thích phân tích những gì nên được so với lý do tại sao nó không. Đó là những thứ mà thành công của Project Euler được thực hiện. Quá sớm một chuyến đi từ fixnums có thể là vấn đề.

Chuỗi số có thể được nhân từ lớn đến nhỏ hoặc ngược lại. Chúng tôi cũng có lệnh 'do' thực hiện lặp lại trực tiếp và tương tự.

(define (thực tế n) (if (= n 1) 1 (* n (thực tế (- n 1)))))

(xác định (fact1 n) (làm ([nn (- n 1)] [p 1 (* pn)]) ((= n 1) p)))

(define (fact2 n) (do ([i 1 (+ i 1)] [p 1 (* pi)]) ((< ni) p)))

(xác định (fact3 n) (cho f ((nn) (p 1)) (if (= n 1) p (f (- n 1) (* pn)))))

(xác định (fact4 n) (cho f ((i 1) (p 1)) (nếu (< ni) p (f (+ i 1) (* pi)))))