0

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

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

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

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

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

如果我使用多进程让我们说 N 个处理器，复杂性会发生什么？

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

谢谢

4

1 回答 1

2

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

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

一般的外部归并排序

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

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

对于合并阶段，能够在执行合并操作的同时执行 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。由于随机访问的开销，使用较小的缓冲区，2 路合并会更快。

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

在 PC 上，这些小缓冲区情况不太可能发生。对于大文本文件的 gnu 排序，在默认设置下，它分配超过 1GB 的内存，在初始传递时创建 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/sec，k = 4，传输速率 ~ 495 MB/sec。对于非堆 4 路合并，传输速率 ~ 1195 MB/秒。硬盘传输速率通常为 70 MB/秒到 200 MB/秒。典型的 SSD 传输速率约为 500 MB/秒。昂贵的服务器类型 SSD（SAS 或 PCIe）读取速度高达 ~2GB/秒，写入速度高达 ~1.2GB/秒。

于 2019-02-16T10:41:00.463 回答