performance - 基数排序的最佳基础

Question

我已经阅读了关于这个主题的几个来源。但是，我很难弄清楚这些公式的确切含义。当 b = n 时，基数排序似乎是线性的。这是否意味着，我应该将基数设置为数组的长度？

如果我有一个 1 亿个整数的数组，范围从 0 到 10 亿，我应该选择基数 1 亿？

如果这不正确，请尝试为我简化它。我能找到的大多数基数排序示例只有以 10 为底或以 2 为底，因此它们对于分别大于 10 或 2 的数组来说很慢，或者我就是不明白。

谢谢你的帮助。

Answer 1

当您将基数设置为数组中的条目数时，基数排序实际上并不是线性时间。基数排序的运行时间为 O(n log _b U)，其中 n 是数组中元素的总数，b 是选择的基数，U 是数组中的最大数。如果设置 b = n，则运行时间为 O(n log _n U) = O(n log U / log n)。渐近，这真的很棒！

然而，在实践中，其他因素在评估基数排序时往往更为重要。一方面是将数字拆分为单个数字的成本。使用一个 2 的幂的基数，这只是一个简单的位移。对于其他基地，您可能需要使用（相对）更昂贵的部门，这可能会有点伤害。不过，更重要的是，有参考的地方性。如果您使用基数 b，那么您将拥有 b 个不同的数组，其中的元素将被删除。如果选择 b 太高，那么在将元素附加到存储桶数组的末尾时，缓存性能可能会很差，这实际上会导致性能下降。

可能最好的想法是根据不同的基本选择实际分析程序，看看什么是最好的。根据经验，当我尝试使用 base-n 基数排序时，我发现它在大型输入上比标准的 base-2 基数排序慢，主要是由于局部性问题。我猜想 2 不是基数排序的理想基础，但是像 2 ¹⁶这样大的东西可能会开始遭受缓存未命中的困扰。尝试试验，让我们知道您的发现！

希望这可以帮助！

Answer 2

For your case, best Radix sort base is 2^16 (65536), or 2^8 (256). in 1st case, you will sort array for two move for each element, in 2nd - for 4 moves.