algorithm - 外部合并的遍数

Question

似乎没有任何预先存在的问题，至少从标题搜索来看是这样。我正在寻找外部合并的最佳通行证数量。所以，如果我们有 1000 个数据 block ，一次传递就是 1000 种方式合并。两次传递可以是 5 组 200 个 block ，然后最终合并 1 组 5 个 block 。等等。我做了一些数学计算，这一定有缺陷，因为看起来两次传球永远不会超过一次传球。不过，这很可能是对数据读取方式的误解。

首先是一个数值例子:

数据:100GB
内存:1 GB

由于我们有 1GB 内存，我们可以一次加载 1GB 以使用快速排序或归并排序进行排序。现在我们有 100 个 block 要排序。我们可以进行 100 路合并。这是通过使 RAM/(chunks+1) size buckets = 1024MB/101 = 10.14MB 来完成的。 100 个 block 中的每一个都有 100 个 10.14MB 桶，一个输出桶的大小也是 10.14MB。当我们合并时，如果有任何输入桶为空，我们会进行磁盘搜索以重新填充该桶。同样，当输出桶变满时，我们写入磁盘并将其清空。我声称“磁盘需要读取的次数”是(data/ram)*(chunks+1)。我从以下事实中得到这一点:我们有 ram/(chunks+1) 大小的输入桶，我们必须读取给定传递的整个数据，所以我们读取 (data/bucket_size ) 次。换句话说，每次输入桶清空时，我们都必须重新填充它。我们在这里对 100 个 block 执行此操作，因此 numChunks*(chunk_size/bucket_size) = datasize/bucket_size 或 100*(1024MB/10.14MB) . BucketSize = ram/(chunks+1) 所以 100*(1024/10.14) = (data/ram) * (chunks+1) = 1024*100MB/1024MB * 101 = 10100 次读取。

对于两遍系统，我们执行 A 组 B #chunks，然后最终合并 1 组 A #chunks。使用之前的逻辑，我们有 numReads = A*( (data/ram)*(B+1)) + 1*( (data/ram)*(A+1))。我们还有 A*B = Data/Ram。例如，10 组 10 个 block ，其中每个 block 为 GB。这里，A = 10 B = 10。10*10 = 100/1 = 100，即Data/Ram。这是因为 Data/Ram 是原始的 block 数。对于第 2 遍，我们想将 Data/Ram 分成一组 B #chunks。

我会尝试分解这里的公式，令 D = 数据，A = #groups，B = #chunks/group，R = RAM

A*(D/R)*(B+1) + 1*(D/R)*(A+1) - 这是 A 乘以外部合并的读取次数在 B #chunks 上加上在 A #chunks 上的最终合并。

A = D/(R*B) => D^2/(B*R^2) * (B+1) + D/R * (D/(R*B)+1)

(D^2/R^2)*[1 + 2/B] + D/R 是 2 遍外部合并的读取次数。对于 1 遍，我们有 (data/ram)*(chunks+1) 其中 chunks = data/ram 对于 1 遍。因此，对于一次通过，我们有 D^2/R^2 + D/R。我们看到，当 block 大小 B 变为无穷大时，第 2 次传递仅达到该值，即使这样，额外的最终合并也会为我们提供 D^2/R^2 + D/R。所以一定有一些关于我遗漏的读数，或者我的数学有缺陷。感谢所有花时间帮助我的人!

Answer 1

你忽略了从磁盘读取一 block 数据所花费的总时间是

• 对于旋转的硬盘驱动器，访问时间大致恒定，大约为几毫秒。
• 传输时间取决于数据 block 的大小和传输速率。

随着 block 数量的增加，输入缓冲区(您称之为桶)的大小会减小。输入缓冲区越小，恒定访问时间对填充缓冲区所需总时间的影响就越明显。在某一时刻，填充缓冲区的时间几乎完全由访问时间决定。因此合并过程的总时间开始随着缓冲区的数量而不是读取的数据量而增加。

这就是额外的合并 channel 可以加快流程的地方。它允许使用更少和更大的输入缓冲区，并减轻访问时间的影响。

编辑:这是一个快速的粗略计算，可以让您了解盈亏平衡点在哪里。

总传输时间可以很容易地计算出来。所有数据必须每次读取和写入一次:

total_transfer_time = num_passes * 2 * data / transfer_rate

缓冲区读取的总访问时间为:

total_access_time = num_passes * num_buffer_reads * access_time

因为只有一个输出缓冲区，它可以比输入缓冲区大而不浪费太多内存，所以我将忽略写入的访问时间。缓冲区读取的数量是data/buffer_size，缓冲区大小大约是ram/num_chunks for the one-pass approach，chunks 的数量是data/ram 。所以我们有:

total_access_time1 = num_chunks^2 * access_time

对于两次通过的解决方案，使用 sqrt(num_chunks) 缓冲区来最小化访问时间是有意义的。所以缓冲区大小是 ram/sqrt(num_chunks) 我们有:

total_access_time2 = 2 * (data / (ram / sqrt(num_chunks))) * acccess_time
                   = 2 * num_chunks^1.5 * access_time

因此，如果我们使用 transfer_rate = 100 MB/s，access_time = 10 ms，data = 100 GB，ram = 1 GB，总时间为:

total_time1 = (2 * 100 GB / 100 MB/s) + 100^2 * 10 ms
            = 2000 s + 100 s = 2100 s
total_time2 = (2 * 2 * 100 GB / 100 MB/s) + 2 * 100^1.5 * 10 ms
            = 4000 s + 20 s = 4020 s

访问时间的影响还是很小的。因此，让我们将数据更改为 1000 GB:

total_time1 = (2 * 1000 GB / 100 MB/s) + 1000^2 * 10 ms
            = 20000 s + 10000 s = 30000 s
total_time2 = (2 * 2 * 1000 GB / 100 MB/s) + 2 * 1000^1.5 * 10 ms
            = 40000 s + 632 s = 40632 s

现在一次性版本的一半时间花在了磁盘寻道上。让我们尝试使用 5000 GB:

total_time1 = (2 * 5000 GB / 100 MB/s) + 5000^2 * 10 ms
            = 100000 s + 250000 s = 350000 s
total_time2 = (2 * 2 * 5000 GB / 100 MB/s) + 2 * 5000^1.5 * 10 ms
            = 200000 s + 7071 s = 207071 s

现在两次通过版本更快。