gpt4 book ai didi

c++ - 最高有效位基数排序如何比最低有效位基数排序更有效?

转载 作者:太空狗 更新时间:2023-10-29 20:24:16 24 4
gpt4 key购买 nike

我刚刚在阅读以下问题: Radix sort most significant first or least significant, which is faster?

接受答案的作者暗示 MSD 基数排序确实更快。但是我不明白为什么。

我已经实现了 LSD 和 MSD(通过移位操作基于二进制),LSD 是迭代的,只需要一个桶数组,而 MSD 是递归的,每次递归调用都需要一个单独的桶数组。

如果您创建一个包含 1000 万个整数的随机数组,我看不出 MSD 会比 LSD 快多少,因为您每次重新输入函数时都会分配额外的桶数组,而且您还必须面对开销递归调用自己。

我可以看到 MSD 和 LSD 的组合如何提供全面的提升(对前几位运行 MSD,对其余位运行 LSD 以减少缓存未命中),但是单独使用 MSD 是如何预期更多考虑到 LSD 的递归性质以及每次递归调用都需要一个新的桶数组这一事实,它比 LSD 更高效,这与 LSD 不同,LSD 是迭代的并且只需要一个桶数组来完成整个排序过程?

最佳答案

回答

MSD 基数排序的迭代次数取决于输入大小,而 LSD 基数排序的迭代次数取决于 key 长度。这通常会导致 MSD 基数排序所需的迭代次数明显少于 LSD 基数排序,因此速度更快。

内存分配不是问题,因为 MSD 基数排序可以很容易地就地实现。

理由

我已经实现了 LSD 和 MSD 基数排序,所以我可以看到它们具有哪些属性使 MSD 基数排序比 LSD 基数排序更快。

我将它们的速度与 std::sort 在 100.000.000 个随机正 63 位整数的数组上进行了比较(我使用 std::sort 的结果我也用于验证排序的数组)并得到以下结果:

  • 纯 LSD 排序:10.5s
  • std::sort : 9.5s
  • 纯 MSD 排序:9.3s
  • MSD 排序 + 插入排序:7.6s

因此,它比 std::sort 稍微快一些,如果叶子用 insertion_sort 排序,它会快很多。

为什么 MSD 基数排序可能比 LSD 基数排序更快?

  • 存在缓存局部性,但我怀疑这是否真的很重要,因为 LSD 基数排序也会扫描数组,而不是执行随机访问。
  • 可以实现 MSD 基数排序,使其空间复杂度为 O(d k),因此仅取决于基数 d 和项的长度 k。这个可以在栈上分配,几乎是免费的。因此,它基本上是一种就地排序算法。
  • 可以修剪底层。 IE。当一个桶只包含 1 个元素时,它已经排序,因此不需要对该桶进行递归。因此,MSD 基数排序只需要执行大约 log(n)/log(d) 次迭代。而 LSD 基数排序总是必须执行 k 次迭代。

我相信最后一点是 MSD 基数排序通常比 LSD 基数排序更快的原因。如果输入数据是均匀随机分布的,则期望运行时间为 O(n log(n)/log(d)),而 LSD 基数排序的运行时间为 O(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]++;
}
}
}

关于c++ - 最高有效位基数排序如何比最低有效位基数排序更有效?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28884387/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com