पूर्णांक (स्कैला) के जोड़े की पूंछ-पुनरावर्ती बाध्य धारा?

Question

मैं स्कैला के लिए बहुत नया हूं, इसलिए मेरी अज्ञानता को क्षमा करें! मैं पूर्णांक से जुड़े पूर्णांक के जोड़े की पुनरावृत्ति करने की कोशिश कर रहा हूं। उदाहरण के लिए, यदि अधिकतम 5 है, तो यात्रा लौटना चाहिए:

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5) 

मैं कोशिश करने के लिए चुन लिया है और पूंछ पुनरावर्ती एक स्ट्रीम के रूप में इस वापसी:

@tailrec 
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = { 
     if (i == maximum && j == maximum) Stream.empty 
     else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum) 
     else (i, j) #:: _pairs(i, j + 1, maximum) 
    } 

tailrec एनोटेशन के बिना कोड काम करता है:

scala> _pairs(0, 0, 5).take(11) 
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?) 

scala> _pairs(0, 0, 5).take(11).toList 
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4)) 

लेकिन यह मेरे लिए पर्याप्त नहीं है। संकलक सही ढंग से उनका कहना है कि _pairs की अंतिम पंक्ति _pairs नहीं लौटा रहा है:

could not optimize @tailrec annotated method _pairs: it contains a recursive call not in tail position 
    else (i, j) #:: _pairs(i, j + 1, maximum) 
       ^

तो, मैं कई प्रश्न हैं:

• सीधे ऊपर कार्यान्वयन को संबोधित कर, कैसे करता है एक पूंछ पुनरावर्ती वापसी स्ट्रीम [(Int, Int)]?
• एक कदम पीछे लेना, पूर्णांक के बाध्य अनुक्रमों को फिर से चलाने के लिए सबसे मेमोरी-कुशल तरीका क्या है? मैं रेंज पर पुनरावृत्ति नहीं करना चाहता क्योंकि Range extends IndexedSeq, और मैं नहीं चाहता कि अनुक्रम पूरी तरह स्मृति में मौजूद हो। या मैं गलत हूँ? अगर मैं रेंज पर पुन: प्रयास करता हूं। क्या मैं इसे स्मृति में आने से बचता हूं? (!)

अजगर, सभी मैं चाहता हूँ है:

In [6]: def _pairs(maximum): 
    ...:  for i in xrange(maximum+1): 
    ...:   for j in xrange(maximum+1): 
    ...:    yield (i, j) 
    ...:    

In [7]: p = _pairs(5) 

In [8]: [p.next() for i in xrange(11)] 
Out[8]: 
[(0, 0), 
(0, 1), 
(0, 2), 
(0, 3), 
(0, 4), 
(0, 5), 
(1, 0), 
(1, 1), 
(1, 2), 
(1, 3), 
(1, 4)] 

आपकी मदद के लिए धन्यवाद! अगर आपको लगता है कि मुझे संदर्भ/एपीआई दस्तावेज़/कुछ और पढ़ने की जरूरत है तो कृपया मुझे बताएं, क्योंकि मैं सीखना चाहता हूं।

Answer 1

यह पूंछ-प्रत्यावर्तन नहीं है

चलो मान लीजिए आप एक स्ट्रीम के बजाय एक सूची बना रहे थे:

def foo(n: Int): List[Int] = 
    if (n == 0) 
    0 :: Nil 
    else 
    n :: foo(n - 1) 

सामान्य स्थिति में (मुझे एक सरल कार्य का उपयोग मेरी बात बनाने के लिए करते हैं) इस रिकर्सन में, foo(n - 1) के बाद फ़ंक्शन को उस सूची के साथ कुछ करना पड़ता है जो यह लौटाता है - इसे सूची की शुरुआत में किसी अन्य आइटम को जोड़ना होगा। तो समारोह पूंछ रिकर्सिव नहीं हो सकता है, क्योंकि रिकर्सन के बाद सूची में कुछ किया जाना है।

पूंछ रिकर्सन के बिना, n के कुछ बड़े मूल्य के लिए, आप स्टैक स्पेस से बाहर हो जाते हैं।

सामान्य सूची समाधान

सामान्य समाधान एक ListBuffer एक दूसरे पैरामीटर के रूप में पारित, और भरने कि करने के लिए किया जाएगा।

def foo(n: Int) = { 
    def fooInternal(n: Int, list: ListBuffer[Int]) = { 
    if (n == 0) 
     list.toList 
    else { 
     list += n 
     fooInternal(n - 1, list) 
    } 
    } 
    fooInternal(n, new ListBuffer[Int]()) 
} 

क्या आप कर रहे हैं "tail recursion modulo cons" के रूप में जाना जाता है, और यह एक अनुकूलन लिस्प Prolog compilers द्वारा स्वचालित रूप से प्रदर्शन किया, जब वे देखते हैं पूंछ प्रत्यावर्तन सापेक्ष पैटर्न बुरा है, क्योंकि यह इतना आम है। स्कैला का कंपाइलर स्वचालित रूप से इसे अनुकूलित नहीं करता है।

स्ट्रीम पूंछ प्रत्यावर्तन की जरूरत नहीं है

स्ट्रीम पूंछ प्रत्यावर्तन की जरूरत नहीं है ढेर में स्थान कम से बचने के लिए - यह है क्योंकि वे एक चतुर चाल का उपयोग पर foo को पुनरावर्ती कॉल को क्रियान्वित करने से रोकने के लिए बिंदु जहां यह कोड में दिखाई देता है। फंक्शन कॉल एक थंक में लपेटा जाता है, और केवल उस बिंदु पर बुलाया जाता है कि आप वास्तव में स्ट्रीम से मूल्य प्राप्त करने का प्रयास करते हैं। foo पर केवल एक कॉल सक्रिय है - यह कभी भी रिकर्सिव नहीं होता है।

मैंने स्टैक ओवरफ्लो पर how the #:: operator works समझाते हुए पिछले उत्तर लिखा है। यहां बताया गया है कि जब आप निम्न रिकर्सिव स्ट्रीम फ़ंक्शन को कॉल करते हैं तो क्या होता है। (यह गणितीय अर्थ में पुनरावर्ती है, लेकिन यह जिस तरह से आप आमतौर पर उम्मीद फोन एक समारोह के भीतर से एक समारोह कॉल नहीं है।)

def foo(n: Int): Stream[Int] = 
    if (n == 0) 
    0 #:: Nil 
    else 
    n #:: foo(n - 1) 

आप foo(10) कहते हैं, यह एक तत्व पहले से ही गणना की साथ एक धारा रिटर्न , और पूंछ एक थंक है जो अगली बार स्ट्रीम से तत्व की आवश्यकता होने पर foo(9) पर कॉल करेगा। foo(9) अभी कॉल नहीं किया गया है - बल्कि कॉल स्ट्रीम के अंदर lazy val तक बाध्य है, और foo(10) तुरंत लौटता है। जब आपको अंत में स्ट्रीम में दूसरे मान की आवश्यकता होती है, तो foo(9) कहा जाता है, और यह एक तत्व की गणना करता है और एचटी स्ट्रीम की पूंछ को एक थंक के रूप में सेट करता है जो foo(8) पर कॉल करेगा। foo(9)foo(8) पर कॉल किए बिना तुरंत लौटता है। और इतने पर ...

यह आपको स्मृति से बाहर चलने के बिना अनंत धाराओं बनाने के लिए, की अनुमति देता है, उदाहरण के लिए:

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1) 

(सावधान क्या आपरेशन आप इस धारा पर फोन रहो तुम एक करने की कोशिश करते हैं। forEach या एक map, आप अपने पूरे ढेर को भरने देंगे, लेकिन take का उपयोग कर धारा की एक मनमाना उपसर्ग के साथ काम करने के लिए एक अच्छा तरीका है।)

एक सरल पूरी तरह समाधान

के बजाय फिर से साथ काम कर कर्सर और स्ट्रीम, क्यों न केवल स्कैला के for लूप का उपयोग करें?

def pairs(maximum:Int) = 
    for (i <- 0 to maximum; 
     j <- 0 to maximum) 
    yield (i, j) 

यह पूरे संग्रह को स्मृति में पूरा करता है, और IndexedSeq[(Int, Int)] देता है।

यदि आपको विशेष रूप से स्ट्रीम की आवश्यकता है, तो आप पहली श्रेणी को Stream में परिवर्तित कर सकते हैं।

def pairs(maximum:Int) = 
    for (i <- 0 to maximum toStream; 
     j <- 0 to maximum) 
    yield (i, j) 

यह एक Stream[(Int, Int)] वापस आ जाएगी। जब आप अनुक्रम में किसी निश्चित बिंदु तक पहुंचते हैं, तो इसे स्मृति में पूरा किया जाएगा, और यह तब तक टिकेगा जब तक कि उस तत्व से पहले स्ट्रीम में किसी भी बिंदु का संदर्भ न हो।

आप दोनों श्रेणियों को विचारों में परिवर्तित करके बेहतर स्मृति उपयोग भी प्राप्त कर सकते हैं।

def pairs(maximum:Int) = 
    for (i <- 0 to maximum view; 
     j <- 0 to maximum view) 
    yield (i, j) 

यह एक SeqView[(Int, Int),Seq[_]] कि प्रत्येक तत्व हर बार जब आप इसकी आवश्यकता की गणना करता है देता है, और precomputed परिणाम की दुकान नहीं है।

तुम भी एक iterator (जो आप केवल एक बार पार कर सकते हैं) प्राप्त कर सकते हैं उसी तरह

def pairs(maximum:Int) = 
    for (i <- 0 to maximum iterator; 
     j <- 0 to maximum iterator) 
    yield (i, j) 

कि Iterator[(Int, Int)] देता है।

Answer 2

हो सकता है कि एक इटरेटर बेहतर आप के लिए अनुकूल है?

class PairIterator (max: Int) extends Iterator [(Int, Int)] { 
    var count = -1 
    def hasNext = count <= max * max 
    def next() = { count += 1; (count/max, count % max) } 
} 

val pi = new PairIterator (5) 
pi.take (7).toList