3

TimRun 文档的“计算 minrun”部分,它给出了为 N=2112 数组选择 minrun 的一个好例子和一个坏例子。它指出使用 minrun = 32 效率低下,因为

长度为 2048 和 64 的运行最终合并 自适应噱头可以通过少于 2048+64 次比较来做到这一点,但它仍然比必要的比较多,并且 - 合并排序相对于样本排序的错误 - 更多的数据移动(O (N) 复制只是为了让 64 个元素到位)。

它还将 minrun = 32 算法描述为:

然后我们有一个类似于“2112”的案例,再次为最后一次合并留下了太少的工作要做

然后它表示选择 minrun = 33 将得到一个更好的完美平衡合并。

如果我们在这种情况下采用 minrun=33,那么我们很可能最终得到 64 次运行,每个运行长度为 33,然后所有合并都是完美平衡的。更好的!

我的问题是,如果总元素数相同(示例中为 2112),为什么合并完美平衡的排序数组比不平衡数组更好?

当 minrun=33 的总元素也是 2112 时,为什么 minrun=32 “做的比较比必要的多”?

为什么会有“更多的数据移动”?

为什么最后一次合并“工作太少”?

我的理解是,合并大小为 A 和大小 B 的排序数组需要 O(A+B)。为什么 A 和 B 大小相同时效率更高?

我绘制了如何执行 2 个 minrun 场景的图表,但我仍然感到困惑。

合并规则

错误的最小运行示例

好的最小运行示例

calcMinRun 函数

4

1 回答 1

1

对于 2112 个元素,如果所有运行的大小都是 33,那么从 33 合并到 2112 需要 6 个步骤:33 -> 66 -> 132 -> 264 -> 528 -> 1056 -> 2112。如果所有运行的大小都是 32,从 32 合并到 2112 需要 7 个步骤:32 -> 64 -> 128 -> 256 -> 512 -> 1024 -> 2048 -> 2112。

如果你算一下,在 minrun = 33 时,整个数组分 6 步处理,在 minrun = 32 时,几乎整个数组(2048 个元素)分 6 步处理,那么整个数组在第 7 步处理。

于 2021-08-18T17:34:51.557 回答