Vòng lặp thực hiện nối

Question

Chỉ cần dưới đây, mã của ++ phương pháp 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() } 
     } 

Trong bình luận, nó nói: // optimize a little bit to prevent n log n behavior..

Khi nào và cách ghép nối hai trình vòng lặp dẫn đến n log n?

Answer 1

Nhu cầu phổ biến, tôi trả lời cho câu hỏi của riêng tôi, trích dẫn nhận xét @Paolo Falabella ngay trên:

Nó đề cập trong "Lập trình trong Scala ed 2.". Nhật ký n là do thêm hướng dẫn được giới thiệu bằng cách quyết định ở mỗi bước của lặp lại nếu phần tử tiếp theo đến từ trình lặp đầu tiên hoặc trình lặp thứ hai thứ hai.