最重要的位基数排序如何比最低位基数排序更有效？

2 回答

• 1

  答案

  MSD基数中的迭代次数取决于输入大小，而LSD基数排序中的迭代次数取决于密钥长度 . 这通常导致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 sort insertion_sort：7.6s

  因此，它比std :: sort略快，如果使用insertion_sort对叶子进行排序，则速度要快得多 .

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

  • 有缓存局部性，但我怀疑这是否真的很重要，因为LSD基数排序也会扫描数组，而不是执行随机访问 .

  • MSD基数排序可以实现为其空间复杂度为O（d k），因此仅取决于基数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]++;
      }
    }
  }
  

  回复于 2024-04-26T17:37:18+08:00
• 4

  您要引用的问题是仅对单个位执行排序 . 因此，每次递归仅将数组拆分为两组 . 因此，在递归时实际上您不必存储太多内容 .

  你下降的小组 - 更大的组，你放在一个堆栈以便以后执行 . 在最坏的情况下，堆栈中最多只有 w 个元素，其中 w 是数据类型的宽度（以位为单位） .

  现在，已经证明在这种情况下递归并不是那么糟糕，argumentation of Niklas B.为什么MSD有机会运行得更快（即缓存局部性） .

  回复于 2024-04-26T17:37:18+08:00