From tshort at eprisolutions.com  Sun Jul 30 14:02:19 2006
From: tshort at eprisolutions.com (tshort)
Date: Sun, 30 Jul 2006 05:02:19 -0700 (PDT)
Subject: [Rd] Any interest in "merge" and "by" implementations
 specifically for so
In-Reply-To: <207048BB-90DD-43DA-8FBC-D73544E6E3A8@sympatico.ca>
References: <07820D54-9DDC-42F7-8F32-C931B2B80DE6@sympatico.ca>
	<Pine.GSO.4.31.0607280805550.24504-100000@markov.stats>
	<FFDE23C5-EA11-4E16-B372-012DB00BD589@sympatico.ca>
	<971536df0607281112j43c4ffc0s96d3b4743b93b690@mail.gmail.com>
	<D5EA9DD0-BFC7-45A6-A541-65E8A9E8192C@sympatico.ca>
	<Pine.GSO.4.56.0607281229290.28145@durian.statsci.com>
	<5A40DD7D-3BF4-4451-AC91-9B121BE9901F@sympatico.ca>
	<Pine.GSO.4.56.0607281725120.28145@durian.statsci.com>
	<AAC5E1FB-71BB-46C8-9D51-A72DD25C735E@sympatico.ca>
	<207048BB-90DD-43DA-8FBC-D73544E6E3A8@sympatico.ca>
Message-ID: <5562816.post@talk.nabble.com>


Kevin, starting with your idea of sorting first, you can get some speedups
just using R. Start by comparing the base case that Bill used:

> x <- runif(2e6)
> i <- rep(1:1e6, 2)
> unix.time(res0 <- unlist(lapply(split(x,i), sum))) 
[1] 11.00  0.16 11.28    NA    NA

Now, try sorting and using a loop:

> idx <- order(i)
> xs <- x[idx]
> is <- i[idx]
> res <- array(NA, 1e6)
> idx <- which(diff(is) > 0)
> startidx <- c(1, idx+1)
> endidx <- c(idx, length(xs))
> f1 <- function(x, startidx, endidx, FUN = sum)  {
+   for (j in 1:length(res)) {
+     res[j] <- FUN(x[startidx[j]:endidx[j]])
+   }
+   res
+ }
> unix.time(res1 <- f1(xs, startidx, endidx))
[1] 6.86 0.00 7.04   NA   NA

For the case of sum (or averages), you can vectorize this using cumsum as
follows. This won't work for median or max.

> f2 <- function(x, startidx, endidx)  {
+   cum <- cumsum(x)
+   res <- cum[endidx]
+   res[2:length(res)] <- res[2:length(res)] - cum[endidx[1:(length(res) -
1)]]
+   res
+ }
> unix.time(res2 <- f2(xs, startidx, endidx))
[1] 0.20 0.00 0.21   NA   NA

You can also use Luke Tierney's byte compiler
(http://www.stat.uiowa.edu/~luke/R/compiler/) to speed up the loop for
functions where you can't vectorize:

> library(compiler)
> f3 <- cmpfun(f1)
Note: local functions used: FUN 
> unix.time(res3 <- f3(xs, startidx, endidx))
[1] 3.84 0.00 3.91   NA   NA

- Tom

-- 
View this message in context: http://www.nabble.com/Any-interest-in-%22merge%22-and-%22by%22-implementations-specifically-for-sorted-data--tf2009595.html#a5562816
Sent from the R devel forum at Nabble.com.



[Rd] Any interest in "merge" and "by" implementations specifically for so
tshort