most efficient R cosine calculation

Question

I have two vectors of values and one vector of weights, and I need to calculate the cosine similarity. For complicated reasons, I can only calculate the cosine for one pair at a time. But I have to do it many millions of times.

cosine_calc <- function(a,b,wts) {
  #scale both vectors by the weights, then compute the cosine of the scaled vectors
  a = a*wts
  b = b*wts
  (a %*% b)/(sqrt(a%*%a)*sqrt(b%*%b))
}

works, but I want to try to eke better performance out of it.

Example data:

a = c(-1.2092420, -0.7053822, 1.4364633, 1.3612304, -0.3029147, 1.0319704, 0.6707610, -2.2128987, -0.9839970, -0.4302205)
b = c(-0.69042619, 0.05811749, -0.17836802, 0.15699691, 0.78575477, 0.27925779, -0.08552864, -1.31031219, -1.92756861, -1.36350112)
w = c(0.26333839, 0.12803180, 0.62396023, 0.37393705, 0.13539926, 0.09199102, 0.37347546, 1.36790007, 0.64978409, 0.46256891)
> cosine_calc(a,b,w)[,1]
[1,] 0.8390671

This question points out that there are other predefined cosine functions available in R, but says nothing about their relative efficiency.

only being able to do it one pair at a time is going to be a major bottleneck ... — Ben Bolker, Nov 16 '11 at 21:23
I hate to break it to you, but in my experience, R doesn't seem to be built for performance (relatively speaking). If this data is from a relational database, you might want to consider computing the similarities there and then exporting to R. Most of what I use R for is small-scale analysis (ie on data sets after I've done a significant amount of aggregation) and producing graphics. — , Nov 16 '11 at 21:42
Why don't you go ahead and benchmark the examples listed in http://stackoverflow.com/questions/2535234/find-cosine-similarity-in-r/2536149#2536149 (i.e. the question you linked; @JoshUlrich shows you how in his answer) and see for yourself? — Ben Bolker, Nov 16 '11 at 22:05
PS it might not matter *that* much, but wouldn't `sqrt((a%*%a)*(b%*%b))` be marginally more efficient than taking the square root twice? — Ben Bolker, Nov 16 '11 at 22:07
@jack I would love to see a world where computing in a database is faster than computing in a statistical programming environment — hadley, Nov 16 '11 at 22:36
@hadley - Well, if the raw data resides in a database, it can often be quicker to perform computations in the database than to export the data and do the calculations elsewhere (hence the concept of in-database analytics). — , Nov 16 '11 at 22:39

Joshua Ulrich · Accepted Answer · 2011-11-16T23:20:58.057

All the functions you're using are .Primitive (therefore already call compiled code directly), so it will be hard to find consistent speed gains outside of re-building R with an optimized BLAS. With that said, here is one option that might be faster for larger vectors:

cosine_calc2 <- function(a,b,wts) {
  a = a*wts
  b = b*wts
  crossprod(a,b)/sqrt(crossprod(a)*crossprod(b))
}

all.equal(cosine_calc1(a,b,w),cosine_calc2(a,b,w))
# [1] TRUE

# Check some timings
library(rbenchmark)
# cosine_calc2 is slower on my machine in this case
benchmark(
  cosine_calc1(a,b,w),
  cosine_calc2(a,b,w), replications=1e5, columns=1:4 )
#                    test replications user.self sys.self
# 1 cosine_calc1(a, b, w)       100000      1.06     0.02
# 2 cosine_calc2(a, b, w)       100000      1.21     0.00

# but cosine_calc2 is faster for larger vectors
set.seed(21)
a <- rnorm(1000)
b <- rnorm(1000)
w <- runif(1000)
benchmark(
  cosine_calc1(a,b,w),
  cosine_calc2(a,b,w), replications=1e5, columns=1:4 )
#                    test replications user.self sys.self
# 1 cosine_calc1(a, b, w)       100000      3.83        0
# 2 cosine_calc2(a, b, w)       100000      2.12        0

UPDATE:

Profiling reveals that quite a bit of time is spent multiplying each vector by the weight vector.

> Rprof(); for(i in 1:100000) cosine_calc2(a,b,w); Rprof(NULL); summaryRprof()
$by.self
             self.time self.pct total.time total.pct
*                 0.80    45.98       0.80     45.98
crossprod         0.56    32.18       0.56     32.18
cosine_calc2      0.32    18.39       1.74    100.00
sqrt              0.06     3.45       0.06      3.45

$by.total
             total.time total.pct self.time self.pct
cosine_calc2       1.74    100.00      0.32    18.39
*                  0.80     45.98      0.80    45.98
crossprod          0.56     32.18      0.56    32.18
sqrt               0.06      3.45      0.06     3.45

$sample.interval
[1] 0.02

$sampling.time
[1] 1.74

If you can do the weighting before you have to call the function millions of times, it could save you quite a bit of time. cosine_calc3 is marginally faster than your original function with small vectors. Byte-compiling the function should give you another marginal speedup.

cosine_calc3 <- function(a,b) {
  crossprod(a,b)/sqrt(crossprod(a)*crossprod(b))
}
A = a*w
B = b*w
# Run again on the 1000-element vectors
benchmark(
  cosine_calc1(a,b,w),
  cosine_calc2(a,b,w),
  cosine_calc3(A,B), replications=1e5, columns=1:4 )
#                    test replications user.self sys.self
# 1 cosine_calc1(a, b, w)       100000      3.85     0.00
# 2 cosine_calc2(a, b, w)       100000      2.13     0.02
# 3    cosine_calc3(A, B)       100000      1.31     0.00

Am I reading that results right? 100,000 reps of 1,000 inputs takes 3 seconds? Seems hard to believe this could be a bottleneck in someone's code! — hadley, Nov 16 '11 at 22:37

most efficient R cosine calculation

1 Answers1

Linked