减少部分排序

Question

如上所述?sort,如果参数partial不是NULL,则采用包含结果元素的索引,这些索引将通过部分排序放置在排序数组中的正确位置.您可以在R中读取排序函数的Argument"partial"以 获取详细信息.因此,在情况下,我需要找到最小的5个号码中x <- sample(1:100, 50),然后

sort(x, partial = 1:5)[1:5]

会快于

sort(x)[1:5]

但是,如何通过部分排序找到最大的5个数字？直觉上,我尝试使用:

sort(x, partial = 1:5, decreasing = T)

但它得到了

sort.int中的错误(x,na.last = na.last,减少=减少,...):部分排序的不受支持的选项

因此,我的问题是如何在这种情况下实现效率的效果.

Answer 1

您可能仍然受益于速度提升，例如（假设数字数据）：

-sort(-x, partial = 1:5)[1:5]

基准测试：

set.seed(3)
x <- sample(1:100000, 500000, replace = TRUE)

bench::mark(
  snoram = -sort(-x, partial = 1:5)[1:5],
  OP = sort(x, decreasing = TRUE)[1:5],
  sotos_check = x[order(x, decreasing = TRUE)][1:5],
  jogo = {p <- length(x) - 0:4; sort(x, partial = p)[p]}
)
# A tibble: 4 x 14
  expression       min     mean   median      max `itr/sec` mem_alloc  n_gc n_itr total_time result    memory             time     gc               
  <chr>       <bch:tm> <bch:tm> <bch:tm> <bch:tm>     <dbl> <bch:byt> <dbl> <int>   <bch:tm> <list>    <list>             <list>   <list>           
1 snoram        6.87ms   7.77ms   7.43ms  15.04ms     129.     5.72MB     9    34      264ms <int [5]> <Rprofmem [3 x 3]> <bch:tm> <tibble [43 x 3]>
2 OP            17.4ms  18.96ms  18.56ms  24.37ms      52.7    3.81MB     3    21      398ms <int [5]> <Rprofmem [2 x 3]> <bch:tm> <tibble [24 x 3]>
3 sotos_check  14.65ms  17.07ms  16.48ms  25.58ms      58.6    3.81MB     4    23      393ms <int [5]> <Rprofmem [2 x 3]> <bch:tm> <tibble [27 x 3]>
4 jogo          4.98ms   5.45ms   5.35ms   8.91ms     184.     3.81MB     6    37      201ms <int [5]> <Rprofmem [2 x 3]> <bch:tm> <tibble [43 x 3]>

Answer 2

您可以从排序的向量中获取尾部:

set.seed(42)
x <- sample(1:100, 50)
# sort(x, partial = 1:5)[1:5] ## head

p <- length(x)+1 - (1:5) ## tail
sort(x, partial = p)[p]

如果您愿意,可以使用反转结果 rev()