我刚刚读到以下问题:基数先排序最显著还是最不显著,哪个更快?
公认答案的作者认为MSD基数排序确实更快。我不明白为什么。
我已经实现了LSD和MSD(通过执行移位操作基于二进制),LSD是迭代的,只需要一个bucket数组,而MSD是递归的,每个递归调用需要一个单独的bucket数组。
如果你创建一个1000万整数的随机数组,我看不出MSD会比LSD快多少,因为每次重新输入函数时都会分配额外的bucket数组,而且你还必须面对递归调用本身的开销。
我可以看到MSD和LSD的组合如何提供全面的提升(对前几个位运行MSD,对其余位运行LSD,以减少缓存未命中),但考虑到MSD的递归性质以及每次递归调用都需要一个新的bucket数组的事实,单靠MSD怎么会比LSD更高效,与LSD不同,LSD是迭代的,整个排序过程只需要一个桶数组?
答案
MSD基数的迭代次数取决于输入大小,而LSD基数排序的迭代次数则取决于密钥长度。这通常导致MSD基数排序比LSD基数排序需要更少的迭代,因此速度更快。
内存分配不是问题,因为MSD基数排序可以很容易地就地实现。
基本原理
我已经为LSD和MSD基数排序做了一个实现,所以我可以看看它们有什么属性可以使MSD基数分类比LSD基数分类更快
我在一个由100.000.000个随机正63位整数组成的数组上将它们的速度与std::sort进行了比较(我使用了std::sort的结果,我也用它来验证排序后的数组),得到了以下结果:
- 纯LSD排序:10.5s
- std::排序:9.5秒
- 纯MSD排序:9.3s
- MSD排序+插入排序:7.6s
因此,它比std::sort稍微快一点,如果用insert_sort对叶子进行排序,它会快很多。
为什么MSD基数排序可能比LSD基数排序更快
- 还有缓存局部性,尽管我怀疑这是否真的很重要,因为LSD基数排序也会扫描数组,而不是执行随机访问
- MSD基数排序可以实现为其空间复杂度为O(dk),因此仅取决于基数d和项k的长度。这可以在堆栈上分配,堆栈几乎是免费的。因此,它基本上是一种就地排序算法
- 底层可以修剪。也就是说,当一个bucket只包含一个元素时,它已经被排序了,因此不需要在该bucket上递归。因此,MSD基数排序只需要执行近似log(n)/log(d)的迭代。而LSD基数排序总是必须执行k次迭代
我相信最后一点就是MSD基数排序通常比LSD基数排序快的原因。如果输入数据是均匀随机分布的,则预期运行时间为O(n-log(n)/log(d)),而LSD基数排序的运行时间为0(n-k)。通常n比k^d小很多。只有当n=o(k^d)时,LSD基数排序才会更快。但是,在这种情况下,也可以使用计数排序(k=1的基数排序)。
实施
inline void insertion_sort(int64_t * array, int n) {
for (int i=1; i<n; i++) {
int64_t val = array[i];
int j = i;
while (j>0 && array[j-1] > val) {
array[j] = array[j-1];
j--;
}
array[j] = val;
}
}
void msd_sort(int64_t * array, int n, int64_t bit=60) {
const int64_t mask = INT64_C(7);
// Count bucket sizes
int count[9]={};
for (int i=0; i<n; i++) {
count[((array[i]>>bit) & mask)+1]++;
}
// Create holes.
int loc[8];
int64_t unsorted[8];
int live = 0;
for (int i=0; i<8; i++) {
loc[i] = count[i];
count[i+1]+=count[i];
unsorted[live] = array[loc[i]];
if (loc[i] < count[i+1]) {
live++;
}
}
live--;
// Perform sort
for (int i=0; i<n; i++) {
int64_t val = unsorted[live];
int64_t d = (val>>bit) & mask;
array[loc[d]] = val;
loc[d]++;
unsorted[live] = array[loc[d]];
if (loc[d] == count[d+1]) {
live--;
}
}
if (bit>0) {
for (int i=0; i<8; i++) {
n = count[i+1] - count[i];
if (n > 20) { // If replaced by n > 1, insertion_sort is not needed.
msd_sort(array + count[i], n, bit-3);
} else {
insertion_sort(array + count[i], n);
}
}
}
}
void lsd_sort(int64_t * array, int n) {
const int64_t mask = INT64_C(7);
std::vector<int64_t> buffer(n);
for (int64_t bit=0; bit<63; bit+=3) {
// Copy and count
int count[9]={};
for (int i=0; i<n; i++) {
buffer[i] = array[i];
count[((array[i]>>bit) & mask) + 1]++;
}
// Init writer positions
for (int i=0; i<8; i++) {
count[i+1]+=count[i];
}
// Perform sort
for (int i=0; i<n; i++) {
int64_t val = buffer[i];
int64_t d = (val>>bit) & mask;
array[count[d]] = val;
count[d]++;
}
}
}
您所指的问题是仅对单个位执行排序。因此,每次递归都只将数组分成两组。因此,在递归时,实际上不需要存储太多内容。
你下降的小组越小,越大的小组,你就把它放在一个堆栈上,以便稍后执行。在最坏的情况下,堆栈中最多有w
元素,其中w
是数据类型的宽度(以位为单位)。
现在,已经证明递归在这种情况下并没有那么糟糕,Niklas B.为什么MSD有机会运行得更快(即缓存位置)的论点成立了。