r - 为什么 rcpp 中实现的快速排序运行缓慢？

Question

我在 Rcpp 中实现了快速排序算法，但对于大型数组，它的运行速度明显慢于 sort(array, method="quick")。为什么？

这是我的 Rcpp 代码

// partition using hoare's scheme

#include <Rcpp.h>
using namespace Rcpp;

int partition(NumericVector a,int start,int end)
{
    double pivot = a[end];
    int i = start - 1;
    int j = end + 1;
    //Rcout << a <<"\n";
    while(1)
    {
        do {
            i++;
        } while (a[i] < pivot);

        do {
            j--;
        } while (pivot < a[j]);

        if(i > j)
            return j;

        //special.Swap(a, i, j);
        std::swap(a[i], a[j]);
    }
}

void qsort(NumericVector a,int start,int end)
{
  //Rcout << start <<"," << end <<"\n";
  if(start < end)
  {
    int P_index = partition(a, start, end);
    //Rcout << P_index << "\n";
    qsort(a, start, P_index);
    qsort(a, P_index + 1, end);
  }
}


// [[Rcpp::export]]
NumericVector QuickSortH_WC(NumericVector arr)
{
  int len = arr.size();
  qsort(arr, 0, len-1);
  //Rcout << arr <<"\n";
  return 1;
}

对于具有浮点值的数组，该算法也更糟糕。我想与hoare和lomuto分区方案进行比较，但我不知道这个实现是否有任何缺陷，哪个算法运行速度较慢。

Answer 1

代码效率低下的主要原因似乎是混合了要比较的两种分区方案。您声称使用 Hoare 分区方案，代码看起来非常像，但是 pivot 是根据 Lomuto 分区方案计算的。此外，如果 i >= j，则应返回 j，而不是如果 i > j。修复这两件事并将 i++ 替换为稍快的 ++i 我得到:

// partition using hoare's scheme

#include <Rcpp.h>
using namespace Rcpp;

int partition(NumericVector a,int start,int end)
{
    double pivot = a[(start + end) / 2];
    int i = start - 1;
    int j = end + 1;
    //Rcout << a <<"\n";
    while(1)
    {
        do {
            ++i;
        } while (a[i] < pivot);

        do {
            --j;
        } while (pivot < a[j]);

        if(i >= j)
            return j;

        //special.Swap(a, i, j);
        std::swap(a[i], a[j]);
    }
}

void qsort(NumericVector a,int start,int end)
{
    //Rcout << start <<"," << end <<"\n";
    if(start < end)
    {
        int P_index = partition(a, start, end);
        //Rcout << P_index << "\n";
        qsort(a, start, P_index);
        qsort(a, P_index + 1, end);
    }
}


// [[Rcpp::export]]
NumericVector QuickSortH_WC(NumericVector arr)
{
    int len = arr.size();
    qsort(arr, 0, len-1);
    //Rcout << arr <<"\n";
    return arr;
}

/*** R
set.seed(42)
dat <- runif(1e6)
bench::mark(QuickSortH_WC(dat), sort(dat, method="quick"))
*/

输出

> bench::mark(QuickSortH_WC(dat), sort(dat, method="quick"))
# A tibble: 2 x 13
  expression                     min  median `itr/sec` mem_alloc `gc/sec` n_itr
  <bch:expr>                  <bch:> <bch:t>     <dbl> <bch:byt>    <dbl> <int>
1 QuickSortH_WC(dat)          95.7ms 100.5ms      8.63    2.49KB     43.2     5
2 sort(dat, method = "quick")   15ms  16.5ms     53.1    11.44MB     23.6    27
# … with 6 more variables: n_gc <dbl>, total_time <bch:tm>, result <list>,
#   memory <list>, time <list>, gc <list>
Warning message:
Some expressions had a GC in every iteration; so filtering is disabled. 

因此，虽然此方法比 R's sort 慢大约 7 倍，它的运行时间至少具有可比较的数量级。 (感谢@JosephWood 挖掘出链接)。和Wikipedia列出了这两种模式的更多改进。

顺便说一句，我还更改了包装函数以返回更改后的数组。这允许我使用 bench::mark 的默认行为，即比较返回的结果。我发现这很有用...