sort.cpp

#include <Rcpp.h>
#include <boost/sort/spreadsort/spreadsort.hpp>

using namespace Rcpp;
using namespace boost::sort::spreadsort;

template <int RTYPE>
Vector<RTYPE> sort_impl(const Vector<RTYPE> & x, bool decreasing = false) {
    Vector<RTYPE> res = no_init(x.size());
    std::copy(x.begin(), x.end(), res.begin());
    spreadsort(res.begin(), res.end());
    if (decreasing) std::reverse(res.begin(), res.end());
    return res;
}

template <>
Vector<STRSXP> sort_impl(const Vector<STRSXP> & x, bool decreasing) {
    std::vector<std::string> res(x.size());
    std::copy(x.begin(), x.end(), res.begin());
    spreadsort(res.begin(), res.end());
    if (decreasing) std::reverse(res.begin(), res.end());
    return wrap(res);
}

// [[Rcpp::export]]
SEXP sort2(SEXP x, bool decreasing = false) {
    switch(TYPEOF(x)) {
    case INTSXP:
        return sort_impl<INTSXP>(x, decreasing);
    case REALSXP:
        return sort_impl<REALSXP>(x, decreasing);
    case STRSXP:
        return sort_impl<STRSXP>(x, decreasing);
    default:
        stop("Unsupported type.");
    }
}

template <int RTYPE>
Vector<RTYPE> sort_impl2(const Vector<RTYPE> & x, bool decreasing = false) {
    Vector<RTYPE> res = no_init(x.size());
    std::copy(x.begin(), x.end(), res.begin());
    std::sort(res.begin(), res.end());
    if (decreasing) std::reverse(res.begin(), res.end());
    return res;
}

// [[Rcpp::export]]
SEXP sort3(SEXP x, bool decreasing = false) {
    switch(TYPEOF(x)) {
    case INTSXP:
        return sort_impl2<INTSXP>(x, decreasing);
    case REALSXP:
        return sort_impl2<REALSXP>(x, decreasing);
    case STRSXP:
        return sort_impl2<STRSXP>(x, decreasing);
    default:
        stop("Unsupported type.");
    }
}

/*** R
n <- 1E6
int <- sample.int(1000, n, replace = TRUE)
dbl <- runif(n)
chr <- sample(letters, n, replace = TRUE)
library(benchr)
benchmark(sort(int, method = "radix"),
          sort(int, method = "shell"),
          sort(int, method = "quick"),
          sort2(int),
          sort3(int))
benchmark(sort(dbl, method = "radix"),
          sort(dbl, method = "shell"),
          sort(dbl, method = "quick"),
          sort2(dbl),
          sort3(dbl))
benchmark(sort(chr, method = "radix"),
          sort(chr, method = "shell"),
          sort(chr, method = "quick"),
          sort2(chr),
          sort3(chr))
*/

R> n <- 1E6

R> int <- sample.int(1000, n, replace = TRUE)

R> dbl <- runif(n)

R> chr <- sample(letters, n, replace = TRUE)

R> library(benchr)

R> benchmark(sort(int, method = "radix"),
..           sort(int, method = "shell"),
..           sort(int, method = "quick"),
..           sort2(int), .... [TRUNCATED] 
Benchmark summary:
Time units : milliseconds 
                        expr n.eval   min lw.qu median  mean up.qu  max total relative
 sort(int, method = "radix")    100 11.90 12.30  12.80 14.00 13.30 40.1  1400     1.43
 sort(int, method = "shell")    100 60.60 61.20  61.50 61.70 61.90 65.3  6170     6.87
 sort(int, method = "quick")    100 39.80 40.00  40.40 41.10 40.70 69.4  4110     4.52
                  sort2(int)    100  8.62  8.72   8.95  9.36  9.21 34.2   936     1.00
                  sort3(int)    100 35.50 35.50  35.70 36.20 36.10 64.0  3620     3.99

R> benchmark(sort(dbl, method = "radix"),
..           sort(dbl, method = "shell"),
..           sort(dbl, method = "quick"),
..           sort2(dbl), .... [TRUNCATED] 
Benchmark summary:
Time units : milliseconds 
                        expr n.eval  min lw.qu median mean up.qu   max total relative
 sort(dbl, method = "radix")    100 63.0  63.9   65.9 67.4  67.9 100.0  6740     1.30
 sort(dbl, method = "shell")    100 96.4  97.1   97.5 99.0 101.0 132.0  9900     1.93
 sort(dbl, method = "quick")    100 74.4  74.6   75.1 76.4  75.8 108.0  7640     1.48
                  sort2(dbl)    100 49.3  50.0   50.6 52.2  52.5  79.8  5220     1.00
                  sort3(dbl)    100 65.9  66.1   66.7 68.5  68.1  94.8  6850     1.32

R> benchmark(sort(chr, method = "radix"),
..           sort(chr, method = "shell"),
..           sort(chr, method = "quick"),
..           sort2(chr), .... [TRUNCATED] 
Benchmark summary:
Time units : milliseconds 
                        expr n.eval   min lw.qu median  mean up.qu   max total relative
 sort(chr, method = "radix")    100  16.4  17.1   18.0  19.6  19.3  57.9  1960     1.00
 sort(chr, method = "shell")    100 143.0 143.0  144.0 147.0 146.0 185.0 14700     8.04
 sort(chr, method = "quick")    100 143.0 143.0  144.0 146.0 146.0 179.0 14600     8.00
                  sort2(chr)    100  32.7  33.2   33.8  34.8  34.9  68.3  3480     1.88
                  sort3(chr)    100 272.0 272.0  273.0 275.0 274.0 310.0 27500    15.20