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

Answered By – Park

Answer Checked By – Pedro (BugsFixing Volunteer)