scala - Scala 中使用惰性求值或融合的迭代器？

Question

我听说迭代者很懒，但是他们到底有多懒呢？或者，是否可以将迭代器与后处理功能融合，从而不必构建中间数据结构？

例如，我可以在我的迭代器中构建一个 100 万个项目吗Stream[Option[String]] 来自 java.io.BufferedReader ，然后随后过滤掉 None s，以组合的方式，不需要将整个 Stream 保存在内存中？并且同时保证我不炸堆？或类似的东西 - 它不必使用 Stream .

我目前正在使用 Scalaz 6，但如果其他迭代实现能够以更好的方式做到这一点，我很想知道。

请提供完整的解决方案，包括关闭BufferedReader并调用 unsafePerformIO ，如果适用的话。

Answer 1

这是一个使用 Scalaz 7 库的快速迭代示例，演示了您感兴趣的属性:常量内存和堆栈使用。

问题

首先假设我们有一个大文本文件，每行都有一串十进制数字，我们想要找到所有至少包含 20 个零的行。我们可以像这样生成一些样本数据:

val w = new java.io.PrintWriter("numbers.txt")
val r = new scala.util.Random(0)

(1 to 1000000).foreach(_ =>
  w.println((1 to 100).map(_ => r.nextInt(10)).mkString)
)

w.close()

现在我们有了一个名为 numbers.txt 的文件。 .让我们用 BufferedReader 打开它:

val reader = new java.io.BufferedReader(new java.io.FileReader("numbers.txt"))

它不是太大(约 97 兆字节)，但足以让我们很容易地看到我们的内存使用是否在我们处理它时实际上保持不变。

设置我们的枚举器

首先是一些进口:

import scalaz._, Scalaz._, effect.IO, iteratee.{ Iteratee => I }

还有一个枚举器(请注意，为了方便起见，我将 IoExceptionOr s 更改为 Option s):

val enum = I.enumReader(reader).map(_.toOption)

Scalaz 7 当前不提供枚举文件行的好方法，因此我们一次将文件分 block 处理一个字符。这当然会非常缓慢，但我不会在这里担心，因为这个演示的目标是展示我们可以在恒定内存中处理这个大文件并且不会破坏堆栈。该答案的最后一部分提供了一种性能更好的方法，但在这里我们将仅在换行符处进行拆分:

val split = I.splitOn[Option[Char], List, IO](_.cata(_ != '\n', false))

如果事实是 splitOn需要一个谓词来指定不拆分的位置让您感到困惑，您并不孤单。 split是我们的第一个枚举示例。我们将继续将我们的枚举器包装在其中:

val lines = split.run(enum).map(_.sequence.map(_.mkString))

现在我们有了 Option[String] 的枚举数s 在 IO单子(monad)。

使用枚举对象过滤文件

接下来是我们的谓词——请记住，我们说过我们想要至少有 20 个零的行:

val pred = (_: String).count(_ == '0') >= 20

我们可以把它变成一个过滤枚举器并将我们的枚举器包装在其中:

val filtered = I.filter[Option[String], IO](_.cata(pred, true)).run(lines)

我们将设置一个简单的操作，仅打印通过此过滤器的所有内容:

val printAction = (I.putStrTo[Option[String]](System.out) &= filtered).run

当然，我们还没有真正读过任何东西。为此，我们使用 unsafePerformIO :

printAction.unsafePerformIO()

现在我们可以观看 Some("0946943140969200621607610...") s 慢慢滚动，而我们的内存使用量保持不变。它很慢，错误处理和输出有点笨拙，但我认为对于大约九行代码来说还不错。

从迭代器获取输出

那是 foreach -ish 用法。我们还可以创建一个更像折叠的迭代器——例如收集通过过滤器的元素并将它们返回到一个列表中。只需重复以上所有内容，直到 printAction定义，然后改写:

val gatherAction = (I.consume[Option[String], IO, List] &= filtered).run

启动该操作:

val xs: Option[List[String]] = gatherAction.unsafePerformIO().sequence

现在去喝杯咖啡(可能需要离得很远)。当你回来时，你要么有一个 None (如果是 IOException 沿途某处)或 Some包含 1,943 个字符串的列表。

自动关闭文件的完整(更快)示例

为了回答您关于关闭阅读器的问题，这里有一个完整的工作示例，大致相当于上面的第二个程序，但有一个负责打开和关闭阅读器的枚举器。它也快得多，因为它读取的是行，而不是字符。首先是导入和几个辅助方法:

import java.io.{ BufferedReader, File, FileReader }
import scalaz._, Scalaz._, effect._, iteratee.{ Iteratee => I, _ }

def tryIO[A, B](action: IO[B]) = I.iterateeT[A, IO, Either[Throwable, B]](
  action.catchLeft.map(
    r => I.sdone(r, r.fold(_ => I.eofInput, _ => I.emptyInput))
  )
)

def enumBuffered(r: => BufferedReader) =
  new EnumeratorT[Either[Throwable, String], IO] {
    lazy val reader = r
    def apply[A] = (s: StepT[Either[Throwable, String], IO, A]) => s.mapCont(
      k =>
        tryIO(IO(reader.readLine())).flatMap {
          case Right(null) => s.pointI
          case Right(line) => k(I.elInput(Right(line))) >>== apply[A]
          case e => k(I.elInput(e))
        }
    )
  }

现在是枚举器:

def enumFile(f: File): EnumeratorT[Either[Throwable, String], IO] =
  new EnumeratorT[Either[Throwable, String], IO] {
    def apply[A] = (s: StepT[Either[Throwable, String], IO, A]) => s.mapCont(
      k =>
        tryIO(IO(new BufferedReader(new FileReader(f)))).flatMap {
          case Right(reader) => I.iterateeT(
            enumBuffered(reader).apply(s).value.ensuring(IO(reader.close()))
          )
          case Left(e) => k(I.elInput(Left(e)))
        }
      )
  }

我们准备好了:

val action = (
  I.consume[Either[Throwable, String], IO, List] %=
  I.filter(_.fold(_ => true, _.count(_ == '0') >= 20)) &=
  enumFile(new File("numbers.txt"))
).run

现在阅读器将在处理完成后关闭。