Scala - 合并多个迭代器

Question

我有多个迭代器，它们根据某种排序标准以排序的方式返回项目。现在，我想将迭代器合并(多路复用)为一个组合迭代器。我知道如何以 Java 风格做到这一点，例如 TreeMap ，但我想知道是否有更实用的方法？我想尽可能保留迭代器的惰性。

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
}

虽然不一定更快，但您应该对其进行微基准测试。

一个可能的替代方案是使用 buffered iterators达到同样的效果。