# [R] Lagged values problem requiring short solution time

Mon Dec 12 18:17:25 CET 2011

```Kevin,

Your problem seems to have three restrictions: (1) abs(x[i] - x[i-1]) >=
delta (2) y[i] >= x[i]
and (3) minimize sum(y-x). If this is the case I believe I have a better
solution, with a smaller sum
and in much less time.
The problem is restriction (2). If the diffs are negative you can't subtract
negative,
the new y[i] would be less than x[i]. So, add. Here is the code:

fun2 <- function(x, delta){
n <- length(x)                                             # don't need to
create a work y
if(abs(x - x[n]) < delta) x <- x[n] + delta # special case, wraps
around.
ix <- which(abs(x[2:n] - x[2:n - 1]) < delta)     # make up an index vector
x[ix] <- x[ix - 1] + delta                                # and use it.
x
}

# First test both

x = runif(10,1,5)
y1 <- fun1(x, delta=0.75); s1 <- sum(y1 - x)
y2 <- fun2(x, delta=0.75); s2 <- sum(y2 - x)
# and display results
rbind(fun1=c(y=y1, s=s1), c(diff(c(y1,y1)), NA),
fun2=c(y=y2, s=s2), c(diff(c(y2,y2)), NA),
x=c(x, NA), c(diff(c(x,x)), NA))

# now time them!
x <- runif(10^5, 1, 5)
t1 <- system.time(for(i in 1:10^2) y1 <- fun1(x, delta=0.75))[c(1, 3)]
t2 <- system.time(for(i in 1:10^2) y2 <- fun2(x, delta=0.75))[c(1, 3)]
rbind(fun1=t1, fun2=t2, ratio=t1/t2)
#
# Sample run
#
user.self  elapsed
fun1   26.99000 29.60000
fun2    0.92000  1.09000
ratio  29.33696 27.15596

29 times faster!

I hope it's usefull