按谓词拆分迭代器

Question

我需要一种可以将Iterator[Char]拆分为行的方法(用n和r分隔(

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

这是我的实现：

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 = ("aaaaaaaaabbbbbbbbbbbcccccccccccccrn" * 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 行是来自span的第二个迭代器的hasNext，第 651 行是来自 dropWhile 的迭代器中的hasNext

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

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(因此您需要在每次调用 next 时替换 iter(，只需在原始iter上使用 takeWhile 和 dropWhile 即可。 那么就不需要var了.

我认为您原始堆栈溢出的原因是重复调用span会创建一个长链Iterator，每个hasNext方法都调用其父Iterator的hasNext。如果您查看 Iterator 的源代码，您可以看到每个span都会创建新的迭代器，这些迭代器将调用转发给hasNext原始迭代器(通过 BufferedIterator，这进一步增加了调用堆栈(。

更新 查阅文档后，似乎尽管我上面的解决方案似乎有效，但不建议这样做 - 特别请参阅：

特别重要的是要指出，除非另有说明， 在调用迭代器的方法后，永远不应该使用迭代器。 [...]使用旧迭代器是未定义的，可能会发生变化，并且还可能导致新迭代器的更改。

这适用于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)