कारण है कि आप आलसी रूप से एक ट्रैवर्सबल से इटेटरेटर नहीं प्राप्त कर सकते हैं यह है कि आप आंतरिक रूप से नहीं कर सकते हैं। ट्रैवर्सबल foreach
परिभाषित करता है, और foreach
स्टॉप किए बिना सब कुछ के माध्यम से चलता है। वहां कोई आलस्य नहीं है।
तो आपके पास आलसी बनाने के लिए दो विकल्प हैं, दोनों भयानक हैं।
सबसे पहले, आप हर बार पूरी चीज के माध्यम से फिर से शुरू कर सकते हैं। आप कुशल अनुक्रमित टुकड़ा करने की क्रिया के लिए होता है (मैं स्काला इटरेटर का उपयोग करने के लिए जा रहा हूँ, लेकिन जावा इटरेटर मूलतः एक ही है।)
class Terrible[A](t: Traversable[A]) extends Iterator[A] {
private var i = 0
def hasNext = i < t.size // This could be O(n)!
def next: A = {
val a = t.slice(i,i+1).head // Also could be O(n)!
i += 1
a
}
}
, यह ठीक हो जाएगा। यदि नहीं, तो प्रत्येक "अगली" इटरेटर की लंबाई में समय रैखिक लगेगा, O(n^2)
के लिए बस इसे पार करने के लिए। लेकिन यह भी आलसी नहीं है; अगर आप का कहना है कि यह होना चाहिए कि आप सभी मामलों में O(n^2)
लागू करने और कर
class Terrible[A](t: Traversable[A]) extends Iterator[A] {
private var i = 0
def hasNext: Boolean = {
var j = 0
t.foreach { a =>
j += 1
if (j>i) return true
}
false
}
def next: A = {
var j = 0
t.foreach{ a =>
j += 1
if (j>i) { i += 1; return a }
}
throw new NoSuchElementException("Terribly empty")
}
}
यह स्पष्ट रूप से सामान्य कोड के लिए एक भयानक विचार है करने के लिए है।
जाने का दूसरा तरीका थ्रेड का उपयोग करना है और जैसा कि यह जा रहा है, के ट्रैवर्सल को अवरुद्ध करना है। यह सही है, आपको प्रत्येक तत्व पहुंच पर इंटर-थ्रेड संचार करना होगा! चलो देखते हैं कि यह कैसे काम करता है - मैं यहां जावा थ्रेड का उपयोग करने जा रहा हूं क्योंकि स्कैला अक्का-स्टाइल अभिनेताओं के स्विच के बीच में है (हालांकि पुराने कलाकारों या अक्का अभिनेताओं या स्कालाज़ अभिनेताओं या लिफ्ट अभिनेताओं में से कोई भी या (आदि) काम करेंगे)
class Horrible[A](t: Traversable[A]) extends Iterator[A] {
private val item = new java.util.concurrent.SynchronousQueue[Option[A]]()
private class Loader extends Thread {
override def run() { t.foreach{ a => item.put(Some(a)) }; item.put(None) }
}
private val loader = new Loader
loader.start
private var got: Option[A] = null
def hasNext: Boolean = {
if (got==null) { got = item.poll; hasNext }
else got.isDefined
}
def next = {
if (got==null) got = item.poll
val ans = got.get
got = null
ans
}
}
यह O(n^2)
आपदा से बचा जाता है, लेकिन संबंधों ऊपर एक धागा और सख्त धीमी तत्व-दर-तत्व पहुंच नहीं है। मुझे एक सामान्य ट्रैवर्सबल के लिए 100 एम की तुलना में, मेरी मशीन पर प्रति सेकंड लगभग 2 मिलियन एक्सेस मिलती है। यह सामान्य कोड के लिए स्पष्ट रूप से एक भयानक विचार है।
तो आपके पास यह है। ट्रैवर्सबल सामान्य रूप से आलसी नहीं है, और प्रदर्शन को समझौता किए बिना आलसी बनाने का कोई अच्छा तरीका नहीं है।
स्रोत कोड के अनुसार, 'toIterator' को डिफ़ॉल्ट रूप से कार्यान्वित किया गया है: '.toStream.iterator' जो आलसी है। – paradigmatic
@paradigmatic इसे देखने के लिए धन्यवाद। मैंने वही किया, और जब तक मैंने इसका परीक्षण नहीं किया, तब तक उसी निष्कर्ष तक पहुंचा। मैंने एक छोटा परीक्षण केस जोड़ा है जो मेरी समस्या दिखाता है। – Andres
@paradigmatic: हाँ, लेकिन toStream को buffer.toStream – Arjan