Iteratory wydajność konkatenacji

Question

Tuż poniżej, kod ++ metody Iterator „s:

/** Concatenates this iterator with another. 
     * 
     * @param that the other iterator 
     * @return a new iterator that first yields the values produced by this 
     * iterator followed by the values produced by iterator `that`. 
     * @note Reuse: $consumesTwoAndProducesOneIterator 
     * @usecase def ++(that: => Iterator[A]): Iterator[A] 
     */ 
     def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = new Iterator[B] { 
     // optimize a little bit to prevent n log n behavior. 
     private var cur : Iterator[B] = self 
     // since that is by-name, make sure it's only referenced once - 
     // if "val it = that" is inside the block, then hasNext on an empty 
     // iterator will continually reevaluate it. (ticket #3269) 
     lazy val it = that.toIterator 
     // the eq check is to avoid an infinite loop on "x ++ x" 
     def hasNext = cur.hasNext || ((cur eq self) && { 
      it.hasNext && { 
      cur = it 
      true 
      } 
     }) 
     def next() = { hasNext; cur.next() } 
     } 

W komentarzu, to mówi: // optimize a little bit to prevent n log n behavior..

Kiedy i w jaki sposób łączenie dwóch iteratorów prowadzi do n log n?

Answer 1

Przez popularne popytu, mogę odpowiedzieć na moje własne pytanie, powołując się na komentarz @Paolo Falabella tuż powyżej:

Jest wymienione w „Programowanie w Scala 2nd ed.”. Dziennik n jest spowodowany przez dodatkowy kierunek pośredni wprowadzony przez konieczność decydowania na każdym etapie iteracji, jeśli następny element pochodzi z pierwszego lub drugiego iteratora .