Chức năng đệ quy gây tràn ngăn xếp

Question

Tôi đang cố gắng viết một hàm sàng đơn giản để tính số nguyên tố trong clojure. Tôi đã nhìn thấy this câu hỏi về cách viết một chức năng sàng hiệu quả, nhưng tôi chưa đến điểm đó. Ngay bây giờ tôi chỉ đang cố viết một cái rây rất đơn giản (và chậm). Dưới đây là những gì tôi đã đưa ra:

(defn sieve [potentials primes] 
    (if-let [p (first potentials)] 
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p)) 
    primes)) 

Đối với các khoảng nhỏ nó hoạt động tốt, nhưng gây ra một tràn ngăn xếp cho các phạm vi lớn:

user=> (sieve (range 2 30) []) 
[2 3 5 7 11 13 17 19 23 29] 
user=> (sieve (range 2 15000) []) 
java.lang.StackOverflowError (NO_SOURCE_FILE:0) 

Tôi nghĩ rằng bằng cách sử dụng recur này sẽ là một tổ chức phi -stack-loop looping xây dựng? Tôi đang thiếu gì?

Answer 1

Bạn đang bị ảnh hưởng bởi sự lười biếng của filter. Thay đổi (filter ...) thành (doall (filter ...)) trong biểu mẫu recur của bạn và sự cố sẽ biến mất.

Một sâu hơn giải thích:

Các cuộc gọi đến filter trả về một seq lười biếng, mà materializes yếu tố thực tế của seq lọc theo yêu cầu. Như đã được viết, mã của bạn sẽ ngăn xếp filter theo số filter khi số filter ..., thêm một cấp độ khác là filter ing tại mỗi lần lặp; tại một số điểm này thổi lên. Giải pháp là buộc toàn bộ kết quả tại mỗi lần lặp lại để cho phép tiếp theo sẽ thực hiện lọc của nó trên một seq hoàn toàn nhận biết và trả về một seq hoàn toàn nhận biết thay vì thêm một lớp bổ sung xử lý seq lười biếng; đó là những gì doall thực hiện.

Answer 2

Vấn đề về mặt thuật toán là bạn tiếp tục lọc khi không có mục đích nào khác. Dừng càng sớm càng tốt đạt được giảm bậc hai trong sâu đệ quy (sqrt(n) vs n):

(defn sieve [potentials primes]  
    (if-let [p (first potentials)] 
     (if (> (* p p) (last potentials)) 
     (concat primes potentials) 
     (recur (filter (fn [n] (not= (mod n p) 0)) potentials) 
       (conj primes p))) 
    primes)) 

Chạy OK cho 16.000 (thực hiện chỉ trong 30 lần lặp thay vì 1862), và cho 160.000 quá, on ideone. Thậm chí chạy nhanh hơn 5% mà không cần doall.