performance - 迭代器连接性能

Question

下面是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() }
      }

在评论中，它说：// optimize a little bit to prevent n log n behavior.。

连接两个迭代器何时以及如何导致 n log n ？

Answer 1

根据大众的需求，我引用上面的@Paolo Falabella 评论来回答我自己的问题：

它在“Scala 编程第二版”中提到。log n 是由于必须在迭代的每个步骤中决定下一个元素来自第一个迭代器还是第二个迭代器而引入的额外间接性。