Verkettung von Iteratoren

Question

sah ich dieses Beispiel in „Programming in Scala“ Kapitel 24 „Sammlungen in der Tiefe“. Dieses Beispiel zeigt zwei alternative Möglichkeiten, um einen Baum zu implementieren:

1. von Traversable[Int] erstreckt - hier die Komplexität der def foreach[U](f: Int => U): Unit wäre O(N).

2. durch Erweitern Iterable[Int] - hier wäre die Komplexität def iterator: Iterator[Int] wäre O(N log(N)). Diese

ist es zu zeigen, warum es hilfreich wäre, zwei separate Züge zu haben, Traversable und Iterable.

sealed abstract class Tree 
    case class Branch(left: Tree, right: Tree) extends Tree 
    case class Node(elem: Int) extends Tree 

    sealed abstract class Tree extends Traversable[Int] { 
    def foreach[U](f: Int => U) = this match { 
    case Node(elem) => f(elem) 
    case Branch(l, r) => l foreach f; r foreach f 
    } 
    } 

    sealed abstract class Tree extends Iterable[Int] { 
    def iterator: Iterator[Int] = this match { 
     case Node(elem) => Iterator.single(elem) 
     case Branch(l, r) => l.iterator ++ r.iterator 
    } 
    } 

die Umsetzung foreach Bezug sie sagen:

ein ausgeglichener Baum nimmt im Baum proportional zur Anzahl der Elemente Zeit durchquert. Um dies zu sehen, der Ansicht, dass für einen ausgeglichenen Baum mit N Blätter werden Sie N - 1 inneren Knoten der Klasse Niederlassung haben. So die Gesamtzahl der Schritte, um den Baum zu durchlaufen ist N + N - 1.

, die Sinn macht. :)

jedoch erwähnen sie, dass die Verknüpfung der beiden Iteratoren im iterator Methode Zeitkomplexität von log(N) hat, so dass die Gesamtkomplexität des Verfahrens wäre N log(N):

Jedes Mal, wenn ein Element erzeugt wird, durch einen verketteten Iterator, wie zum Beispiel l.iterator ++ r.iterator, muss die Berechnung einer Indirektion folgen, um den richtigen Iterator zu erhalten (entweder l.iterator oder r.iterator). Alles in allem macht das log(N) Indirektionen zu einem Blatt eines ausgewogenen Baumes mit N Blättern. So sind die Kosten alle Elemente eines Baumes Besuch ging von etwa bis 2N für die foreach Traversal-Methode N log(N) für die Traversal mit iterator.

????

Warum wird die Berechnung des verketteten Iterator Bedarf an einem Blatt der linken oder rechten Iterator zu bekommen?

Answer 1

In dieser Implementierung weiß der oberste Zweig NICHT, wie viele Elemente es in seinen Unterzweigen left und right gibt.

Daher ist der Iterator rekursiv mit der Kluft gebaut und Ansatz erobern, die eindeutig in der iterator Methode dargestellt wird - erhalten Sie zu jedem Knoten (case Branch), erzeugen Sie den Iterator des einzelnen Knotens case Node => ... und dann Sie beitreten Sie.

Ohne in jeden einzelnen Knoten zu gelangen, würde er nicht wissen, welche Elemente dort sind und wie der Baum strukturiert ist (ungerade Zweige erlaubt, nicht erlaubt usw.).

EDIT: Werfen wir einen Blick in die ++ Methode auf Iterator.

def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = new Iterator.JoinIterator(self, that) 

und dann bei Iterator.JoinIterator

private[scala] final class JoinIterator[+A](lhs: Iterator[A], that: => GenTraversableOnce[A]) extends Iterator[A] { 
    private[this] var state = 0 // 0: lhs not checked, 1: lhs has next, 2: switched to rhs 
    private[this] lazy val rhs: Iterator[A] = that.toIterator 
    def hasNext = state match { 
     case 0 => 
     if (lhs.hasNext) { 
      state = 1 
      true 
     } else { 
      state = 2 
      rhs.hasNext 
     } 
     case 1 => true 
     case _ => rhs.hasNext 
    } 
    def next() = state match { 
     case 0 => 
     if (lhs.hasNext) lhs.next() 
     else { 
      state = 2 
      rhs.next() 
     } 
     case 1 => 
     state = 0 
     lhs.next() 
     case _ => 
     rhs.next() 
    } 

    override def ++[B >: A](that: => GenTraversableOnce[B]) = 
     new ConcatIterator(this, Vector(() => that.toIterator)) 
    } 

Von dass wir das Verbinden Iteratoren nur eine rekursive Struktur auf dem Gebiet rhs schafft sehen können. Konzentrieren wir uns darüber hinaus ein bisschen mehr. Betrachten wir eine noch Baum mit Struktur level1 [A]; level2 [B][C]; level 3[D][E][F][F]

Wenn Sie JoinIterator auf dem Iterator rufen Sie die vorhandene lhs Iterator bewahren. Sie haben jedoch immer .toIterator auf rhs. Das bedeutet, dass für jede nachfolgende Ebene der rhs Teil rekonstruiert wird. Also für B ++ C bekommst du das wie A.lhs (stands for B) und A.rhs (stands for C.toIterator) wo C.toIterator für C.lhs and C.rhs etc. steht. Also die zusätzliche Komplexität.

Ich hoffe, dies beantwortet Ihre Frage.

Answer 2

Das Wortspiel auf "Sammlungen in Tiefe" ist apt. Die Tiefe der Datenstruktur ist wichtig.

Wenn Sie top.iterator.next(), die jeweils innere Branch Delegierten der Iterator der Branch oder Node darunter, eine Verbindungskette aufrufen, die log(N) ist.

Diese Anrufkette entsteht bei jedem next().

Mit foreach, besuchen Sie nur einmal Branch oder Node.

Edit: Nicht sicher, ob dies hilft, aber hier ist ein Beispiel für eifrig die Blätter zu finden, aber faul produzieren die Werte. In älteren Versionen von Scala würde Stackoverflow auftreten oder langsamer sein, aber die Implementierung von Chained ++ wurde verbessert. Jetzt ist es eine flache Kette, die kürzer wird, wenn sie verbraucht wird.

sealed abstract class Tree extends Iterable[Int] { 
    def iterator: Iterator[Int] = { 
    def leafIterator(t: Tree): List[Iterator[Int]] = t match { 
     case Node(_) => t.iterator :: Nil 
     case Branch(left, right) => leafIterator(left) ::: leafIterator(right) 
    } 
    this match { 
     case n @ Node(_) => Iterator.fill(1)(n.value) 
     case Branch(left @ Node(_), right @ Node(_)) => left.iterator ++ right.iterator 
     case b @ Branch(_, _) => 
     leafIterator(b).foldLeft(Iterator[Int]())((all, it) => all ++ it) 
    } 
    } 
} 

case class Branch(left: Tree, right: Tree) extends Tree { 
    override def toString = s"Branch($left, $right)" 
} 
case class Node(elem: Int) extends Tree { 
    def value = { 
    Console println "An expensive leaf calculation" 
    elem 
    } 
    override def toString = s"Node($elem)" 
} 

object Test extends App { 
    // many leaves 
    val n = 1024 * 1024 
    val ns: List[Tree] = (1 to n).map(Node(_)).toList 
    var b = ns 
    while (b.size > 1) { 
    b = b.grouped(2).map { case left :: right :: Nil => Branch(left, right) }.toList 
    } 
    Console println s"Head: ${b.head.iterator.take(3).toList}" 
}