下面是Iterator
的++
方法的代码:
/** 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() }
}
在注释中,它说://优化一点以防止 n log n 行为。
。
何时以及如何连接两个迭代器导致 n log n ?
最佳答案
应大家的要求,我回答我自己的问题,引用上面@Paolo Falabella 的评论:
It's mentioned in "Programming in Scala 2nd ed.". The log n is due to the extra indirection introduced by having to decide at each step of the iteration if the next element comes from the first or the second iterator.
关于performance - 迭代器连接性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14126819/