# [SOLVED] Fastest way to construct the sequence `c(1:1, 1:2, …, 1:n)`

## Issue

For a given positive integer `n`, I want to know the fastest base R (not `Rcpp`) algorithm for constructing the integer vector `c(1:1, 1:2, ..., 1:n)`, which has length `n*(n+1)/2`. There are bonus points for fast and memory-efficient algorithms, since I ultimately want to avoid allocating a vector of length `n*n`.

I’m aware of at least two approaches:

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

the latter being particularly inefficient since it allocates two integer vectors of length `n*n`.

Note that if we assign the value `.col(c(n, n))` to `J` above, then we obtain the sequence `1 2 2 3 3 3 4 4 4 4 ...`. This sequence can be constructed fast and efficiently with `{i <- seq_len(n); rep.int(i, i)}`.

I am wondering if a similarly fast (or faster) algorithm exists in the `.row(c(n, n))` case, or if `unlist``lapply` is optimal from a base R standpoint.

FWIW, here is a benchmark of the three procedures I’ve mentioned so far:

``````## 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
``````

(I’m aware that `f1` is pretty close to `f0` here, but is there something better than `f1`?)

## Solution

I’m not sure what you’re aware of, but if function from `base` is okay, try `sequence`.

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

It seems it’s almost 2~3 times faster than `f0`