delphi - 排序20GB数据

Question

过去我必须处理大文件，大约在 0.1-3GB 范围内。并非所有“列”都是必需的，因此可以将剩余数据放入 RAM 中。 现在我必须处理 1-20GB 范围内的文件，并且它们可能会随着时间的推移而增长。这是完全不同的，因为你不能再将数据放入 RAM 中。

我的文件包含数百万个“条目”(我发现一个包含 3000 万个条目)。条目包含大约 10 个“列”:一个字符串(50-1000 个 unicode 字符)和几个数字。我必须按“列”对数据进行排序并显示它。对于用户来说，只有顶部条目 (1-30%) 是相关的，其余的都是低质量数据。

所以，我需要一些关于前进方向的建议。我绝对不想将数据放入数据库中，因为对于不懂计算机的人来说，它们很难安装和配置。我喜欢交付一个整体程序。

显示数据一点也不困难。但是在普通电脑(2-6GB RAM)上排序...而不将数据加载到 RAM 中...会消磨一些美好的时间。

<小时/>

我正在研究 MMF(内存映射文件)，但 Danny Thorpe 的这篇文章表明它可能不合适:http://dannythorpe.com/2004/03/19/the-hidden-costs-of-memory-mapped-files/

所以，我正在考虑只加载必须在内存中排序的列中的数据以及指向“条目”地址(到磁盘文件中)的指针。我对“列”进行排序，然后使用指针查找与每个列单元格对应的条目并恢复该条目。 “恢复”将直接写入磁盘，因此不需要额外的 RAM。

PS:我正在寻找一种可以在 Lazarus 和 Delphi 上运行的解决方案，因为 Lazarus(实际上是 FPC)对 Mac 具有 64 位支持。 64 位意味着更多可用 RAM = 更快排序。

Answer 1

我认为可行的方法是 Mergesort ，这是一个很好的排序算法 内存有限，大量固定记录。

总体思路:

• 从输入文件中读取 N 行(允许您将这些行保留在内存中的值)

• 对这些行进行排序并将排序后的行写入文件 1

• 重复接下来的 N 行以获得文件 2

  ...

• 您到达输入文件的末尾，现在有 M 个文件(每个文件都已排序)

• 将这些文件合并为一个文件(您也必须分步骤执行此操作)

<小时/>

您还可以考虑基于嵌入式数据库的解决方案，例如Firebird embedded :它与 Delphi/Windows 配合良好，您只需在程序文件夹中添加一些 DLL(我不确定 Lazarus/OSX )。