Scala:通过谓词将可迭代对象分组为可迭代对象的可迭代对象

Question

我有非常大的迭代器，我想将它们分成几部分。我有一个谓词，它查看一个项目，如果它是新作品的开始，则返回 true。我需要这些部分是迭代器，因为即使是这些部分也不适合内存。有太多的部分，我会担心递归解决方案会耗尽你的堆栈。情况类似this question ，但我需要迭代器而不是列表，并且“哨兵”(谓词为真的项目)出现(并且应该包括)在一个片段的开头。结果迭代器将仅按顺序使用，尽管有些可能根本不会使用，并且它们应该只使用 O(1) 内存。我想这意味着它们都应该共享相同的底层迭代器。性能很重要。

如果我要尝试一个函数签名，那就是:

def groupby[T](iter: Iterator[T])(startsGroup: T => Boolean): Iterator[Iterator[T]] = ...

我很想使用 takeWhile ，但它丢失了最后一个元素。我调查了 span ，但它会缓冲结果。我目前最好的想法是 BufferedIterator ，但也许有更好的方法。

你会知道你做对了，因为这样的事情不会让你的 JVM 崩溃:

groupby((1 to Int.MaxValue).iterator)(_ % (Int.MaxValue / 2) == 0).foreach(group => println(group.sum))
groupby((1 to Int.MaxValue).iterator)(_ % 10 == 0).foreach(group => println(group.sum))

Answer 1

你有一个固有的问题。 Iterable意味着您可以获得多个迭代器。 Iterator意味着你只能通过一次。这意味着您的 Iterable[Iterable[T]]应该可以生产Iterator[Iterable[T]] s。但是当它返回一个元素时——an Iterable[T] -- 这要求多个迭代器，底层的单个迭代器不能在不缓存列表的结果(太大)或调用原始迭代器并再次遍历所有内容(非常低效)的情况下遵守。

所以，虽然你可以这样做，但我认为你应该以不同的方式来看待你的问题。

如果您可以从 Seq 开始相反，您可以获取子集作为范围。

如果您已经知道如何使用可迭代对象，则可以编写一个方法

def process[T](source: Iterable[T])(starts: T => Boolean)(handlers: T => Unit *)

每次递增处理程序集 starts触发“真实”。如果有任何方法可以一次完成处理，那么这样的方法就是要走的路。 (但是，您的处理程序必须通过可变数据结构或变量来保存状态。)

如果您可以允许外部列表上的迭代破坏内部列表，则可以使用 Iterable[Iterator[T]]附加的约束是，一旦您迭代到后面的子迭代器，所有以前的子迭代器都无效。

这是最后一种类型的解决方案(从 Iterator[T] 到 Iterator[Iterator[T]] ；可以将其包裹起来以制作外层 Iterable )。

class GroupedBy[T](source: Iterator[T])(starts: T => Boolean)
extends Iterator[Iterator[T]] {
  private val underlying = source
  private var saved: T = _
  private var cached = false
  private var starting = false
  private def cacheNext() {
    saved = underlying.next
    starting = starts(saved)
    cached = true
  }
  private def oops() { throw new java.util.NoSuchElementException("empty iterator") }
  // Comment the next line if you do NOT want the first element to always start a group
  if (underlying.hasNext) { cacheNext(); starting = true }
  def hasNext = {
    while (!(cached && starting) && underlying.hasNext) cacheNext()
    cached && starting
  }
  def next = {
    if (!(cached && starting) && !hasNext) oops()
    starting = false
    new Iterator[T] {
      var presumablyMore = true
      def hasNext = {
        if (!cached && !starting && underlying.hasNext && presumablyMore) cacheNext()
        presumablyMore = cached && !starting
        presumablyMore
      }
      def next = {
        if (presumablyMore && (cached || hasNext)) { 
          cached = false
          saved
        }
        else oops()
      }
    }
  }
}