scala - Scala - 合并多个迭代器

Question

我有多个迭代器，它们根据某些排序标准以排序方式返回项目。现在，我想将迭代器合并（多路复用）为一个组合迭代器。我知道如何以 Java 风格进行操作，例如树形图，但我想知道是否有更实用的方法？我想尽可能地保持迭代器的惰性。

Answer 1

你可以这样做：

val it = iter1 ++ iter2

它创建另一个迭代器并且不评估元素，但包装两个现有的迭代器。它是完全懒惰的，所以你不应该使用iter1或者iter2一旦你这样做了。

一般来说，如果你有更多的迭代器要合并，你可以使用折叠：

val iterators: Seq[Iterator[T]] = ???
val it = iterators.foldLeft(Iterator[T]())(_ ++ _)

如果您对想要在生成的迭代器中维护的元素进行了一些排序，但又想要惰性，则可以将它们转换为流：

def merge[T: Ordering](iter1: Iterator[T], iter2: Iterator[T]): Iterator[T] = {
  val s1 = iter1.toStream
  val s2 = iter2.toStream

  def mergeStreams(s1: Stream[T], s2: Stream[T]): Stream[T] = {
    if (s1.isEmpty) s2
    else if (s2.isEmpty) s1
    else if (s1.head < s2.head) s1.head #:: mergeStreams(s1.tail, s2)
    else s2.head #:: mergeStreams(s1, s2.tail)
  }

  mergeStreams(s1, s2).iterator
}

不过不一定更快，您应该对此进行微基准测试。

一种可能的替代方法是使用缓冲迭代器来实现相同的效果。

Answer 2

就像提到的@axel22 一样，您可以使用 BufferedIterators 来做到这一点。这是一个无流的解决方案：

def combine[T](rawIterators: List[Iterator[T]])(implicit cmp: Ordering[T]): Iterator[T] = {
  new Iterator[T] {
    private val iterators: List[BufferedIterator[T]] = rawIterators.map(_.buffered)

    def hasNext: Boolean = iterators.exists(_.hasNext)

    def next(): T = if (hasNext) {
      iterators.filter(_.hasNext).map(x => (x.head, x)).minBy(_._1)(cmp)._2.next()
    } else {
      throw new UnsupportedOperationException("Cannot call next on an exhausted iterator!")
    }
}

Answer 3

你可以试试：

(iterA ++ iterB).toStream.sorted.toIterator

例如：

val i1 = (1 到 100 乘 3).toIterator
val i2 = (2 到 100 乘 3).toIterator
val i3 = (3 到 100 乘 3).toIterator

val 合并 = (i1 ++ i2 ++ i3).toStream.sorted.toIterator

merge.next // 结果：1
merge.next // 结果：2
merge.next // 结果：3