наиболее эффективный расчет R косинус - PullRequest
Новая
       8

наиболее эффективный расчет R косинус

7 голосов
/ 17 ноября 2011

У меня есть два вектора значений и один вектор весов, и мне нужно вычислить косинусное сходство.По сложным причинам я могу рассчитать только косинус для одной пары за раз.Но я должен сделать это много миллионов раз.

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))
}

работает, но я хочу попытаться добиться от него большей производительности.

Пример данных: 

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

Этот вопрос указывает на наличие других предопределенных косинусных функций, доступных в R, но ничего не говорит об их относительной эффективности.

1 Ответ

7 голосов
/ 17 ноября 2011

Все функции, которые вы используете, .Primitive (поэтому уже вызываете скомпилированный код напрямую), поэтому будет сложно найти согласованный выигрыш в скорости вне перестроения R с оптимизированным BLAS. С учетом сказанного, вот один вариант, который может быть быстрее для больших векторов: 

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:

Профилирование показывает, что на умножение каждого вектора на весовой вектор уходит совсем немного времени. 

> 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

Если вы сможете выполнить взвешивание до того, как вызовете функцию миллионы раз, это может сэкономить вам немного времени. cosine_calc3 незначительно быстрее, чем ваша исходная функция с маленькими векторами. Байт-компиляция функции должна дать вам еще одно предельное ускорение. 

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
...