ट्रैवर्सबल => जावा इटरेटर

Question

मेरे पास एक ट्रैवर्सबल है, और मैं इसे जावा इटरेटर में बनाना चाहता हूं। मेरी समस्या यह है कि मैं सबकुछ आलसी होना चाहता हूं। यदि मैं करता हूं। ट्रैवर्सबल पर इटरेटर, यह उत्सुकता से परिणाम उत्पन्न करता है, इसे एक सूची में कॉपी करता है, और सूची में एक इटरेटर देता है।

मुझे यकीन है कि मैं कुछ यहाँ सरल याद कर रहा हूँ हूँ ...

यहाँ एक छोटे से परीक्षण मामले से पता चलता है कि मैं क्या मतलब है:

class Test extends Traversable[String] { 
     def foreach[U](f : (String) => U) { 
     f("1") 
     f("2") 
     f("3") 
     throw new RuntimeException("Not lazy!") 
    } 
} 

val a = new Test 
val iter = a.toIterator 

Answer 1

मैं run into this problem before है और मैं के रूप में जहाँ तक बता सकते हैं, Iterator प्राप्त करने में कोई भी विशेष रूप से दिलचस्पी नहीं लेता है जब आपने परिभाषित किया है foreach।

लेकिन जैसे कि आपने ध्यान दिया, toStream समस्या है, तो आप सिर्फ इतना है कि रद्द कर सकते थे:

class Test extends Traversable[String] { 
    def foreach[U](f: (String) => U) { 
    f("1") 
    f("2") 
    f("3") 
    throw new RuntimeException("Not lazy!") 
    } 
    override def toStream: Stream[String] = { 
    "1" #:: 
    "2" #:: 
    "3" #:: 
    Stream[String](throw new RuntimeException("Not lazy!")) 
    } 
} 

एक अन्य विकल्प एक Traversable के बजाय एक Iterable परिभाषित करने के लिए किया जाएगा, और फिर आप मिल चाहते हैं iterator विधि सीधे। क्या आप थोड़ा और बता सकते हैं कि आपके Traversable आपके असली उपयोग मामले में क्या कर रहा है?

Answer 2

कारण है कि आप आलसी रूप से एक ट्रैवर्सबल से इटेटरेटर नहीं प्राप्त कर सकते हैं यह है कि आप आंतरिक रूप से नहीं कर सकते हैं। ट्रैवर्सबल 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 मिलियन एक्सेस मिलती है। यह सामान्य कोड के लिए स्पष्ट रूप से एक भयानक विचार है।

तो आपके पास यह है। ट्रैवर्सबल सामान्य रूप से आलसी नहीं है, और प्रदर्शन को समझौता किए बिना आलसी बनाने का कोई अच्छा तरीका नहीं है।