dista performance

[ggrothendieck]

It may be possible to speed up dista B is twice as fast as dista in the code below. See comments below this link

library(microbenchmark)
library(Rfast)
library(collapse)

m1 <- cbind(a=c(1,1,1,1,1,1,1,1), b=c(1,2,3,1,2,3,1,2), c=c(0,0,1,0,0,1,0,0))
m2 <- cbind(a=c(1,2,1,2,1,2,1,2), b=c(1,2,3,1,2,3,1,2), c=c(0,0,1,0,0,1,0,0))

microbenchmark(
  dista = dista.res <- dista(m1, m2, square = TRUE),
  B = B.res <- setop(rowsums(m1^2) - 2*tcrossprod(m1, m2), "+", rowsums(m2^2), 
		 rowwise = TRUE))
## Unit: microseconds
##   expr  min    lq   mean median    uq   max neval
##  dista 66.4 68.05 73.320   71.4 72.65 139.4   100
##      B 27.4 28.70 34.921   33.2 33.85 174.2   100

all.equal(dista.res, B.res)
# [1] TRUE

[ajinkya-k]

I have been testing this code and there are situations where it can lead to negative distances. I am unsure why that is.

[vonGameTheory]

This is a bit old, but I just had to comment. This speedup is amazing! I never would have come up with this trick, and I've often lamented that if I could just get euclidean distances between large matrices faster, it would be great for certain applications. (I'm always playing around with things like nearest neighbors and diffusion maps, etc, but sometimes the distance calculations are just too slow.)

However, it is less numerically precise (because of the row summing I think) if you have a lot of features, and so that's where the sometimes tiny negative results come in along the diagonal or if you have other duplicate rows. (i.e. when the distance is zero, it might come back as a tiny negative, and so therefore all results are just less precise). But if you can live with the imprecision (I can), then after sqrt() to get true euclidean distance, I can just set the NaNs to zero and that's fine. It is still way faster -- on the large matrices I work with, the speedup is way more than 2x.

I don't know if it appropriate for Rfast with this level of imprecision (and those negatives would have to be dealt with), but thanks so much for pointing out this idea anyway. Love it!