构建序列 `c(1:1, 1:2, ..., 1:n)` 的最快方法

Question

对于给定的正整数n，我想知道构造整数向量c(1:1, 1:2, ..., 1:n)的最快基数R（不是Rcpp）算法，其长度为[=17] =].快速和内存高效算法有加分项，因为我最终想避免分配长度为 n*n.

的向量

我知道至少有两种方法：

unlist(lapply(seq_len(n), seq_len), FALSE, FALSE)
{J <- .row(c(n, n)); J[upper.tri(J, TRUE)]}

后者效率特别低，因为它分配两个个长度为 n*n.

的整数向量

注意，如果我们将值.col(c(n, n))赋给上面的J，那么我们得到的是序列1 2 2 3 3 3 4 4 4 4 ...。这个序列可以用{i <- seq_len(n); rep.int(i, i)}快速有效地构建。

我想知道 .row(c(n, n)) 情况下是否存在类似的快速（或更快）算法，或者从基础 R 的角度来看 unlist-lapply 是否是最优的。

FWIW，这是我目前提到的三个程序的基准：

## Seemingly optimal for 1 2 2 3 3 3 4 4 4 4 ...
f0 <- function(n) {i <- seq_len(n); rep.int(i, i)}
## Candidates for 1 1 2 1 2 3 1 2 3 4 ... (the sequence I actually want)
f1 <- function(n) unlist(lapply(seq_len(n), seq_len), FALSE, FALSE)
f2 <- function(n) {J <- .row(c(n, n)); J[upper.tri(J, TRUE)]}

n <- 1000L
microbenchmark::microbenchmark(f0(n), f1(n), f2(n), times = 10000L)

Unit: milliseconds
  expr      min       lq     mean   median       uq      max neval
 f0(n) 1.711873 1.797891 2.112043 1.810273 1.836636 14.96644 10000
 f1(n) 1.986737 2.108630 2.472612 2.148195 2.214369 15.16282 10000
 f2(n) 3.785981 4.624821 5.551115 5.051405 5.861954 17.28740 10000

（我知道 f1 和 f0 很接近，但是还有比 f1 更好的东西吗？）

Answer 1

我不确定你知道什么，但如果 base 的功能没问题，请尝试 sequence。

f3 <- function(n) {sequence(1:n)}

好像比f0快了将近2~3倍

Answer 2

我认为 sequence 是您想要的（如果您不打算使用 Rcpp 以获得更快的版本）

f1 <- function(n) unlist(lapply(seq_len(n), seq_len), FALSE, FALSE)
f2 <- function(n) {
  J <- .row(c(n, n))
  J[upper.tri(J, TRUE)]
}
f3 <- function(n) {
  v <- 1:n
  data.table::rowid(rep.int(v, v))
}
f4 <- function(n) sequence(1:n)

n <- 1000L
microbenchmark::microbenchmark(f1(n), f2(n), f3(n), f4(n), check = "identical")

基准测试

> microbenchmark::microbenchmark(f1(n), f2(n), f3(n), f4(n), check = "identical")
Unit: microseconds
  expr    min       lq      mean  median       uq     max neval
 f1(n) 3928.8  4144.50  5185.839  4227.5  4289.15 67457.1   100
 f2(n) 9490.3 10083.90 14415.777 12951.0 15080.50 78014.2   100
 f3(n) 8083.5  8572.10 12154.922  9063.0  9534.45 75408.7   100
 f4(n)  213.9   425.05   787.637   442.6   494.00  7844.4   100

Answer 3

这2个也可能是选项-

n <- 5

unlist(purrr::map(seq(5), ~seq(.x)))
#>  [1] 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5

unlist(mapply(FUN = function(.x) seq(.x), seq(n)))
#>  [1] 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5

^{由 reprex package (v2.0.1)}

于 2021-12-10 创建

构建序列 `c(1:1, 1:2, ..., 1:n)` 的最快方法

Fastest way to construct the sequence `c(1:1, 1:2, ..., 1:n)`

performance

r