Làm cách nào để viết chức năng Clojure này để nó không thổi tung ngăn xếp?

Question

Tôi mới sử dụng Clojure và tôi nghĩ rằng cách tiếp cận viết mã của tôi cho đến nay không phù hợp với "Way of Clojure". Ít nhất, tôi tiếp tục viết các hàm giữ cho dẫn đến lỗi StackOverflow với các giá trị lớn. Tôi đã học về cách sử dụng recur đã được một bước tiến tốt. Tuy nhiên, làm thế nào để thực hiện các chức năng như một chức năng dưới đây cho các giá trị như 2500000?

(defn fib [i] 
    (if (>= 2 i) 
    1 
    (+ (fib (dec i)) 
     (fib (- i 2))))) 

Chức năng là, đối với mắt tôi, việc triển khai "đồng bằng" của trình tạo Fibonacci. Tôi đã thấy các triển khai khác được tối ưu hóa nhiều hơn, nhưng ít rõ ràng hơn về những gì họ thực hiện. I E. khi bạn đọc định nghĩa hàm, bạn không đi "oh, fibonacci".

Mọi con trỏ sẽ được đánh giá cao!

Answer 1

Bạn cần có mô hình tinh thần về cách hoạt động của chức năng. Giả sử bạn tự thực hiện chức năng của mình, sử dụng các mẩu giấy cho mỗi lời gọi. Trước tiên, bạn viết (fib 250000), sau đó bạn thấy "oh, tôi cần tính (fib 249999) và (fib 249998) và cuối cùng thêm chúng", vì vậy bạn lưu ý và bắt đầu hai mẩu tin lưu niệm mới. Bạn không thể vứt bỏ cái đầu tiên, bởi vì nó vẫn có những thứ cần làm cho bạn khi bạn hoàn thành các phép tính khác. Bạn có thể tưởng tượng rằng tính toán này sẽ cần rất nhiều mẩu tin lưu niệm.

Một cách khác không phải là bắt đầu ở trên cùng, nhưng ở phía dưới cùng. Làm thế nào bạn sẽ làm điều này bằng tay? Bạn sẽ bắt đầu với các số đầu tiên, 1, 1, 2, 3, 5, 8 & hellip ;, và sau đó luôn thêm hai số cuối cùng, cho đến khi bạn đã thực hiện nó i lần. Bạn thậm chí có thể vứt bỏ tất cả các số trừ hai số cuối cùng ở mỗi bước, vì vậy bạn có thể sử dụng lại hầu hết các mẩu tin lưu niệm.

(defn fib [i] 
    (loop [a 0 
     b 1 
     n 1] 
    (if (>= n i) 
     b 
     (recur b 
       (+ a b) 
       (inc n))))) 

Đây cũng là một thực hiện khá rõ ràng, nhưng trong những cách, không phải của các gì. Nó luôn luôn có vẻ khá thanh lịch khi bạn có thể chỉ đơn giản là viết ra một định nghĩa và nó được tự động chuyển thành một phép tính hiệu quả, nhưng lập trình là sự biến đổi đó. Nếu một cái gì đó được chuyển đổi tự động, thì vấn đề cụ thể này đã được giải quyết (thường theo cách tổng quát hơn).

Suy nghĩ "làm cách nào tôi thực hiện bước này trên giấy" thường dẫn đến việc triển khai tốt.

Answer 2

Một máy phát Fibonacci được thực hiện theo cách "đơn giản", như trong định nghĩa của chuỗi, sẽ luôn thổi tung ngăn xếp của bạn lên. Không có hai cuộc gọi đệ quy đến fib là đệ quy đuôi, định nghĩa như vậy không thể được tối ưu hóa.

Thật không may, nếu bạn muốn viết một triển khai hiệu quả làm việc với số lượng lớn, bạn sẽ phải chấp nhận thực tế là ký pháp toán học không dịch mã như sạch như chúng ta muốn.

Ví dụ: triển khai không đệ quy có thể được tìm thấy trong clojure.contrib.lazy-seqs. Có thể tìm thấy một loạt các cách tiếp cận khác nhau cho vấn đề này trên Haskell wiki. Nó không phải là khó hiểu với kiến ​​thức cơ bản của lập trình chức năng.

Answer 3

;;from "The Pragmatic Programmers Programming Clojure" 
(defn fib [] (map first (iterate (fn [[a b]][b (+ a b)])[0N 1N]))) 
(nth (fib) 2500000)