रिकर्सिव फ़ंक्शन एक स्टैक ओवरफ़्लो

Question

का कारण बनता है मैं क्लोजर में प्राइम संख्याओं की गणना करने के लिए एक सरल चलनी फ़ंक्शन लिखने की कोशिश कर रहा हूं। मैंने एक कुशल चलनी कार्य लिखने के बारे में this प्रश्न देखा है, लेकिन मैं अभी तक उस बिंदु पर नहीं हूं। अभी मैं बस एक बहुत ही सरल (और धीमी) चलनी लिखने की कोशिश कर रहा हूं। यहाँ मैं क्या लेकर आए हैं है:

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

छोटे पर्वतमाला यह ठीक काम करता है के लिए, लेकिन बड़े श्रेणियों के लिए एक ढेर अतिप्रवाह कारण बनता है:

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) 

मैंने सोचा था कि recur का उपयोग करके यह एक गैर होगा -स्टैक उपभोग लूपिंग निर्माण? मैं क्या खो रहा हूँ?

Answer 1

आपको filter की आलस्य से मारा जा रहा है। अपने recur फॉर्म में (filter ...) से (doall (filter ...)) बदलें और समस्या दूर होनी चाहिए।

एक और अधिक में गहराई से स्पष्टीकरण:

filter करने के लिए कॉल एक आलसी seq देता है, जो seq फ़िल्टर्ड की वास्तविक तत्व materializes के रूप में की आवश्यकता है। लिखित के रूप में, आपका कोड filterfilter पर filter पर filter पर ढेर करता है ..., प्रत्येक पुनरावृत्ति पर filter आईएनजी का एक और स्तर जोड़ना; कुछ बिंदु पर यह उड़ाता है। समाधान प्रत्येक पुनरावृत्ति पर पूरे परिणाम को मजबूर करना है ताकि अगला व्यक्ति पूरी तरह से एहसास सीक पर फ़िल्टरिंग कर सके और आलसी सीक प्रसंस्करण की एक अतिरिक्त परत जोड़ने के बजाय पूरी तरह से एहसास हुआ सीक वापस कर दे; यह doall करता है।

Answer 2

एल्गोरिदमिक रूप से समस्या यह है कि जब आप इसका कोई और उद्देश्य नहीं लेते हैं तो आप फ़िल्टरिंग जारी रखते हैं। रोक को जल्द से जल्द प्रत्यावर्तन गहराई में द्विघात कमी (sqrt(n) बनाम n) को प्राप्त होता है: 16,000 (1862 के बजाय सिर्फ 30 पुनरावृत्तियों प्रदर्शन) के लिए

(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)) 

चलाता है ठीक है, और भी के लिए 160,000, on ideone। doall के बिना भी 5% तेज चलता है।