Nested rolling sum in vector

Question

I am struggling to produce an efficient code to compute the vector result r result from an input vector v using this function.

    r(i) = \sum_{j=i}^{i-N} [o(i)-o(j)] * exp(o(i)-o(j))

where i loops (from N to M) over the vector v. Size of v is M>>N.

Of course this is feasible with 2 nested for loops, but it is too slow for computational purposes, probably out of fashion and deprecated style...

A MWE:

for (i in c(N+1):length(v)){
  csum <- 0
  for (j in i:c(i-N)) {
      csum <- csum + (v[i]-v[j])*exp(v[i]-v[j]) 
      }
  r[i] <- csum
}

In my real application M > 10^5 and the v vector is indeed several vectors.

I have been trying with nested applications of lapply and rollapply without success. Any suggestion is welcome.

Thanks!

Answer 1

I don't know if it is any more efficient but something you can try:

r[N:M] <- sapply(N:M, function(i) tail(cumsum((v[i]-v[1:N])*exp(v[i]-v[1:N])), 1))

checking that both computations give same results, I got r with your way and r2 with mine, initializing r2 to rep(NA, M) and assessed the similarity:

all((r-r2)<1e-12, na.rm=TRUE)
# [1] TRUE

NOTE: as in @lmo answer, tail(cumsum(...), 1) can be efficiently replaced by just using sum(...):

r[N:M] <- sapply(N:M, function(i) sum((v[i]-v[1:N])*exp(v[i]-v[1:N])))

Answer 2

Here is a method with a single for loop.

# create new blank vector
rr <- rep(NA,M)

for(i in N:length(v)) {
  rr[i] <- sum((v[i] - v[seq_len(N)]) * exp(v[i] - v[seq_len(N)]))
}

check for equality

all.equal(r, rr)
[1] TRUE

You could reduce the number of operations by 1 if you store the difference. This should add a little speed up.

for(i in N:length(v)) {
  x <- v[i] - v[seq_len(N)]
  rr[i] <- sum(x * exp(x))
}