C# 中的快速外部排序

• 下载 External-Sort - 5.66 KB
• 浏览 C# 源代码中的 External-Sort

引言

大型数据集的外部排序（以及相关的算法，如合并、连接、分组、唯一）是许多数据组织工作的重要组成部分，例如数据库构建、搜索引擎索引和数据挖掘算法。

背景

当您需要对 5,000,000,000 (5*10^9) 个整数进行排序时，您该怎么办？（如果以二进制方式存储整数，每个整数占用 4 个字节，则约为 18GB 的数据；如果以文本形式存储数据，则约为 30GB）

• 使用数据库。无聊！
• 使用商业产品，例如 oridinal.com 的 nsort。昂贵！
• 使用开源工具，例如 unix sort 命令。不确定！
• 自己编写并查看其性能。有趣！

我在 C# 中编写了自己的外部排序实现，但只与 unix sort 实用程序进行了比较。猜猜怎么着，我的实现比 unix sort 快 6 倍以上。公平地说，有一些研究报告展示了快速排序的实现，但这些实现都针对特定硬件进行了调整，并且通常无法在网上找到。

目标

• 展示一个使用磁盘对大量整数（但仅限整数）进行排序的程序。
• 我的程序在效率方面应与 unix sort 相当或优于它。事实证明，我的程序快了大约 6 倍，当您以小时为单位衡量程序的运行时间时，这是一个很大的差距。
• 我的程序是用 C# 编写的
• 发布我的代码
• 保持简短

非目标

• 编写最快的排序程序
• 编写一个完整的解决方案，即不仅适用于整数，而且适用于任何类型的输入并支持多个选项的程序
• 评估并比较对大型数据集进行排序的大多数可能的选项
• 提供对我自己或其他外部排序方法的广泛讨论

实验

在实现我的程序后，我进行了一次大规模实验。我生成了一个包含 5*10^9 个整数的文本文件。假设每个整数占用 4 个字节，则大约需要 18GB 的空间来存储这么多数据。当数据以文本形式存储时，每行一个数字，根据您是使用 "\n" 还是 "\r\n" 来终止行，则需要 28GB 或 33GB。我使用了两个外部 USB 硬盘驱动器，它们之间的传输速率为每秒 30-35MB。使用一个 USB 硬盘驱动器的结果类似。鉴于排序算法需要对数据集进行两次读取和两次写入，并且假设传输速率在每秒 30-35 MB 之间，那么对于该实验，在最佳情况下，对数据集进行排序应花费 49 到 58 分钟。我使用了以下公式进行此计算

 (   33.0 (*initial read*)
   + 18.0 (*sort chunks and write*) 
   + 18.0 (*read sorted chunks and merge*)
   + 33.0 (*write sorted file*)
 )* 1024.0 (*work in GB*) 
 /
 (   30.0 (*transfer rate MB/s*)
   * 60.0 (*convert to minutes*));;

我将原始文件分成 200MB 的块，这导致了 96 个文件需要合并。总的来说，我的程序没有消耗超过 1GB 的内存。程序的各个部分的计时如下所示

ExternalSort.exe:
Time to sort intermediate files: 00:28:34.9422320
Number of files to merge: 96
Time to merge intermediate files: 00:24:50.6632475 
    (When '\n' for end of line is replaced by '\r\n' it took 00:27:43.6421148)
Total Sort Time: 00:53:25.9329689

我获得了 unix sort 的以下计时

$ time sort -n --buffer-size=1000M --temporary-directory=/cygdrive/e/tmpSort/tmp/ 
--output=unixsort.output input.txt
real    422m35.296s (this is around 7 hours)
user    346m14.309s
sys     2m56.857s

我通过 Windows 性能监视器监控了 unix sort，并注意到大部分时间都花在了 CPU 上。这很奇怪，因为外部排序主要应该是 IO 密集型的。作为另一个基线，我运行了 wc（输出文件上的字数统计命令）

$ time wc -l output.txt
5000000000 output.txt
real    14m22.307s
user    1m40.386s
sys     0m27.424s

字数统计花了大部分时间在 IO 上，这正如预期的那样。

从这个实验中可以看出，读取花费了 14 分钟，读取+写入（无论是初始排序传递还是合并传递）花费了 28=2*14 分钟。似乎对于我选择的特定硬件，排序速度不能快于 4*14（约 26 分钟）。如果使用压缩文件进行输入/输出或使用多个非 USB 磁盘，则可以做得更好。

技巧

每个实现外部排序程序的人都有一些技巧。我使用的最重要的技巧是我执行多个文件合并的方式。文献记载了使用优先级队列。根据我的经验，优先级队列显示出较差的引用局部性并最终变慢。我使用了流的合并，其中每个流都表示为数组+rest。 Rest 包含生成新的“数组+rest”的代码。对于两个以上的流，我预先构建了一个合并的二叉树并分配了存储缓冲区。之后不会发生内存分配。该策略的一个缺点是使用了大量的内存。要合并 n 个文件，其中我为每个文件使用 k 字节的缓冲区，我需要：log(n)*n*k 字节。通常，n <= 1024，因此 log(n) 为 10。