0

这是一个流行的问题：对 100 万个 32 位整数进行排序的最有效（时间复杂度）方法是什么。大多数答案似乎都同意，最好的方法之一是使用基数排序，因为假设这些数字中的位数是恒定的。当 CS 学生第一次学习基于非比较的排序时，这也是一个非常常见的思维练习。但是，我没有看到详细（或至少清楚地）描述的是如何为算法优化选择基数（或桶数）。

在这个观察到的答案中，基数/桶数的选择是凭经验完成的，对于 32 位 100 万整数，结果是 2^8。我想知道是否有更好的方法来选择该号码？在“算法简介”（第 198-199 页）中，它解释了 Radix 的运行时间应该是 Big Theta(d(n+k))（d=digits/passes，n=number of items，k=possible values）。然后它进一步说，给定 n 个 b 位数字，并且任何正整数 r <= b，基数排序在 Big Theta((b/r)(n+2^r)) 时间内对数字进行排序。然后它说：“如果 b>= floor(lg(n))，则选择 r ~= floor(lg(n)) 给出了在常数因子内的最佳时间......”。

但是，如果我们选择 r=lg(1million)~=20 != 8 正如观察到的答案所示。

这告诉我，我很可能误解了书中建议的“选择 r”方法，并且遗漏了一些东西（很可能），或者观察到的答案没有选择最佳值。

谁能帮我解决这个问题？先感谢您。

4

1 回答 1

0

观察到的答案指向似乎需要 Google 提供凭据的东西，而我并不热衷于“请提供论文”。但是，我认为这最好凭经验解决，因为每个参数选择需要多长时间取决于缓存和其他内存访问行为的细节。当我们在理论上计算一个算法需要的时间时，我们通常不会使用如此详细的模型——我们通常只考虑操作次数或内存访问次数，我们通常甚至会丢弃常数因子以便我们可以使用符号就像 O(n) 与 O(n^2)。

如果您在一个长时间运行的程序中执行许多类似的基数排序，您可以让它在启动之前进行一系列测试运行以选择最佳设置。这将确保它使用最快的设置，即使不同的计算机需要不同的设置，因为它们具有不同大小的缓存，或者主内存和缓存之间的访问时间比率不同。

于 2014-01-13T05:37:54.740 回答