为什么排序比R中的序函数慢？

Question

一切都在标题里。我希望order使用sort来查找向量中值的顺序。因此，sort应该比order更快地对向量进行排序，但事实并非如此：

library(microbenchmark)
ss=sample(100,10000,replace=T)
microbenchmark(sort(ss))
microbenchmark(ss[order(ss)])

结果：

> microbenchmark(sort(ss))
Unit: microseconds
    expr     min       lq     mean  median       uq      max neval
 sort(ss) 141.535 144.6415 173.6581 146.358 150.2295 2531.762   100
> microbenchmark(ss[order(ss)])
Unit: microseconds
        expr     min       lq     mean  median       uq     max neval
 ss[order(ss)] 109.198 110.9865 115.6275 111.901 115.3655 197.204   100

使用更大的向量的示例：

ss=sample(100,1e8,replace=T)
microbenchmark(sort(ss), ss[order(ss)], times = 5)
# Unit: seconds
#           expr      min       lq     mean   median       uq      max neval
#       sort(ss) 5.427966 5.431971 5.892629 6.049515 6.207060 6.346633     5
#  ss[order(ss)] 3.381253 3.500134 3.562048 3.518079 3.625778 3.784997     5

Answer 1

默认参数下对NA值的处理不同。在sort中，必须扫描整个向量以获取NA值，然后删除这些值；在order中，只需将它们放在最后。当在这两种情况下都使用参数sort.last = TRUE时，性能基本相同。

ss=sample(100,1e8,replace=T) 
bench::mark(sort(ss), ss[order(ss)], sort(ss, na.last = TRUE))
# A tibble: 3 x 14
  expression    min   mean median    max `itr/sec` mem_alloc  n_gc n_itr total_time result
  <chr>      <bch:> <bch:> <bch:> <bch:>     <dbl> <bch:byt> <dbl> <int>   <bch:tm> <list>
1 sort(ss)   2.610s 2.610s 2.610s 2.610s     0.383 762.940MB     0     1     2.610s <int ~
2 ss[order(~ 1.597s 1.597s 1.597s 1.597s     0.626 762.940MB     0     1     1.597s <int ~
3 sort(ss, ~ 1.592s 1.592s 1.592s 1.592s     0.628 762.940MB     0     1     1.592s <int ~
# ... with 3 more variables: memory <list>, time <list>, gc <list>

Answer 2

因为sort.default()使用order (而不是相反的方式)。

function (x, decreasing = FALSE, na.last = NA, ...) 
{
  if (is.object(x)) 
    x[order(x, na.last = na.last, decreasing = decreasing)]
  else sort.int(x, na.last = na.last, decreasing = decreasing, 
    ...)
}

sort必须确定其方法，然后在直接使用x[order(x)]时一步执行相同的x[order(x)]调用。您可以根据需要增加输入的大小。对于整数向量，x[order(x)]应该总是优于sort(x)。

一年后，@Hugh's answer演示了大部分差异是在NA值的默认处理中实现的。这应该是公认的答案。