outer() and dist() are good for speed on smaller problems but they
require O(length(X)^2) memory. This can slow things down or even
stop the calculations for large problems. You can gain a lot of speed
without the memory problem by summing things up in chunks.
E.g., On a Linux box I compared
fChunk <- function(x) {
ans <- 0
for(i in seq_along(x)[-1]) {
ans <- ans + sum( (x[i] - x[seq_len(i-1)])^2)
}
2*ans
}
with the original algorithm (slightly cleaned up)
fOrig <-function (x) {
ans <- 0
for (i in seq_along(x)[-1]) {
for (j in seq_len(i)) {
ans <- ans + (x[i] - x[j])^2
}
}
2 * ans
}
and the ones based on outer() and dist().
fOuter <- function(x) sum(outer(x, x, FUN=`-`)^2)
fDist <- function(x) 2 * sum(dist(x)^2)
for a vector of length 10000.
> z <- rnorm(10^4)
> t(sapply(list(fOrig=fOrig, fChunk=fChunk, fDist=fDist, fOuter=fOuter),
function(f)tryCatch(system.time(f(z)), error=function(e)NA)[1:3]))
user.self sys.self elapsed
fOrig 90.262 0.000 90.378
fChunk 0.776 0.004 0.779
fDist 1.092 0.276 1.370
fOuter 0.740 1.068 1.855
They all give slightly different answers because the round-off error depends on
the order in which sums and squares are done.
Of course, the Rcpp version has no memory penalty and is faster than any of
them.
Bill Dunlap
Spotfire, TIBCO Software
wdunlap tibco.com
> -----Original Message-----
> From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-project.org] On
> Behalf
> Of S Ellison
> Sent: Tuesday, October 22, 2013 6:08 AM
> To: r-help@r-project.org
> Cc: Ken Knoblauch
> Subject: Re: [R] speeding up "sum of squared differences" calculation
>
> > Conclusion: hard to beat outer() for this purpose in R
> ... unless you use Ken Knoblauch's suggestion of dist() or Rccp.
>
> Nice indeed.
>
>
> S Ellison
>
>
> *******************************************************************
> This email and any attachments are confidential. Any use...{{dropped:8}}
>
> ______________________________________________
> R-help@r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
