Scala - 合并多个迭代器

Question

我有多个迭代器，根据一些排序标准以已排序的方式返回项目。现在，我想将这些迭代器合并为一个组合迭代器（多路复用）。我知道如何使用 Java 风格实现，例如使用 tree-map，但我想知道是否有更多函数式的方法？ 我希望尽可能保留这些迭代器的惰性特性。

- Bober02

---

可能是如何在Scala中组合2个迭代器？的重复问题。 - om-nom-nom

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
}

但并不一定更快，您应该进行微基准测试。

一个可能的替代方案是使用缓冲迭代器来达到相同的效果。

- axel22

---

好的，我如何确保相对顺序按照相同的排序标准保持不变呢？假设我有一个对象，其时间戳以DateTime的形式存在。我想要这两个迭代器根据时间戳合并，而不是一个接一个（在Java中，我会使用比较器）。 - Bober02

谢谢，但我绝对不想使用流，因为它们会缓存元素。此外，我能否在实际元素上提供排序，例如像Java Comparator那样，可以将其作为参数传递给集合？ - Bober02

流的内存占用复杂度和渐进运行时间复杂度与视图和迭代器相同，但是在内存占用复杂度方面存在异议。 - Bober02

有什么想法可以将其功能性地扩展到N个迭代器？ - Bober02

虽然可能不是特别高效，但您可以使用 mergeStreams 方法进行折叠。不过，使用自定义的 Iterator 实现可能会更加高效。 - axel22

Answer 2

就像@axel22提到的那样，您可以使用BufferedIterators来完成此操作。以下是一种不需要Stream的解决方案：

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!")
    }
}

- sralmai

Answer 3

您可以尝试以下方法：

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

例如：

val i1 = (1 to 100 by 3).toIterator
val i2 = (2 to 100 by 3).toIterator
val i3 = (3 to 100 by 3).toIterator

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

merged.next  // 结果为：1
merged.next  // 结果为：2
merged.next  // 结果为：3

- Keith Pinson

---

抱歉，我的错。我看到你不想使用流。 - Keith Pinson