почему быстрая сортировка, реализованная в r cpp, работает медленно? - PullRequest
Новая
       5

почему быстрая сортировка, реализованная в r cpp, работает медленно?

2 голосов
/ 09 февраля 2020

Я реализовал алгоритм быстрой сортировки в R cpp, но он работает значительно медленнее, чем sort(array, method="quick") для больших массивов. Почему?

Вот мой код R cpp 

// 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, но я не знаю, есть ли в этой реализации какой-либо недостаток, для которого алгоритм работает медленнее.

Ответы [ 2 ]

3 голосов
/ 10 февраля 2020

Основной причиной неэффективности вашего кода, похоже, является смешение двух схем разбиения, которые вы хотите сравнить. Вы утверждаете, что используете схему разбиения Hoare, и код очень похож на нее, но pivot рассчитывается в соответствии со схемой разбиения Lomuto. Кроме того, вы должны вернуть j, если i >= 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.

Так что этот метод примерно в 7 раз медленнее, чем R sort, он имеет по крайней мере сопоставимый порядок величины для времени выполнения. (Спасибо @JosephWood за то, что выкопали ссылку). И Википедия перечисляет еще больше улучшений по сравнению с этими двумя схемами.

Кстати, я также изменил функцию-обертку, чтобы она возвращала измененный массив. Это позволяет мне использовать поведение по умолчанию bench::mark, которое заключается в сравнении возвращаемых результатов. Я считаю это полезным ...

1 голос
/ 10 февраля 2020

R cpp плохо применяют рекурсивные функции. Я предлагаю итеративную реализацию быстрой сортировки: 

void _Quick_sorti( double _array[],int _l,int _h){
    int *_stack=new int [_h-_l+1]; double _tmp;int _i,_p,_top=-1;
    _stack[++_top]=_l;_stack[++_top]=_h;
    while(_top>=0){
      _h=_stack[_top--];_l=_stack[_top--];
      _tmp=_array[_h];
      _i=_l-1;
      for(int _j=_l;_j<=_h-1;_j++){
        if(_array[_j]<=_tmp){_i++;std::swap(_array[_i],_array[_j]);}
      }
      _p=_i+1;
      std::swap(_array[_p],_array[_h]);
      if(_p-1>_l){_stack[++_top]=_l;_stack[++_top]=_p-1;}
      if(_p+1<_h){_stack[++_top]=_p+1;_stack[++_top]=_h;}
    }
  delete _stack;
  }


     // [[Rcpp::export]]
SEXP Quick_sorti(SEXP &unsorted) { //run
  SEXP temp=clone(unsorted);// or Rf_duplicate
  double *z=REAL(temp);
  int N=LENGTH(temp)-1;
  int k=0;
  _Quick_sorti(z,k,N); // note that we have provide lvalue (if we put 0 it will not works int place of N)
  return temp;}

Код адаптирован из макросов, которые содержат префикс '_' и выглядят безобразно, кроме того, он использует R внутренние компоненты. Добавление стека подразумевает N больше памяти.

...