通过谓词拆分迭代器

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 = ("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原始. 那么就没有必要了。dropWhileitervar

我认为你原来的堆栈溢出的原因是重复调用span创建了一长串Iterators ，其中每个hasNext方法都调用hasNext其parent 的Iterator。如果您查看 的源代码Iterator，您可以看到每个都span创建了新的迭代器，将调用转发到hasNext原始迭代器（通过 a BufferedIterator，这进一步增加了调用堆栈）。

查阅文档后更新似乎，虽然我上面的解决方案似乎有效，但不推荐 - 特别参见：

特别重要的是要注意，除非另有说明，否则永远不要在调用迭代器的方法后使用迭代器。[...] 使用旧迭代器是未定义的，可能会发生变化，并且也可能导致新迭代器发生变化。

适用于takeWhileand dropWhile(and span)，但不适用于nextor 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)