0

我想在 Scala 中实现一个外部合并排序。它用于对无法完全放入主存储器的大文件进行排序。

可以在此处找到详细信息：- 外部合并排序算法如何工作？

现在，我需要读取文件块，对其进行排序并将其写入磁盘等

分段读取/写入大文件的最惯用/功能性的方式是什么？

  • 如果我使用 'Source.fromFile(filename).getLines' 方法，我知道我在文件上获得了一个迭代器，并且可以部分读取它。但是当我得到一个迭代器时，在主内存中读取了多少文件？是否可以从中读取固定数量的字节？
  • 关于如何实现这一点的任何其他建议？可能有一些指向 fs2(scalaz-stream)/Akka Stream/Monix 实现的指针，我可以将文件视为 Stream 并以块的形式读取？
4

1 回答 1

2

分块排序/写入

假设您想一次将 N 个数字保存在内存中，并进一步假设给您一个函数，该函数将 N 个排序后的数字写入文件：

val N : Int = ???

val writeToFile : Seq[Int] => Unit = ???

如您的问题所示，迭代器可用于一次仅将 N 个数字保留在 RAM 中以对它们进行排序并将它们写入中间文件：

val sourceFileName : String = ???

val sortAndWrite : Seq[Int] => Unit = 
  (_.sorted) andThen writeToFile

Source
  .fromFile(sourceFileName)
  .getLines
  .map(_.toInt)
  .grouped(N)
  .foreach(sortAndWrite)

现在您将每组 N 个数字放在不同的文件中。剩下要做的就是将文件合并在一起。

合并

给定一些从每个子文件返回迭代器的读取函数：

val subFiles : Iterable[Iterator[String]] = ???

我们可以编写一个函数，该函数将返回一个新的迭代器，该迭代器从每个文件中获取值并对它们进行排序：

val mergeSort : Iterable[Iterator[String]] => Iterator[Int] = 
  (fileIterators) => {

    val nonEmptyFiles = fileIterators filter (_.hasNext)

    nonEmptyFiles
      .map(_.next)
      .map(_.toInt)
      .sorted
      .toIterator ++ mergeSort(nonEmptyFiles)
  }

注意：上述函数将为Integer每个文件在内存中保留一个，因此 RAM 使用量取决于writeToFile创建的不同文件的数量。

现在只需将值写入文件：

 val destinationFileName : String = ???

 val writer : Writer = new FileWriter(destinationFileName)

 mergeSort(subFiles) foreach (i => writer write i.toString)

不完美排序

需要注意的一件事：如果 N 很小并且源文件不够随机，那么解决方案将不会产生完美的排序。示例：假设N = 2初始列表是[10,11,0,1]算法，经过一轮后，将产生[0,10,1,11]结果。

于 2017-09-04T17:09:38.600 回答