Scala: Yinelemeli bir yinelenebilir duruma dönüşebilir bir grup oluşturun

Question

Parçalara ayırmak istediğim çok büyük yineleyiciler var. Yeni bir parçanın başlangıcıysa, bir öğeye bakıp doğru olan bir yüklemem var. Yineleyici olacak parçalara ihtiyacım var, çünkü parçalar bile belleğe sığmayacak. Yığını dışarı üfleyen özyinelemeli bir çözümden kaçınacağım kadar çok parça var. Durum this question'a benzer, ancak Listeler yerine yineleyicilere ihtiyacım var ve bir parçanın başında "sentinel" (yüklemin doğru olduğu öğeler) meydana gelir (ve dahil edilmeli). Sonuçta meydana gelen yineleyiciler sadece sırayla kullanılır, ancak bazıları hiç kullanılmayabilir ve sadece O (1) belleğini kullanmalıdır. Bunun hepsinin aynı temel yineleyiciyi paylaşması gerektiği anlamına geldiğini hayal ediyorum. Performans önemlidir. Ben bir işlev imza bir bıçak almak için olsaydı

, bu şöyle olacaktır:

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

Ben takeWhile kullanmak isterdim ama son elemanını kaybeder. span'u araştırdım, ancak arabellek sonuçları. Şu anki en iyi fikrim BufferedIterator içeriyor ama belki daha iyi bir yol var.

Sen böyle bir şey senin JVM çökmez doğru çünkü var bileceksiniz:

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

İşte benim çözümüm BufferedIterator kullanarak. Yineleyicileri doğru şekilde atlamanıza izin vermez, ancak oldukça basit ve işlevseldir. İlk eleman (lar) !startsGroup(first) olsa bile bir gruba gider.

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() 
    } 
    } 

Güncelleme:

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

Sen doğal bir sorun var. Iterable, birden çok yineleyici alabileceğiniz anlamına gelir. Iterator, yalnızca bir kez geçebileceğinizi gösterir. Bu, Iterable[Iterable[T]] ürününüzün Iterator[Iterable[T]] s ürününü üretebilmesi anlamına gelir. Ancak bu, bir öğeyi döndürdüğünde - Iterable[T] - ve birden çok yineleyici sorduğunda, temeldeki tek yineleyici, listenin sonuçlarını (çok büyük) önbelleğe almaksızın (çok büyük) veya orijinal yinelenen çağrılır ve kesinlikle geçer Yine her şey (çok verimsiz). Eğer olabilir bunu yaparken

yani, ben farklı bir şekilde sorunun gebe gerektiğini düşünüyorum.

Bunun yerine Seq ile başlayabilirseniz, alt kümeleri aralıklar olarak alabilirsiniz.

zaten size iterable kullanmak istediğiniz biliyorsanız

, bir "gerçek" kapalı her seferinde işleyicileri kümesi içinden starts yangınları artırır bir yöntem

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

yazabiliriz. İşleminizi tek bir taramada yapabileceğiniz herhangi bir yol varsa, bunun gibi bir şey gitmek. (İşleyicileriniz değişebilir veri yapıları veya değişkenler aracılığıyla durumu kaydetmelidirler.)

İç listeyi kırmak için dış listeden yinelemeye izin verebiliyorsanız, yinelediğinizde ek sınırlama olan bir Iterable[Iterator[T]] olabilir. Daha sonraki bir alt yineleyiciye, önceki tüm alt yineleyiciler geçersizdir.

---

İşte geçen türde bir çözüm (Iterator[T]Iterator[Iterator[T]] ila, biri dış katmanlarını Iterable yerine yapmak için bu sarabilirsiniz).

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

Bellek kısıtlamalarına bakıyorsanız, aşağıdakiler çalışacaktır. Yalnızca temeldeki yinelenen nesnenin görünümleri desteklemesi durumunda kullanabilirsiniz.Bu uygulama, yinelenen üzerinde yinelenecek ve daha sonra yinelenen IterableViews üretecektir. Bu uygulama, ilk elemanın bir başlangıç ​​grubu olarak test edip etmediği umurunda değildir, çünkü bu durumun önemi yoktur.

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

Sen Akışları kullanarak düşük bellek ayak izi koruyabilirsiniz: Biraz Durumun saklanması Eğer yineleyicinızı atlayıp öncekilerden ile karıştırmasını engellemek sağlar. Bir yineleyici tekrar ederseniz, result.toIterator kullanın.

Akımlar ile, değişebilir bir durum yoktur, sadece tek bir koşulludur ve neredeyse Jay Hacker'in çözümü kadar kısadır. Taşması Stack için yapıştırmak için çok fazla

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

ikinci test baskılar:

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() 
    } 

Ben testler yaptık.

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 
    } 
}