Быстро отсортированный образец с заменой

Question

В основном я хочу сделать sort(sample(n, replace = TRUE)), для n = 1e6 и много раз (например, 1e4 раза).

Есть ли способ сделать это быстрее в R (cpp)?

Answer 1

Реализация идеи Фрэнка в Rcpp:

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
IntegerVector sort_sample(int n) {
  IntegerVector tab(n);
  for (int i = 0; i < n; i++) {
    int k = n * unif_rand();
    tab[k]++;
  }
  return tab;
}

Тест:

microbenchmark::microbenchmark(
  sort(sample(n, replace = TRUE)),
  tabulate(sample(n, replace = TRUE), n),
  sort_sample(n)
)

Для n = 1e5:

Unit: microseconds
                                   expr      min       lq      mean    median        uq      max neval
        sort(sample(n, replace = TRUE)) 3214.726 3393.606 3667.1001 3507.0525 3716.3560 7007.411   100
 tabulate(sample(n, replace = TRUE), n) 1087.543 1104.215 1245.0722 1136.9085 1218.5865 4265.075   100
                         sort_sample(n)  789.403  812.780  870.2723  837.3445  924.4395 1188.432   100

Для n = 1e6:

Unit: milliseconds
                                   expr      min       lq     mean   median       uq       max neval
        sort(sample(n, replace = TRUE)) 49.96651 52.58784 61.19775 55.09312 58.43035 160.16275   100
 tabulate(sample(n, replace = TRUE), n) 13.74391 14.44253 17.22742 15.99816 17.54367  48.72374   100
                         sort_sample(n) 12.80741 14.40371 17.98320 15.31699 17.53548  63.21692   100

Answer 2

Как упомянуто @Frank в комментариях, имеет смысл использовать tabulate вместо sort. Как только кто-то использует это, имеет смысл подумать о более быстрых методах выборки , как это предусмотрено в моем пакете dqrng :

library(dqrng)
m <- 1e6
bm <- bench::mark(sort(sample.int(m, replace = TRUE)),
                  tabulate(sample.int(m, replace = TRUE)),
                  sort(dqsample.int(m, replace = TRUE)),
                  tabulate(dqsample.int(m, replace = TRUE)),
                  check = FALSE)
bm[, 1:4]
#> # A tibble: 4 x 4
#>   expression                                     min   median `itr/sec`
#>   <bch:expr>                                <bch:tm> <bch:tm>     <dbl>
#> 1 sort(sample.int(m, replace = TRUE))         72.3ms   75.5ms      13.2
#> 2 tabulate(sample.int(m, replace = TRUE))     22.8ms   27.7ms      34.6
#> 3 sort(dqsample.int(m, replace = TRUE))       59.5ms     64ms      15.3
#> 4 tabulate(dqsample.int(m, replace = TRUE))   14.4ms   16.3ms      57.0

^{Создано в 2019-06-27 пакетом Представление (v0.3.0)}

Обратите внимание, что я все еще использую R 3.5 на этой машине. С R 3.6 разница между sample.int и dqsample.int будет больше. Также обратите внимание, что для получения методов быстрой выборки больше не требуется версия разработки dqrng.

Можно также использовать RNG из dqrng через C ++, но это не имеет большого значения по сравнению с tabulate(dqsample.int(...)) по моему опыту:

#include <Rcpp.h>
// [[Rcpp::depends(dqrng, sitmo)]]
#include <dqrng_generator.h>
#include <convert_seed.h>
#include <R_randgen.h>
// [[Rcpp::plugins(cpp11)]]

// [[Rcpp::export]]
Rcpp::IntegerVector sort_sample(uint32_t n) {
    Rcpp::IntegerVector seed(2, dqrng::R_random_int);
    auto rng = dqrng::generator(dqrng::convert_seed<uint64_t>(seed));
    Rcpp::IntegerVector tab(n);
    for (uint32_t i = 0; i < n; i++) {
        uint32_t k = (*rng)(n);
        tab[k]++;
    }
    return tab;
}