并行外部排序的复杂度是多少
what is the complexity of parallel external sort
我想知道进行并行外部排序时的复杂性是什么。
假设我有一个大数组 N 和有限的内存。 F.e 10 亿个条目要排序，条目内存中只有 1k。
对于这种情况，我使用并行线程将大数组分成 K 个排序文件，块大小为 B，并保存在磁盘中。
从所有文件中读取之后，使用 pripriityQueue 和线程合并回新数组。
我需要用大 O 表示法计算复杂度。
如果我使用多进程（比如 N 个处理器），复杂性会发生什么变化？
is it ~O(N/10 * log N) ??
谢谢
无论处理器数量如何，时间复杂度都将是 O(n log(n)) and/or 外部驱动器的数量。总时间为 T(n/a logb(n))，但由于 a 和 b 是常量，时间复杂度在 O(n log(n)) 时保持不变，即使时间是 10 次一样快。
我不清楚 "parallel" 外部排序是什么意思。我假设有多个内核或多个处理器，但是否还有多个驱动器？所有 N 个内核或处理器是否共享仅包含 1k 元素的相同内存，或者每个内核或处理器是否有自己的“1k”内存（实际上有 "Nk" 内存）？
一般的外部归并排序
在初始传递中，输入数组以大小为 B 的块（1k 个元素）读取，排序，然后写入 K 个排序文件。此初始传递的最终结果是大小为 B（1k 个元素）的 K 个排序文件。所有剩余的遍将重复合并排序文件，直到生成单个排序文件。
初始通道通常是 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，通常没有命令排队，命令开销约为读取时的 .0001 秒，写入时的 .000025 秒。 Sata 接口 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/sec，k = 4，传输率 ~ 495 MB/sec。对于非堆 4 路合并，传输速率约为 1195 MB/sec。硬盘传输速率通常为 70 MB/sec 到 200 MB/sec。典型的 SSD 传输速率约为 500 MB/sec。昂贵的服务器类型 SSD（SAS 或 PCIe）读取速度高达 ~2GB/秒，写入速度高达 ~1.2GB/秒。
我想知道进行并行外部排序时的复杂性是什么。
假设我有一个大数组 N 和有限的内存。 F.e 10 亿个条目要排序，条目内存中只有 1k。
对于这种情况，我使用并行线程将大数组分成 K 个排序文件，块大小为 B，并保存在磁盘中。
从所有文件中读取之后，使用 pripriityQueue 和线程合并回新数组。
我需要用大 O 表示法计算复杂度。
如果我使用多进程（比如 N 个处理器），复杂性会发生什么变化？
is it ~O(N/10 * log N) ??
谢谢
无论处理器数量如何，时间复杂度都将是 O(n log(n)) and/or 外部驱动器的数量。总时间为 T(n/a logb(n))，但由于 a 和 b 是常量，时间复杂度在 O(n log(n)) 时保持不变，即使时间是 10 次一样快。
我不清楚 "parallel" 外部排序是什么意思。我假设有多个内核或多个处理器，但是否还有多个驱动器？所有 N 个内核或处理器是否共享仅包含 1k 元素的相同内存，或者每个内核或处理器是否有自己的“1k”内存（实际上有 "Nk" 内存）？
一般的外部归并排序
在初始传递中，输入数组以大小为 B 的块（1k 个元素）读取，排序，然后写入 K 个排序文件。此初始传递的最终结果是大小为 B（1k 个元素）的 K 个排序文件。所有剩余的遍将重复合并排序文件，直到生成单个排序文件。
初始通道通常是 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，通常没有命令排队，命令开销约为读取时的 .0001 秒，写入时的 .000025 秒。 Sata 接口 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/sec，k = 4，传输率 ~ 495 MB/sec。对于非堆 4 路合并，传输速率约为 1195 MB/sec。硬盘传输速率通常为 70 MB/sec 到 200 MB/sec。典型的 SSD 传输速率约为 500 MB/sec。昂贵的服务器类型 SSD（SAS 或 PCIe）读取速度高达 ~2GB/秒，写入速度高达 ~1.2GB/秒。