algorithm - 并行外部排序的复杂度是多少

Question

我想知道进行并行外部排序时的复杂性是什么。

假设我有一个大数组 N 和有限的内存。 F.e 10 亿个条目要排序，条目内存中只有 1k。

对于这种情况，我使用并行线程将大数组分成 K 个排序文件， block 大小为 B，并保存在磁盘中。

从所有文件中读取后，使用 pripriityQueue 和线程合并回新数组。

我需要用大 O 表示法计算复杂度。

如果我使用多进程(比方说 N 个处理器)，复杂性会怎样？

is it ~O(N/10 * log N) ?? 

谢谢

Answer 1

无论处理器数量和/或外部驱动器数量如何，时间复杂度都将为 O(n log(n))。总时间为 T(n/a logb(n))，但由于 a 和 b 是常量，时间复杂度在 O(n log(n)) 时保持不变，即使时间快 10 倍.

我不清楚“并行”外部排序是什么意思。我假设有多个内核或多个处理器，但是否还有多个驱动器？所有 N 个内核或处理器是否共享仅包含 1k 元素的相同内存，或者每个内核或处理器是否有自己的“1k”内存(实际上有“Nk”内存)？

---

一般的外部归并排序

在初始遍历中，输入数组以大小为 B 的 block (1k 个元素)读取，排序，然后写入 K 个排序文件。此初始传递的最终结果是大小为 B(1k 个元素)的 K 个排序文件。所有剩余的遍将重复合并排序的文件，直到生成单个排序的文件。

初始 channel 通常受 cpu 限制，使用多个内核或处理器对每个大小为 B 的 block 进行排序会减少时间。任何排序方法或任何稳定的排序方法都可以用于初始传递。

对于合并阶段，能够在执行合并操作的同时执行 I/O 将减少时间。使用多线程将 I/O 与合并操作重叠将减少时间，并且比使用异步 I/O 来做同样的事情更简单。我不知道有什么方法可以使用多线程来减少 k 路合并操作的时间。

对于 k 路合并，文件以大小为 B/(k+1) 的较小块读取。这允许 k 个输入缓冲区和 1 个输出缓冲区用于 k 路合并操作。

对于硬盘驱动器，随机访问开销是一个问题，假设传输速率为 200 MB/s，平均随机访问开销为 0.01 秒，这与传输 2 MB 的时间相同。如果缓冲区大小为 2 MB，则随机访问开销会有效地将传输速率降低 1/2 至约 100 MB/s。如果缓冲区大小为 8 KB，则随机访问开销会有效地将传输速率降低 1/250 至约 0.8 MB/s。由于随机访问的开销，使用小缓冲区时，双向合并会更快。

对于非服务器设置中的 SSD，通常没有命令排队，命令开销约为读取时的 .0001 秒，写入时的 .000025 秒。 Sata 接口(interface) SSD 的传输速率约为 500 MB/s。如果缓冲区大小为 2MB，则命令开销微不足道。如果缓冲区大小为 4KB，则读取速率降低 1/12.5 至约 40 MB/s，写入速率降低 1/3.125 至约 160 MB/s。因此，如果缓冲区大小足够小，那么 2 路合并会更快。

在 PC 上，这些小缓冲区场景不太可能发生。对于大型文本文件的 gnu 排序，在默认设置下，它分配 1GB 多一点的 ram，在初始传递时创建 1GB 排序文件，并进行 16 路合并，因此缓冲区大小为 1GB/17 ~ = 60 MB。 (17 代表 16 个输入缓冲区，1 个输出缓冲区)。

---

考虑所有数据都在内存中的情况，并且内存由 k 个排序列表组成。合并列表的时间复杂度将为 O(n log(k))，无论是否使用 2 向合并排序，以任何顺序合并列表对，或者是否使用 k 向合并排序来合并所有一次列出。

我在我的系统上对此做了一些实际测试，Intel 3770K 3.5ghz，Windows 7 Pro 64 位。对于基于堆的 k 路合并，k = 16，传输速率约为 235 MB/秒，k = 4，传输速率约为 495 MB/秒。对于非堆 4 路合并，传输速率约为 1195 MB/秒。硬盘传输速率通常为 70 MB/秒到 200 MB/秒。典型的 SSD 传输速率约为 500 MB/秒。昂贵的服务器类型 SSD(SAS 或 PCIe)读取速度高达 ~2GB/秒，写入速度高达 ~1.2GB/秒。