排序20GB的数据

Question

在过去,我不得不使用大文件,大约在0.1-3GB范围内.并非所有"列"都需要,因此可以将剩余数据放入RAM中.现在我必须处理1-20GB范围内的文件,它们可能会随着时间的推移而增长.这完全不同,因为您无法再将数据放入RAM中.

我的文件包含数百万个"条目"(我找到了一个有30个条目的条目).入口包含大约10个"列":一个字符串(50-1000个unicode字符)和几个数字.我必须按"列"对数据进行排序并显示它.对于用户,只有顶部条目(1-30%)是相关的,其余的是低质量数据.

所以,我需要一些关于朝哪个方向发展的建议.我绝对不希望将数据放入数据库中,因为它们很难为非计算机精通人员安装和配置.我喜欢提供一个单一的程序.

显示数据并不困难.但排序......无需在RAM中加载数据,在常规PC(2-6GB RAM)上......将会耗费一些时间.

---

我看了一下MMF(内存映射文件),但丹尼索普的这篇文章表明它可能不合适:http://dannythorpe.com/2004/03/19/the-hidden-costs-of-memory-映射出的文件/

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

PS:我正在寻找一种适用于Lazarus和Delphi的解决方案,因为Lazarus(实际上是FPC)对Mac有64位支持.64位表示可用RAM更多=排序更快.

Answer 1

我认为还有一个方法是Mergesort,它是一个很好的算法,用于排序大量有限内存的固定记录.

大概的概念:

• 从输入文件中读取N行(允许您将行保留在内存中的值)
• 对这些行进行排序并将排序的行写入文件1

• 用下面的N行重复以获得文件2

  ...

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

• 将这些文件合并到一个文件中(您还必须按步骤执行此操作)

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

Answer 2

如果您只需要整个数据的一小部分,则按顺序扫描文件并仅保留显示所需的条目.FI假设您只需要300万个条目.扫描文件中的前300个条目并在内存中对它们进行排序.然后为每个剩余的条目检查它是否低于内存中的最低值并跳过它.如果它作为内存中的最低条目更高,则将其插入300内的正确位置并丢弃最低值.这将使第二低的最低.重复直到文件结束.