10

当数据不适合内存时，网络上有很多关于在 Unix 上对大文件进行排序的话题的讨论。一般使用归并排序和变体。

但是，如果假设有足够的内存来容纳整个数据，那么最有效/最快的排序方式是什么？csv 文件约为 50 GB（> 10 亿行），并且有足够的内存（数据大小的 5 倍）来保存整个数据。

我可以使用 Unix 排序，但这仍然需要 > 1 小时。我可以使用任何必要的语言，但我主要寻找的是速度。我知道我们可以将数据加载到一个列式数据库表中并进行排序，但这是一次性的，所以寻找更灵活的东西......

提前致谢。

4

3 回答 3

5

对大量数据使用并行排序算法。

有用的话题： 哪种并行排序算法的平均案例性能最好？

于 2013-06-26T12:37:26.703 回答
1

快速排序呢？你试过了吗？std::sort 通常由快速排序实现（更准确地说是 introsort，如果快速排序性能不好，它会切换到堆排序），因此您可以尝试使用它。快速排序通常是最快的选择（虽然最坏情况下的复杂度是 O(n^2)，但在通常情况下它胜过所有其他排序算法）。

快速排序的空间复杂度应该不会太差，它需要 log2(N) 的堆栈空间，对于 10 亿个项目，大约有 30 个堆栈帧。

但是，它是不稳定的排序算法（不保留“相等”项目的顺序），所以这取决于你是否同意。

顺便提一句。Unix 排序似乎是通过合并排序实现的，这通常不是 RAM 内排序的最快选择。

于 2013-06-26T12:05:33.010 回答
1

我知道这已经过时了，但我想我会加入我刚刚发现的内容，希望它可以在未来对其他人有所帮助。

您可能已经知道 GNU 排序非常快。再加上许多 CPU 内核和大量 RAM，当您将一些特殊标志传递给 GNU 的排序并使其非常快时。

* 密切注意“缓冲区大小”标志。缓冲区大小是这种加速的主要原因。我以前使用过并行标志，它本身并没有那么快。

sort --parallel=32 --buffer-size=40G -u -t, -k2 -o $file.csv $file

我使用 for 循环来处理文件夹中的所有文件，并使用逗号分隔的第二个键对巨大的 csv 文件进行排序，只保留唯一值，结果如下：

for file in $(ls -p | grep -v  -E "[0-4/]"); 
do 
    time sort --parallel=32 --buffer-size=40G -u -t, -k2 -o $file.sorted.csv $file; 
done

real    0m36.041s
user    1m53.291s
sys     0m32.007s

real    0m52.449s
user    1m52.812s
sys     0m38.202s

real    0m50.133s
user    1m41.124s
sys     0m38.595s

real    0m41.948s
user    1m41.080s
sys     0m35.949s

real    0m47.387s
user    1m39.998s
sys     0m34.076s

输入文件为 5.5 GB，每个文件约 75,000,000 百万行。我在进行排序时看到的最大内存使用量略低于 20 GB。因此，如果它按比例缩放，那么一个 50 GB 的文件应该占用比 200 GB 少一点的空间。在 9 分钟内整理了 27.55 GB 的数据！

于 2021-05-10T08:21:42.360 回答