0

我正在解决一个问题,其中我有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 既然你说更大的块大小将花费更少的时间来读/写那么你如何看待这个公式:

Time to read/write  1 block = Average Seek time + 
Average rotational latency + blocksize/Maximum Transfer Rate

根据这个公式,如果块大小很小,那么整体读/写时间也会更短。你觉得这里有什么问题吗?或者我们需要将块的总数与此相乘才能准确了解所需的总时间。

4

1 回答 1

2

这是一种外部排序,因此正常的时间复杂度不适用,至少在现实世界的情况下不适用。

为了澄清第一条语句,内存(不是外部)中的 k 路合并(不是合并排序)合并了 k 个大小为 n 的数组,因此移动了 kn 个数据,在一个简单的版本中,对每个数组进行 k-1 次比较移动,所以 (kn) (k-1) = nk^2 - nk => O(nk^2)。如果使用堆/优先级队列/...来跟踪当前最小元素集,则比较次数减少到 log2(k),因此 O(nk 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 数据。第一遍创建 80 个 1GB 集群实例。下一遍一次合并 5 或 8 个簇,最后一遍一次合并 16 或 10 个簇。主要问题是一次读取或写入大量数据以减少随机访问开销。与 10 路合并相比,16 路合并会将 1GB 的内存分成更小的块,这可能会对随机访问开销产生细微的影响,因此 8 / 10 方法可能会更快一些。如果使用固态驱动器进行外部排序,那么随机访问/块大小就不是问题了。

另一个问题是 10 路或 16 路合并是否在内存中运行得足够快,以至于合并过程是 I/O 绑定的。

于 2015-12-07T06:23:28.493 回答