6

对大于可用内存（许多 10 千兆字节）并包含可变长度记录的文本文件进行排序的好算法是什么？我见过的所有算法都假设 1) 数据适合内存，或者 2) 记录是固定长度的。但想象一个我想按“出生日期”字段（第 4 个字段）排序的大 CSV 文件：

Id,UserId,Name,BirthDate
1,psmith,"Peter Smith","1984/01/01"
2,dmehta,"Divya Mehta","1985/11/23"
3,scohen,"Saul Cohen","1984/08/19"
...
99999999,swright,"Shaun Wright","1986/04/12"
100000000,amarkov,"Anya Markov","1984/10/31"

我知道：

  1. 这将在一台机器上运行（非分布式）。
  2. 我要运行它的机器将有几个处理器。
  3. 我要排序的文件可能比机器的物理内存大。
  4. 文件包含可变长度的行。每行将包含固定数量的列（分隔符分隔的值）。文件将按特定字段（即文件中的第 4 个字段）排序。
  5. 一个理想的解决方案可能是“使用这个现有的排序实用程序”，但我正在寻找最好的算法。
  6. 我不希望得到一个完全编码的、有效的答案。更多类似于“检查一下，这是它的工作原理，或者这就是它对这个问题有效的原因”。我只是不知道在哪里看...
  7. 这不是家庭作业！

谢谢！♥</p>

4

4 回答 4

3

这类算法称为外部排序。我将从查看Wikipedia 条目开始。它包含一些讨论和指示。

于 2010-12-15T18:24:02.397 回答
1

推荐以下资源：

合并排序：http ://en.wikipedia.org/wiki/Merge_sort

Seminumerical Algorithms, vol 2 of The Art of Computer Programming: Knuth: Addison Wesley:ISBN 0-201-03822-6(v.2)

于 2010-12-15T18:39:55.467 回答
0

标准的合并排序方法将起作用。常见的架构是

  1. 将文件分成大小大致相等的 N 部分
  2. 对每个部分进行排序（如果它足够小，则在内存中，否则递归应用相同的算法）
  3. 合并排序的部分
于 2010-12-15T18:34:11.210 回答
0

无需排序。每天读取文件 ALL.CSV 并将每个读取行附加到文件中，例如 19841231.CSV。对于具有数据的每个现有日期，按数字顺序读取该 CSV 文件并将这些行附加到新文件中。例如，通过多次处理原始文件或通过在文件 ALL.CSV 中记录实际发生的天数，可以进行优化。

因此，应将包含“1985/02/28”的行添加到文件 19850228.CSV。在将文件 19850227.CSV 附加到 NEW.CSV 之后，应将文件 19850228.CSV 附加到 NEW.CSV。数字顺序避免了使用所有排序算法，尽管它可能会折磨文件系统。

实际上，文件 ALL.CSV 可以按例如年分割成一个文件。1984.CSV、1985.CSV 等等。

于 2013-08-27T03:10:08.793 回答