[R] Lagged values problem requiring short solution time

Rui Barradas ruipbarradas at sapo.pt
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:

fun1 <- your code

fun2 <- function(x, delta){
	n <- length(x)                                             # don't need to
create a work y
	if(abs(x[1] - x[n]) < delta) x[1] <- 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[1])), NA),
	fun2=c(y=y2, s=s2), c(diff(c(y2,y2[1])), NA),
	x=c(x, NA), c(diff(c(x,x[1])), 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

Rui Barradas


--
View this message in context: http://r.789695.n4.nabble.com/Lagged-values-problem-requiring-short-solution-time-tp4184566p4186786.html
Sent from the R help mailing list archive at Nabble.com.



More information about the R-help mailing list