[R] Recursive decreasing sequences

[Achim Zeileis]

On Fri, 20 Oct 2006 15:16:12 -0500 Marc Schwartz wrote:

> > Range <- c(2:6)
> 
> Gack....
> 
> Disregard the 'c' and parens there.  Left over from a first attempt
> at a solution using c(2, 6)...

Like this one:
  myseq4 <- function(start, end)
    unlist(lapply(start:end, function(x) x:end))
which is very similar to Marc's that was essentially
  myseq3 <- function(start, end) {
    rval <- start:end
    unlist(sapply(seq(along = rval), function(x) rval[x]:max(rval)))
  }

The problem with Julian's original suggestion
  myseq1 <- function(start, end) {
    rval <- integer(0)
    for(i in start:end) rval <- c (rval, i:end)
    return(rval)
  }
is that rval is recursively grown which becomes really slow (as
documented in various places). The program can already be improved
significantly if this is avoided by creating a sufficiently large
vector initially:
  myseq2 <- function(start, end) {
    rval <- integer((end-start+1) * (end-start+2)/2)
    j <- 1
    for(i in start:end) {
      rval[j:(j+end-i)] <- i:end
      j <- j+end-i+1
    }
    return(rval)
  }

And on my machine I obtain the following timings:

R> system.time(myseq1(2, 1000))
[1] 7.150 1.110 8.312 0.000 0.000
R> system.time(myseq2(2, 1000))
[1] 0.060 0.000 0.059 0.000 0.000
R> system.time(myseq3(2, 1000))
[1] 0.050 0.000 0.048 0.000 0.000
R> system.time(myseq4(2, 1000))
[1] 0.020 0.010 0.028 0.000 0.000

Thus, the main problem was growing the return value recursively. My
last suggestion seems to be slightly faster than the previous ones...

hth,
Z