स्टैक ओवरफ्लोइंग

Question

1 मैं एक सीमित-कम फैक्टोरियल फ़ंक्शन (जिज्ञासा से बाहर) बनाने की कोशिश कर रहा हूं। यह n (100000 तक की कोशिश की गई और यह काम करने लगता है, हालांकि मैं काम नहीं कर सकता) शुद्धता के लिए उत्पादन मूल्य की जाँच करें, क्योंकि अच्छी तरह से, यह बड़े है!)

(BigInt(1) to n).reduceRight(_*_) 

लेकिन मुझे डर है कि पूरे BigInt(1) to n रेंज स्मृति में हो सकता है कर रहा हूँ, जबकि मैं सिर्फ यह तत्व तत्व द्वारा reduceRight के लिए की जरूरत है। स्काला के मानक पुस्तकालय कोड पर एक नज़र यह लग रहा है BigInt(1) to n वास्तव में पूरी Range और नहीं एक आलसी Stream आउटपुट लेकिन मैं Stream.range जो मैं इस तरह उपयोग कर सकते हैं पाया की तरह ले रहा है (नोटिस n+1, धारा रेंज अनन्य है)

Stream.range[BigInt](BigInt(1), BigInt(n+1)).reduceRight(_*_) 

यह लेकिन n=100000 के लिए मैं इस ढेर अतिप्रवाह मिल (किसी कारण इसे थोड़ा समय लेता है! जो मुझे लगता है कि शायद सामान्य श्रेणी के वास्तव में एक Stream भी है? बनाता है के लिए) के लिए काम करता n=10000

java.lang.StackOverflowError 
    at java.math.BigInteger.add(Unknown Source) 
    at scala.math.BigInt.$plus(BigInt.scala:161) 
    at scala.math.Numeric$BigIntIsIntegral$class.plus(Numeric.scala:28) 
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40) 
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40) 
    at scala.math.Numeric$Ops.$plus(Numeric.scala:208) 
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695) 
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695) 
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:634) 
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:626) 
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:130) 
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47) 
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131) 
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47) 
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131) 
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47) 
    ... 

ऐसा नहीं है कि reduceRight ही इस

reduceRight(reduceRight(first, second, op), third, op)... 

और इस तरह ढेर अतिप्रवाह तरह बुला रहा है स्पष्ट है। मुझे लगता है कि यह पूंछ-कॉल अनुकूलित नहीं है क्योंकि यह पहले मूल्य को वापस करने से पहले कम करता है और फिर संचालित होता है, इसलिए इसे अनुकूलित नहीं किया जा सकता है। तब मैं इस समस्या से कैसे संपर्क कर सकता हूं? क्या मुझे कार्यात्मक दृष्टिकोण को कम करना चाहिए और कम करने के लिए कस्टम अनिवार्य-शैली कोड का लक्ष्य रखना चाहिए?

मुझे एक बहुत ही अजीब चीज़ के रूप में क्या रोकता है यह है कि (BigInt(1) to n).reduceRight(_*_) बड़े n के लिए ओवरफ़्लो नहीं होता है जबकि लगभग एक ही स्ट्रीम का उपयोग करता है ... यहां क्या हो रहा है?

Answer 1

reduceLeft गणना के लिए लागू किया गया है क्योंकि यह धाराओं पर चला जाता है (और यह क्रम में कॉल करता है)। इस प्रकार आप यह सत्यापित कर सकते हैं:

Stream.range(1,10).map(i => print(i)).reduceLeft((a,b) => println("r")) 

या आप पूंछ प्रत्यावर्तन का उपयोग कर सकते हैं:

final def fac(n: BigInt, prod: BigInt = BigInt(1)): BigInt = { 
    if (n<2) prod else fac(n-1,prod*n) 
} 

(के रूप में ट्रैविस बताते हैं, यह तेजी से पहले कम संख्या गुणा करने के लिए है, जो एक अतिरिक्त ले जाएगा होगा लाइन)।

Answer 2

इसके बजाय reduceLeft का उपयोग करने का प्रयास करें। reduceRight धारा के अंत से शुरू होता है और इस प्रकार हर तत्व को मूल्यांकन करने के लिए मजबूर करता है - ठीक वही जो आप टालना चाहते थे।

Answer 3

आप सही हैं कि उल्टा अनुक्रम को स्टोर करने के लिए आपका पहला समाधान will create a list in memory है। आप बस reduceLeft (जिसमें श्रेणियों पर उस समस्या नहीं है) का उपयोग कर सकते हैं, लेकिन यह विपरीत दिशा में सीमा से गुजर जाएगा। आप बड़े अंत में शुरू लेकिन reduceLeft के आलस्य रखना चाहते हैं किसी कारण से, आप एक पीछे की ओर Range बना सकते हैं:

def fact(n: Int) = (BigInt(n) to 1 by -1).reduceLeft(_ * _) 

other ways हो सकता है आप आसानी से इस समारोह का अनुकूलन कर सकते हैं।

Answer 4

def fac (n: BigInt=1, m:BigInt=1): Stream[BigInt] = 
    Stream.cons (n, fac (n * m, m+1)) 

fac().take (10).toList 
res27: List[BigInt] = List(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880) 

take(10000).toList के साथ भी अच्छी तरह से काम करता है।