在R中对“样本”函数进行基准测试

Question

我正在对R中的sample函数进行基准测试，并将其与igraph:sample_seq进行比较，结果遇到了奇怪的结果。

当我运行类似以下的代码时：

library(microbenchmark)
library(igraph)
set.seed(1234)
N <- 55^4
M <- 500
(mbm <- microbenchmark(v1 = {sample(N,M)}, 
                       v2 = {igraph::sample_seq(1,N,M)}, times=50))

我得到了这样的结果：

Unit: microseconds
 expr       min        lq        mean     median        uq       max neval
   v1 21551.475 22655.996 26966.22166 23748.2555 28340.974 47566.237    50
   v2    32.873    37.952    82.85238    81.7675    96.141   358.277    50

但是当我运行时，例如：

set.seed(1234)
N <- 100^4
M <- 500
(mbm <- microbenchmark(v1 = {sample(N,M)}, 
                      v2 = {igraph::sample_seq(1,N,M)}, times=50))

我对sample得到了更快的结果：

Unit: microseconds
 expr    min     lq     mean  median     uq     max neval
   v1 52.165 55.636 64.70412 58.2395 78.636  88.120    50
   v2 39.174 43.504 62.09600 53.5715 73.253 176.419    50

似乎当N是10的某个次方（或其他特殊数字？）时，sample比那些不是10的某个次方的较小N要快得多。这是期望的行为吗，还是我漏掉了什么？

- passerby51

Answer 1

sample() 或者说 sample.int() 在满足某些条件时，默认使用哈希算法，其中之一是 n > 1e7。如果第二个基准测试在不使用哈希的情况下重新运行，则会发现它比 igraph 函数慢得多。

set.seed(1234)
N2 <- 100^4
M <- 500
(mbm <- microbenchmark(v1 = {sample.int(N2,M, useHash = FALSE)}, 
                       v2 = {igraph::sample_seq(1,N2,M)}, times=50))

Unit: microseconds
 expr        min         lq         mean     median         uq       max neval cld
   v1 144297.936 150368.649 167224.95664 154283.077 157832.520 407710.78    50   b
   v2     61.218     65.392     92.35544     87.885    118.262    148.87    50  a 

从useHash参数的文档中得知：

逻辑值，指示是否应使用算法的哈希版本。仅适用于replace = FALSE，prob = NULL和size <= n/2，并且应该在大n的情况下使用，因为useHash=FALSE将使用与n成比例的内存。

- Ritchie Sacramento

---

有趣！看起来就是这样。 - passerby51

现在，我想知道是否有可能比较哈希“sample.int”使用的内存量与igraph::sample_seq (?)。 - passerby51