स्कैला:

Question

द्वारा एक इटरटेबल Iterables में एक Iterable समूह I मेरे पास बहुत बड़े Iterators हैं जिन्हें मैं टुकड़ों में विभाजित करना चाहता हूं। मेरे पास एक अनुमान है जो एक आइटम को देखता है और यदि यह एक नए टुकड़े की शुरुआत है तो सच हो जाता है। मुझे टुकड़े टुकड़े करने की जरूरत है, क्योंकि टुकड़े भी स्मृति में फिट नहीं होंगे। इतने सारे टुकड़े हैं कि मैं आपके स्टैक को उड़ाते हुए एक पुनरावर्ती समाधान से सावधान रहूंगा। स्थिति this question के समान है, लेकिन मुझे सूची के बजाय इटरेटर की आवश्यकता है, और "सेंटीनेल" (जिन वस्तुओं के लिए भविष्य सत्य है) एक टुकड़े की शुरुआत में होते हैं (और शामिल किए जाने चाहिए)। परिणामी इटरेटर्स का उपयोग केवल क्रम में किया जाएगा, हालांकि कुछ का उपयोग नहीं किया जा सकता है, और उन्हें केवल ओ (1) मेमोरी का उपयोग करना चाहिए। मुझे कल्पना है कि इसका मतलब है कि उन्हें सभी एक ही अंतर्निहित पुनरावर्तक साझा करना चाहिए। प्रदर्शन महत्वपूर्ण है।

अगर मैं एक समारोह हस्ताक्षर पर एक वार तय लग रही थी, यह इस होगा:

def groupby[T](iter: Iterator[T])(startsGroup: T => Boolean): Iterator[Iterator[T]] = ... 

मैं takeWhile उपयोग करने के लिए प्यार किया है होगा, लेकिन यह पिछले तत्व खो देता है। मैंने span की जांच की, लेकिन यह परिणाम बफर करता है। मेरे वर्तमान सर्वोत्तम विचार में BufferedIterator शामिल है, लेकिन शायद एक बेहतर तरीका है।

आपको पता चल जाएगा कि आप इसे मिल गया है सही है क्योंकि कुछ इस तरह अपने JVM दुर्घटना नहीं करता है:

groupby((1 to Int.MaxValue).iterator)(_ % (Int.MaxValue/2) == 0).foreach(group => println(group.sum)) 
groupby((1 to Int.MaxValue).iterator)(_ % 10 == 0).foreach(group => println(group.sum)) 

Answer 1

यहाँ मेरी समाधान BufferedIterator का उपयोग कर रहा है। यह आपको इटरेटर को सही ढंग से छोड़ने नहीं देता है, लेकिन यह काफी सरल और कार्यात्मक है। पहला तत्व समूह में जाता है भले ही !startsGroup(first)।

def groupby[T](iter: Iterator[T])(startsGroup: T => Boolean): Iterator[Iterator[T]] = 
    new Iterator[Iterator[T]] { 
    val base = iter.buffered 
    override def hasNext = base.hasNext 
    override def next() = Iterator(base.next()) ++ new Iterator[T] { 
     override def hasNext = base.hasNext && !startsGroup(base.head) 
     override def next() = if (hasNext) base.next() else Iterator.empty.next() 
    } 
    } 

अद्यतन:

def groupby[T](iter: Iterator[T])(startsGroup: T => Boolean): Iterator[Iterator[T]] = 
new Iterator[Iterator[T]] { 
    val base = iter.buffered 
    var prev: Iterator[T] = Iterator.empty 
    override def hasNext = base.hasNext 
    override def next() = { 
    while (prev.hasNext) prev.next()  // Exhaust previous iterator; take* and drop* do NOT always work!! (Jira SI-5002?) 
    prev = Iterator(base.next()) ++ new Iterator[T] { 
     var hasMore = true 
     override def hasNext = { hasMore = hasMore && base.hasNext && !startsGroup(base.head) ; hasMore } 
     override def next() = if (hasNext) base.next() else Iterator.empty.next() 
    } 
    prev 
    } 
} 

Answer 2

आप एक अंतर्निहित समस्या है। Iterable का तात्पर्य है कि आप एकाधिक इटरेटर प्राप्त कर सकते हैं। Iterator का तात्पर्य है कि आप केवल एक बार गुजर सकते हैं। इसका मतलब है कि आपका Iterable[Iterable[T]]Iterator[Iterable[T]] एस बनाने में सक्षम होना चाहिए। लेकिन जब यह एक तत्व देता है - एक Iterable[T] - और जो एकाधिक इटरेटर के लिए पूछता है, अंतर्निहित सिंगल इटरेटर सूची के परिणामों को कैश करने के बिना अनुपालन नहीं कर सकता है (बहुत बड़ा) या मूल पुनरावर्तक को कॉल करना और पूरी तरह से जा रहा है सबकुछ फिर से (बहुत अक्षम)।

तो, जबकि आप ऐसा कर सकते हैं, मुझे लगता है कि आपको अपनी समस्या का एक अलग तरीके से गर्भ धारण करना चाहिए।

यदि आप इसके बजाय Seq से शुरू कर सकते हैं, तो आप श्रेणियों के रूप में सबसेट ले सकते हैं।

आप पहले से ही जानते हैं कि कैसे आप अपने iterable का उपयोग करना चाहते हैं, तो आप एक विधि

def process[T](source: Iterable[T])(starts: T => Boolean)(handlers: T => Unit *) 

जो संचालकों के सेट के माध्यम से बंद "सही" हर बार starts आग की वृद्धि कर लिख सकते हैं। यदि कोई तरीका है कि आप एक स्वीप में अपनी प्रसंस्करण कर सकते हैं, तो ऐसा कुछ तरीका है। (आपके हैंडलर को म्यूटेबल डेटा संरचनाओं या चर के माध्यम से राज्य को सहेजना होगा।)

यदि आप आंतरिक सूची को तोड़ने के लिए बाहरी सूची पर पुनरावृत्ति की अनुमति दे सकते हैं, तो आपके पास अतिरिक्त बाधा के साथ Iterable[Iterator[T]] हो सकता है जिसे एक बार फिर से चालू किया जाए बाद में उप-पुनरावर्तक के लिए, पिछले सभी उप-पुनरावर्तक अमान्य हैं।

---

यहाँ पिछले प्रकार का एक समाधान है (जैसे Iterator[T]Iterator[Iterator[T]] करने के लिए; एक इस लपेट बाहरी परत Iterable बजाय बनाने के लिए कर सकते हैं)।

class GroupedBy[T](source: Iterator[T])(starts: T => Boolean) 
extends Iterator[Iterator[T]] { 
    private val underlying = source 
    private var saved: T = _ 
    private var cached = false 
    private var starting = false 
    private def cacheNext() { 
    saved = underlying.next 
    starting = starts(saved) 
    cached = true 
    } 
    private def oops() { throw new java.util.NoSuchElementException("empty iterator") } 
    // Comment the next line if you do NOT want the first element to always start a group 
    if (underlying.hasNext) { cacheNext(); starting = true } 
    def hasNext = { 
    while (!(cached && starting) && underlying.hasNext) cacheNext() 
    cached && starting 
    } 
    def next = { 
    if (!(cached && starting) && !hasNext) oops() 
    starting = false 
    new Iterator[T] { 
     var presumablyMore = true 
     def hasNext = { 
     if (!cached && !starting && underlying.hasNext && presumablyMore) cacheNext() 
     presumablyMore = cached && !starting 
     presumablyMore 
     } 
     def next = { 
     if (presumablyMore && (cached || hasNext)) { 
      cached = false 
      saved 
     } 
     else oops() 
     } 
    } 
    } 
} 

Answer 3

यदि आप स्मृति बाधाओं को देख रहे हैं तो निम्नलिखित कार्य करेंगे। यदि आप अंतर्निहित पुनरावर्तनीय वस्तु दृश्यों का समर्थन करते हैं तो आप इसका उपयोग केवल तभी कर सकते हैं।यह कार्यान्वयन Iterable पर फिर से शुरू होगा और उसके बाद IterableViews उत्पन्न करेगा जिसे फिर से चालू किया जा सकता है। यह कार्यान्वयन परवाह नहीं करता है अगर प्रारंभिक समूह के रूप में पहला तत्व परीक्षण करता है क्योंकि यह परवाह किए बिना होगा।

def groupby[T](iter: Iterable[T])(startsGroup: T => Boolean): Iterable[Iterable[T]] = new Iterable[Iterable[T]] { 
    def iterator = new Iterator[Iterable[T]] { 
    val i = iter.iterator 
    var index = 0 
    var nextView: IterableView[T, Iterable[T]] = getNextView() 
    private def getNextView() = { 
     val start = index 
     var hitStartGroup = false 
     while (i.hasNext && ! hitStartGroup) { 
     val next = i.next() 
     index += 1 
     hitStartGroup = (index > 1 && startsGroup(next)) 
     } 
     if (hitStartGroup) { 
     if (start == 0) iter.view(start, index - 1) 
     else iter.view(start - 1, index - 1) 
     } else { // hit end 
     if (start == index) null 
     else if (start == 0) iter.view(start, index) 
     else iter.view(start - 1, index) 
     } 
    } 
    def hasNext = nextView != null 
    def next() = { 
     if (nextView != null) { 
     val next = nextView 
     nextView = getNextView() 
     next 
     } else null 
    } 
    } 
} 

Answer 4

आपको स्ट्रीम का उपयोग करके कम स्मृति फुट प्रिंट को बनाए रखने कर सकते हैं: एक छोटे से राज्य में रखते हुए आप iterators छोड़ सकते हैं और पिछले लोगों के साथ खिलवाड़ करने से लोगों को रोक सकते हैं। परिणाम का उपयोग करें। इटरेटर, अगर आप फिर से एक पुनरावर्तक।

धाराओं के साथ, कोई परिवर्तनीय स्थिति नहीं है, केवल एक सशर्त है और यह जे हैकर के समाधान के रूप में संक्षिप्त है।

scala> batchBy((1 to Int.MaxValue).iterator)(_ % (Int.MaxValue/2) == 0) 
     .foreach{case(_,group) => println(group.sum)} 
-1610612735 
1073741823 
-536870909 
2147483646 
2147483647 

दूसरे टेस्ट प्रिंट ओवरफ्लो स्टैक को चिपकाने के लिए बहुत ज्यादा:

def batchBy[A,B](iter: Iterator[A])(f: A => B): Stream[(B, Iterator[A])] = { 
    val base = iter.buffered 
    val empty = Stream.empty[(B, Iterator[A])] 

    def getBatch(key: B) = { 
     Iterator(base.next()) ++ new Iterator[A] { 
     def hasNext: Boolean = base.hasNext && (f(base.head) == key) 
     def next(): A = base.next() 
     } 
    } 

    def next(skipList: Option[Iterator[A]] = None): Stream[(B, Iterator[A])] = { 
     skipList.foreach{_.foreach{_=>}} 

     if (base.isEmpty) empty 
     else { 
     val key = f(base.head) 
     val batch = getBatch(key) 

     Stream.cons((key, batch), next(Some(batch))) 
     } 
    } 

    next() 
    } 

मैं परीक्षण भाग गया।

Answer 5

import scala.collection.mutable.ArrayBuffer 

object GroupingIterator { 

    /** 
    * Create a new GroupingIterator with a grouping predicate. 
    * 
    * @param it The original iterator 
    * @param p Predicate controlling the grouping 
    * @tparam A Type of elements iterated 
    * @return A new GroupingIterator 
    */ 
    def apply[A](it: Iterator[A])(p: (A, IndexedSeq[A]) => Boolean): GroupingIterator[A] = 
    new GroupingIterator(it)(p) 
} 

/** 
* Group elements in sequences of contiguous elements that satisfy a predicate. The predicate 
* tests each single potential next element of the group with the help of the elements grouped so far. 
* If it returns true, the potential next element is added to the group, otherwise 
* a new group is started with the potential next element as first element 
* 
* @param self The original iterator 
* @param p Predicate controlling the grouping 
* @tparam A Type of elements iterated 
*/ 
class GroupingIterator[+A](self: Iterator[A])(p: (A, IndexedSeq[A]) => Boolean) extends Iterator[IndexedSeq[A]] { 

    private[this] val source = self.buffered 
    private[this] val buffer: ArrayBuffer[A] = ArrayBuffer() 

    def hasNext: Boolean = source.hasNext 

    def next(): IndexedSeq[A] = { 
    if (hasNext) 
     nextGroup() 
    else 
     Iterator.empty.next() 
    } 

    private[this] def nextGroup(): IndexedSeq[A] = { 
    assert(source.hasNext) 

    buffer.clear() 
    buffer += source.next 

    while (source.hasNext && p(source.head, buffer)) { 
     buffer += source.next 
    } 

    buffer.toIndexedSeq 
    } 
}