迭代器连接性能

正下方，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() } 
     }

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

何时和如何连接两个迭代器会导致n log n？

来源

2013-01-02 Mik378

它在“Programming in Scala 2nd ed。”中提到。 log n是由于必须在迭代的每一步决定下一个元素是来自第一个还是第二个迭代器而引入的额外间接引入的。 –

如果检查哪个迭代器为空将一直执行，那么通过并置连接迭代器连接会产生错误的复杂性，这是通过将新值重新分配给'cur' – idonnie

非常感谢:)这非常明确。 – Mik378

应广大用户要求，我的回答是我自己的问题，引述@Paolo法拉贝拉评论略高于：

它在提到“斯卡拉第二版程序。”日志n是由于额外间接引入的，因为如果下一个元素来自迭代器的第一个或第二个迭代器，必须在迭代过程中决定每个步骤。

来源

2013-03-25 09:42:40 Mik378

迭代器连接性能

回答

相关问题