Scala - объединение нескольких итераторов

У меня есть несколько итераторов, которые возвращают элементы отсортированным образом в соответствии с некоторым критерием сортировки. Теперь я хотел бы объединить (мультиплексировать) итераторы в один комбинированный итератор. Я знаю, как это сделать в стиле Java, например, tree-map, но мне было интересно, есть ли более функциональный подход? Я хочу как можно больше сохранить лень итераторов.

Ответ 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
}

Не обязательно быстрее, но вы должны микропредпечатать это.

Возможной альтернативой является использование буферизованных итераторов для достижения того же эффекта.

Ответ 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!")
    }
}

Ответ 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  // results in: 1
merged.next  // results in: 2
merged.next  // results in: 3