9

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.。

2 つの反復子を連結すると、いつ、どのように n log n になりますか?

4

1 に答える 1

2

一般的な要望により、私は自分の質問に答え、すぐ上の @Paolo Falabella のコメントを引用します。

「Programming in Scala 2nd ed.」で言及されています。log n は、反復の各ステップで、次の要素が最初の反復子から来るのか 2 番目の反復子から来るのかを決定しなければならないことによって導入された余分な間接性によるものです。

于 2013-03-25T09:42:40.170 に答える