scala - 通过谓词拆分迭代器

Question

我需要一个可以拆分的方法 Iterator[Char]成行(由 \n 和 \r 分隔)

为此，我编写了一个通用方法，它获取一个迭代器和一个谓词，并在每次谓词为真时拆分迭代器。
这类似于 span ，但每次谓词为真时都会 split ，不仅仅是第一次

这是我的实现:

def iterativeSplit[T](iterO: Iterator[T])(breakOn: T => Boolean): Iterator[List[T]] = 
 new Iterator[List[T]] {
  private var iter = iterO
  def hasNext = iter.hasNext

  def next = {
    val (i1,i2) = iter.span(el => !breakOn(el))
    val cur = i1.toList
    iter = i2.dropWhile(breakOn)
    cur
  }
}.withFilter(l => l.nonEmpty)

它在小输入上运行良好，但在大输入上运行非常慢，有时我会遇到堆栈溢出异常

这是重新创建问题的代码:

val iter = ("aaaaaaaaabbbbbbbbbbbccccccccccccc\r\n" * 10000).iterator
iterativeSplit(iter)(c => c == '\r' || c == '\n').length

运行期间的堆栈跟踪是:

... 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847)
at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:615)
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847)
at scala.collection.Iterator$$anon$18.hasNext(Iterator.scala:591)
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847)
at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:615)
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847)
at scala.collection.Iterator$$anon$18.hasNext(Iterator.scala:591)
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847)
at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:615)
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847)
at scala.collection.Iterator$$anon$18.hasNext(Iterator.scala:591)
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847)
...

查看源代码(我使用的是 Scala 2.10.4)
第 591 行是 hasNext来自 span 的第二个迭代器，第 651 行是 hasNext在来自 dropWhile 的迭代器中

我想我错误地使用了这两个迭代器，但我不明白为什么

Answer 1

您可以按如下方式简化代码，这似乎可以解决问题:

  def iterativeSplit2[T](iter: Iterator[T])(breakOn: T => Boolean): Iterator[List[T]] =
    new Iterator[List[T]] {
      def hasNext = iter.hasNext

      def next = {
        val cur = iter.takeWhile(!breakOn(_)).toList
        iter.dropWhile(breakOn)
        cur
      }
    }.withFilter(l => l.nonEmpty)   

而不是使用 span (因此您需要在每次调用 iter 时替换 next )，只需使用 takeWhile和 dropWhile上原 iter .那么就不需要 var .

我认为您原来堆栈溢出的原因是反复调用 span创建一个长链 Iterator s，每个 hasNext方法调用 hasNext其父 Iterator .如果你看 source code为 Iterator ，可以看到每个 span创建新的迭代器将调用转发到 hasNext到原始迭代器(通过 BufferedIterator ，这进一步增加了调用堆栈)。

更新 已咨询 documentation看来，虽然我上面的解决方案似乎有效，但不建议这样做 - 特别是:

It is of particular importance to note that, unless stated otherwise, one should never use an iterator after calling a method on it. [...] Using the old iterator is undefined, subject to change, and may result in changes to the new iterator as well.

适用于 takeWhile和 dropWhile (和 span )，但不是 next或 hasNext .

可以使用 span与您的原始解决方案一样，但使用流而不是迭代器和递归:

  def split3[T](s: Stream[T])(breakOn: T => Boolean): Stream[List[T]] = s match {
    case Stream.Empty => Stream.empty
    case s => {
      val (a, b) = s.span(!breakOn(_))
      a.toList #:: split3(b.dropWhile(breakOn))(breakOn)
    }
  }

但是性能实在是太差了。我相信一定有更好的方法......

更新 2:这是一个非常重要的解决方案，具有更好的性能:

import scala.collection.mutable.ListBuffer

  def iterativeSplit4[T](iter: Iterator[T])(breakOn: T => Boolean): Iterator[List[T]] =
    new Iterator[List[T]] {
      val word = new ListBuffer[T]
      def hasNext() = iter.hasNext

      def next = {
        var looking = true
        while (looking) {
          val c = iter.next
          if (breakOn(c)) looking = false
          else word += c
        }
        val w = word.toList
        word.clear()
        w
      }
    }.withFilter(_.nonEmpty)