最高位优先基数排序比最低位优先基数排序更有效吗？

Question

我刚刚阅读了以下问题：“最高位或最低位先排序的基数排序，哪种更快？”，被采纳回答的作者建议使用MSD基数排序更快，但我并不明白为什么。我实现了基于二进制移位的LSD和MSD，LSD是迭代的，只需要一个桶数组，而MSD则是递归的，每次递归调用都需要一个单独的桶数组。如果创建一个包含1000万个整数的随机数组，我看不出MSD比LSD更快，因为每次重新进入函数时都需要分配额外的桶数组，并且还要面对递归调用本身的开销。我能理解如何通过MSD和LSD的组合来提高效率（对前几位运行MSD，对剩余位运行LSD以减少缓存未命中），但是基于其递归性质和每次递归调用都需要一个新的桶数组的事实，MSD单独如何比LSD更有效呢？

- jsguy

---

你可以重构你的代码，避免这些不必要的分配和释放。请注意，哪一个更快是高度依赖于实现的；我可以实现两者中的任何一个，使得 MSD 排序更快或 LSD 排序更快。 - tmyklebu

你如何避免进行重新分配内存，因为在每个递归调用中都需要桶数组来查找稍后将要递归进入的组？使用全局桶数组或通过引用发送副本到下一个递归调用中，在这两种情况下都会改变你的桶数组，从而使得在之前的递归调用中无法找到下一个组。 - jsguy

每个级别只需要一个桶数组。这是对数级别的；没有理由在每次调用时分配和释放一个。 - tmyklebu

这是真的...... 现在我为每个递归调用使用一个桶。这将需要nxbucketSize空间，与bucketSizexlogn空间相比非常糟糕... - jsguy

实际上我已经想过这个问题，但是我仍然感到困惑。如何使用每层一个桶的数组？有任何相关的参考资料吗？当你从一层到另一层时，你会遇到一堆你需要递归进去的组。在每个组中，你需要检查下一个j位，每个j位序列可能指向桶数组中的任何位置。那么，如何确保不同的组之间不会发生冲突呢？ 我正在使用 @lcgldr 提供的以下实现：http://stackoverflow.com/questions/28726933/cant-get-the-radix-sort-algorithm-to-work-in-c - jsguy

Answer 1

答案

MSD基数排序的迭代次数取决于输入大小，而LSD基数排序的迭代次数取决于关键字长度。这通常导致MSD基数排序需要比LSD基数排序少得多的迭代次数，因此更快。

内存分配不是问题，因为MSD基数排序可以轻松地原地实现。

原理

我已经为LSD和MSD基数排序都做了一个实现，以便我能看到它们具有什么特性，使得MSD基数排序比LSD基数排序更快。

我将它们的速度与100,000,000个随机正63位整数的数组上的std::sort进行了比较（我使用了std::sort的结果，也用于验证排序后的数组），并得到了以下结果：

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

所以，它比std::sort稍微快一点，如果叶子节点使用插入排序进行排序，它就会快得多。

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

• 有缓存局部性，但我怀疑这是否真的很重要，因为LSD基数排序也会扫描整个数组，而不是执行随机访问。
• MSD基数排序可以被实现成空间复杂度为O(d k)的算法，因此只取决于基数和项的长度。这可以在堆栈上分配，几乎是免费的。因此，它基本上是一种原地排序算法。
• 底层可以被修剪。即当一个桶仅包含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]++;
    }
  }
}

- bcmpinc

Answer 2

你所提到的问题仅对单个位执行排序。因此，每次递归仅将数组分成两组。因此，在递归时实际上不需要存储太多内容。

你下降的小组-越大的组，您将其放在堆栈上以供稍后执行。在最坏的情况下，您将最多在堆栈中拥有 w 个元素，其中 w 是数据类型的宽度（以位为单位）。

现在，在证明递归在这种情况下并不那么糟糕之后，Niklas B.的论据 展示了 MSD 为何有机会运行得更快（即缓存局部性）。

- CygnusX1