哪种k-merge排序在外部排序中效率会更高
Which k-merge sorting will be more efficient in external sorting
我正在处理一个问题，我有 80GB 的数据需要排序。我只有 1GB 主内存来对数据进行排序。显然，我们将在这里应用外部排序方法。但我的问题是哪种 k-merge 排序会更有效率？
- 8 路合并后 10 路合并
- 5 路合并后 16 路合并
K-merge排序的复杂度为O(nk^2)，其中n为元素个数。假设我用这个方法来计算复杂度：
8 路合并后 10 路合并
8 way merge - O(n*8^2) => O(64n)
10 way merge - O(8n*10^2) => O(800n)
Total time complexity => O(64n) + O(800n)
5 路合并后 16 路合并
5 way merge - O(n*5^2) => O(25n)
16 way merge - O(5n*16^2) => O(1280n)
Total time complexity => O(25n) + O(1280n)
查看时间复杂度 5 way merge followed by 16 way merge 似乎需要更多时间。你觉得我的流程对吗？我对此不是很有信心。
更新：@rcgldr 因为你说更大的块大小将花费更少的时间 read/write 那么你如何看待这个公式：
Time to read/write 1 block = Average Seek time +
Average rotational latency + blocksize/Maximum Transfer Rate
根据此公式，如果块大小较小，则总体 read/write 时间也会更少。你觉得这里有什么问题吗？或者我们需要将块的总数与此相乘才能准确了解所需的总时间。
这是一种外部排序，因此正常的时间复杂度不适用，至少在现实世界中不适用。
为了澄清第一个陈述，内存（不是外部）中的 k 向合并（不是合并排序）合并大小为 n 的 k 个数组，因此移动了 k n 个数据，在简单版本中，k-1每次移动都会进行比较，因此 (k n) (k-1) = n k^2 - n k => O(n k^2)。如果使用堆/优先级队列/ ...来跟踪当前的最小元素集，那么比较的次数减少到log2(k)，所以O(n k log2(k)).
内存中 n 个元素的 k 向合并排序需要 ⌈logk(n)⌉ == ceil(logk(n)) 次传递，每次传递移动 n 个元素，因此 n ⌈logk(n)⌉。使用堆/优先级队列/ ... 来实现k个元素的比较需要⌊log2(k)⌋ == floor(log2(k)), 所以 (n ⌈logk(n)⌉ ) (⌊log2(k)⌋ ).如果 n 是 k 的幂，k 是 2 的幂，那么复杂度是 n logk(n) log2(k) = n log2(n)。 k 与复杂度无关，但实际 运行 时间可能更好或更差，k > 2 意味着更多比较，但移动更少，因此问题是比较开销与 运行 开销，例如对指向对象的指针数组进行排序。
回到外部排序，假设进程是 I/O 绑定的，那么复杂性与 I/O 有关，而不是 cpu 操作。
这两种方法都需要 3 次读取/写入 80GB 数据。第一遍创建 1GB 集群的 80 个实例。下一次合并 5 或 8 个簇，最后一次合并 16 或 10 个簇。主要问题是一次读取或写入大块数据以减少随机访问开销。 16 路合并会将 1GB 内存分解成比 10 路合并更小的块，这可能会在随机访问开销方面产生轻微差异，因此 8 / 10 方法可能会更快一些。如果使用固态驱动器进行外部排序，那么随机访问/块大小就不是问题了。
另一个问题是，如果 10 路或 16 路合并在内存中运行得足够快，那么合并过程是 I/O 绑定的。
我正在处理一个问题，我有 80GB 的数据需要排序。我只有 1GB 主内存来对数据进行排序。显然，我们将在这里应用外部排序方法。但我的问题是哪种 k-merge 排序会更有效率？
- 8 路合并后 10 路合并
- 5 路合并后 16 路合并
K-merge排序的复杂度为O(nk^2)，其中n为元素个数。假设我用这个方法来计算复杂度：
8 路合并后 10 路合并
8 way merge - O(n*8^2) => O(64n)
10 way merge - O(8n*10^2) => O(800n)
Total time complexity => O(64n) + O(800n)
5 路合并后 16 路合并
5 way merge - O(n*5^2) => O(25n)
16 way merge - O(5n*16^2) => O(1280n)
Total time complexity => O(25n) + O(1280n)
查看时间复杂度 5 way merge followed by 16 way merge 似乎需要更多时间。你觉得我的流程对吗？我对此不是很有信心。
更新：@rcgldr 因为你说更大的块大小将花费更少的时间 read/write 那么你如何看待这个公式：
Time to read/write 1 block = Average Seek time +
Average rotational latency + blocksize/Maximum Transfer Rate
根据此公式，如果块大小较小，则总体 read/write 时间也会更少。你觉得这里有什么问题吗？或者我们需要将块的总数与此相乘才能准确了解所需的总时间。
这是一种外部排序，因此正常的时间复杂度不适用，至少在现实世界中不适用。
为了澄清第一个陈述，内存（不是外部）中的 k 向合并（不是合并排序）合并大小为 n 的 k 个数组，因此移动了 k n 个数据，在简单版本中，k-1每次移动都会进行比较，因此 (k n) (k-1) = n k^2 - n k => O(n k^2)。如果使用堆/优先级队列/ ...来跟踪当前的最小元素集，那么比较的次数减少到log2(k)，所以O(n k log2(k)).
内存中 n 个元素的 k 向合并排序需要 ⌈logk(n)⌉ == ceil(logk(n)) 次传递，每次传递移动 n 个元素，因此 n ⌈logk(n)⌉。使用堆/优先级队列/ ... 来实现k个元素的比较需要⌊log2(k)⌋ == floor(log2(k)), 所以 (n ⌈logk(n)⌉ ) (⌊log2(k)⌋ ).如果 n 是 k 的幂，k 是 2 的幂，那么复杂度是 n logk(n) log2(k) = n log2(n)。 k 与复杂度无关，但实际 运行 时间可能更好或更差，k > 2 意味着更多比较，但移动更少，因此问题是比较开销与 运行 开销，例如对指向对象的指针数组进行排序。
回到外部排序，假设进程是 I/O 绑定的，那么复杂性与 I/O 有关，而不是 cpu 操作。
这两种方法都需要 3 次读取/写入 80GB 数据。第一遍创建 1GB 集群的 80 个实例。下一次合并 5 或 8 个簇，最后一次合并 16 或 10 个簇。主要问题是一次读取或写入大块数据以减少随机访问开销。 16 路合并会将 1GB 内存分解成比 10 路合并更小的块，这可能会在随机访问开销方面产生轻微差异，因此 8 / 10 方法可能会更快一些。如果使用固态驱动器进行外部排序，那么随机访问/块大小就不是问题了。
另一个问题是，如果 10 路或 16 路合并在内存中运行得足够快，那么合并过程是 I/O 绑定的。