What's the efficient way to multiply two arrays and get sum of multiply values in Ruby? I have two arrays in Ruby:
用Ruby将两个数组相乘并得到乘法值的和的有效方法是什么?我有两个Ruby数组:
array_A = [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9]
array_B = [3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4]
My aim is to get the sum value of array_A * array_B, i.e., 1*3 + 2*2 + 1*4 + ... + 8*5 + 9*4.
我的目的是得到array_A * array_B的和值，即，1*3 + 2*2 + 1*4 +…+ 8 * 5 + 9 * 4。
Because I need to calculate them million times in my apps, what's the most efficient way to do such calculations?
因为我需要在我的应用程序中计算上百万次，那么最有效的计算方法是什么呢?
It's just like a matrix calcuation: 1* N matrix * N*1 matrix or a vector dot product.
它就像矩阵计算:1* N矩阵* N*1矩阵或者向量点积。
9 个解决方案
#1
20
Update
更新
I've just updated benchmarks according to new comments. Following Joshua's comment, the inject method will gain a 25% speedup, see array walking without to_a in the table below.
我刚刚根据新的评论更新了基准。在Joshua的评论之后，inject方法将获得25%的加速，见下面表格中没有to_a的数组遍历。
However since speed is the primary goal for the OP we have a new winner for the contest which reduces runtime from .34 to .22 in my benchmarks.
但是，由于速度是OP的主要目标，因此我们有一个新的获胜者，在我的基准测试中，它将运行时间从.34减少到.22。
I still prefer inject method because it's more ruby-ish, but if speed matters then the while loop seems to be the way.
我仍然喜欢注入方法，因为它更像红宝石，但是如果速度很重要，那么while循环似乎就是这样。
New Answer
新回答
You can always benchmark all these answers, I did it for curiosity:
你可以把所有这些答案作为基准，我是出于好奇才这么做的:
> ./matrix.rb
Rehearsal --------------------------------------------------------------
matrix method 1.500000 0.000000 1.500000 ( 1.510685)
array walking 0.470000 0.010000 0.480000 ( 0.475307)
array walking without to_a 0.340000 0.000000 0.340000 ( 0.337244)
array zip 0.590000 0.000000 0.590000 ( 0.594954)
array zip 2 0.500000 0.000000 0.500000 ( 0.509500)
while loop 0.220000 0.000000 0.220000 ( 0.219851)
----------------------------------------------------- total: 3.630000sec
user system total real
matrix method 1.500000 0.000000 1.500000 ( 1.501340)
array walking 0.480000 0.000000 0.480000 ( 0.480052)
array walking without to_a 0.340000 0.000000 0.340000 ( 0.338614)
array zip 0.610000 0.010000 0.620000 ( 0.625805)
array zip 2 0.510000 0.000000 0.510000 ( 0.506430)
while loop 0.220000 0.000000 0.220000 ( 0.220873)
Simple array walking wins, Matrix method is worse because it includes object instantiation. I think that if you want to beat the
inject
while method (to beat here means an order of magnitude fastest) you need to implement a C extension and bind it in your ruby program.
简单的数组步行获胜，矩阵方法更糟，因为它包括对象实例化。我认为，如果您想要打败inject while方法(在这里beat的意思是最快的顺序)，您需要实现一个C扩展并将它绑定到您的ruby程序中。
Here it's the script I've used
这是我用过的脚本
#!/usr/bin/env ruby
require 'benchmark'
require 'matrix'
array_A = [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9]
array_B = [3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4]
def matrix_method a1, a2
(Matrix.row_vector(a1) * Matrix.column_vector(a2)).element(0,0)
end
n = 100000
Benchmark.bmbm do |b|
b.report('matrix method') { n.times { matrix_method(array_A, array_B) } }
b.report('array walking') { n.times { (0...array_A.count).to_a.inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array walking without to_a') { n.times { (0...array_A.count).inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array zip') { n.times { array_A.zip(array_B).map{|i,j| i*j }.inject(:+) } }
b.report('array zip 2') { n.times { array_A.zip(array_B).inject(0) {|r, (a, b)| r + (a * b)} } }
b.report('while loop') do
n.times do
sum, i, size = 0, 0, array_A.size
while i < size
sum += array_A[i] * array_B[i]
i += 1
end
sum
end
end
end
#2
5
Walking through each element should be a must
遍历每个元素应该是必须的
(0...array_A.count).inject(0) {|r, i| r + array_A[i]*array_B[i]}
#3
3
I would start simple and use the Ruby matrix class:
我将从简单开始，使用Ruby矩阵类:
require 'matrix'
a = Matrix.row_vector( [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9])
b = Matrix.column_vector([3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4])
result= a * b
puts result.element(0,0)
If this turns out to be too slow, then do the exact same method but with an external math library.
如果结果是太慢了，那么使用一个外部数学库来执行同样的方法。
#4
3
This is how I would do it
我就是这样做的
array_A.zip(array_B).map{|i,j| i*j }.inject(:+)
#5
1
This is another way:
这是另一种方式:
array_A.zip(array_B).inject(0) {|r, (a, b)| r + (a * b)}
#6
1
Since speed is our primary criterion, I'm going to submit this method as it's fastest according to Peter's benchmarks.
由于速度是我们的主要标准，我将提交这个方法，因为它是根据Peter的基准速度最快的。
sum, i, size = 0, 0, a1.size
while i < size
sum += a1[i] * a2[i]
i += 1
end
sum
#7
1
Try the NMatrix gem. It is a numerical computation library. I think it uses the same C and C++ libraries that Octave and Matlab uses.
试NMatrix宝石。它是一个数值计算库。我认为它使用了和Octave和Matlab相同的C和c++库。
You would be able to do the matrix multiplication like this:
你可以这样做矩阵乘法:
require 'nmatrix'
array_A = [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9]
array_B = [3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4]
vec_a = array_A.to_nm([1,array_A.length]) # create an NMatrix
vec_b = array_B.to_nm([1,array_B.length])
sum = vec_a.dot(vec_b.transpose)
I am not sure how the speed will compare using pure Ruby but I imagine it to be faster, especially for large and sparse vectors.
我不确定使用纯Ruby的速度会如何比较，但我认为它会更快，特别是对于大型和稀疏的向量。
#8
0
array1.zip(array2).map{|x| x.inject(&:*)}.sum
#9
0
EDIT: Vector is not fastest (Marc Bollinger is totally right).
编辑:Vector不是最快的(Marc Bollinger完全正确)。
Here is the modified code with vector and n-times:
这是矢量和n次的修改码:
require 'benchmark'
require 'matrix'
array_A = [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9]
array_B = [3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4]
vector_A = Vector[*array_A]
vector_B = Vector[*array_B]
def matrix_method a1, a2
(Matrix.row_vector(a1) * Matrix.column_vector(a2)).element(0,0)
end
def vector_method a1, a2
a1.inner_product(a2)
end
n = 100000
Benchmark.bmbm do |b|
b.report('matrix method') { n.times { matrix_method(array_A, array_B) } }
b.report('array walking') { n.times { (0...array_A.count).to_a.inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array walking without to_a') { n.times { (0...array_A.count).inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array zip') { n.times { array_A.zip(array_B).map{|i,j| i*j }.inject(:+) } }
b.report('array zip 2') { n.times { array_A.zip(array_B).inject(0) {|r, (a, b)| r + (a * b)} } }
b.report('while loop') do
n.times do
sum, i, size = 0, 0, array_A.size
while i < size
sum += array_A[i] * array_B[i]
i += 1
end
sum
end
end
b.report('vector') { n.times { vector_method(vector_A, vector_B) } }
end
And the results:
结果:
Rehearsal --------------------------------------------------------------
matrix method 0.860000 0.010000 0.870000 ( 0.911755)
array walking 0.290000 0.000000 0.290000 ( 0.294779)
array walking without to_a 0.190000 0.000000 0.190000 ( 0.215780)
array zip 0.420000 0.010000 0.430000 ( 0.441830)
array zip 2 0.340000 0.000000 0.340000 ( 0.352058)
while loop 0.080000 0.000000 0.080000 ( 0.085314)
vector 0.310000 0.000000 0.310000 ( 0.325498)
----------------------------------------------------- total: 2.510000sec
user system total real
matrix method 0.870000 0.020000 0.890000 ( 0.952630)
array walking 0.290000 0.000000 0.290000 ( 0.340443)
array walking without to_a 0.220000 0.000000 0.220000 ( 0.240651)
array zip 0.400000 0.010000 0.410000 ( 0.441829)
array zip 2 0.330000 0.000000 0.330000 ( 0.359365)
while loop 0.080000 0.000000 0.080000 ( 0.090099)
vector 0.300000 0.010000 0.310000 ( 0.325903)
------
Too bad. :(
太糟糕了。:(
#1
20
Update
更新
I've just updated benchmarks according to new comments. Following Joshua's comment, the inject method will gain a 25% speedup, see array walking without to_a in the table below.
我刚刚根据新的评论更新了基准。在Joshua的评论之后，inject方法将获得25%的加速，见下面表格中没有to_a的数组遍历。
However since speed is the primary goal for the OP we have a new winner for the contest which reduces runtime from .34 to .22 in my benchmarks.
但是，由于速度是OP的主要目标，因此我们有一个新的获胜者，在我的基准测试中，它将运行时间从.34减少到.22。
I still prefer inject method because it's more ruby-ish, but if speed matters then the while loop seems to be the way.
我仍然喜欢注入方法，因为它更像红宝石，但是如果速度很重要，那么while循环似乎就是这样。
New Answer
新回答
You can always benchmark all these answers, I did it for curiosity:
你可以把所有这些答案作为基准，我是出于好奇才这么做的:
> ./matrix.rb
Rehearsal --------------------------------------------------------------
matrix method 1.500000 0.000000 1.500000 ( 1.510685)
array walking 0.470000 0.010000 0.480000 ( 0.475307)
array walking without to_a 0.340000 0.000000 0.340000 ( 0.337244)
array zip 0.590000 0.000000 0.590000 ( 0.594954)
array zip 2 0.500000 0.000000 0.500000 ( 0.509500)
while loop 0.220000 0.000000 0.220000 ( 0.219851)
----------------------------------------------------- total: 3.630000sec
user system total real
matrix method 1.500000 0.000000 1.500000 ( 1.501340)
array walking 0.480000 0.000000 0.480000 ( 0.480052)
array walking without to_a 0.340000 0.000000 0.340000 ( 0.338614)
array zip 0.610000 0.010000 0.620000 ( 0.625805)
array zip 2 0.510000 0.000000 0.510000 ( 0.506430)
while loop 0.220000 0.000000 0.220000 ( 0.220873)
Simple array walking wins, Matrix method is worse because it includes object instantiation. I think that if you want to beat the
inject
while method (to beat here means an order of magnitude fastest) you need to implement a C extension and bind it in your ruby program.
简单的数组步行获胜，矩阵方法更糟，因为它包括对象实例化。我认为，如果您想要打败inject while方法(在这里beat的意思是最快的顺序)，您需要实现一个C扩展并将它绑定到您的ruby程序中。
Here it's the script I've used
这是我用过的脚本
#!/usr/bin/env ruby
require 'benchmark'
require 'matrix'
array_A = [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9]
array_B = [3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4]
def matrix_method a1, a2
(Matrix.row_vector(a1) * Matrix.column_vector(a2)).element(0,0)
end
n = 100000
Benchmark.bmbm do |b|
b.report('matrix method') { n.times { matrix_method(array_A, array_B) } }
b.report('array walking') { n.times { (0...array_A.count).to_a.inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array walking without to_a') { n.times { (0...array_A.count).inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array zip') { n.times { array_A.zip(array_B).map{|i,j| i*j }.inject(:+) } }
b.report('array zip 2') { n.times { array_A.zip(array_B).inject(0) {|r, (a, b)| r + (a * b)} } }
b.report('while loop') do
n.times do
sum, i, size = 0, 0, array_A.size
while i < size
sum += array_A[i] * array_B[i]
i += 1
end
sum
end
end
end
#2
5
Walking through each element should be a must
遍历每个元素应该是必须的
(0...array_A.count).inject(0) {|r, i| r + array_A[i]*array_B[i]}
#3
3
I would start simple and use the Ruby matrix class:
我将从简单开始，使用Ruby矩阵类:
require 'matrix'
a = Matrix.row_vector( [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9])
b = Matrix.column_vector([3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4])
result= a * b
puts result.element(0,0)
If this turns out to be too slow, then do the exact same method but with an external math library.
如果结果是太慢了，那么使用一个外部数学库来执行同样的方法。
#4
3
This is how I would do it
我就是这样做的
array_A.zip(array_B).map{|i,j| i*j }.inject(:+)
#5
1
This is another way:
这是另一种方式:
array_A.zip(array_B).inject(0) {|r, (a, b)| r + (a * b)}
#6
1
Since speed is our primary criterion, I'm going to submit this method as it's fastest according to Peter's benchmarks.
由于速度是我们的主要标准，我将提交这个方法，因为它是根据Peter的基准速度最快的。
sum, i, size = 0, 0, a1.size
while i < size
sum += a1[i] * a2[i]
i += 1
end
sum
#7
1
Try the NMatrix gem. It is a numerical computation library. I think it uses the same C and C++ libraries that Octave and Matlab uses.
试NMatrix宝石。它是一个数值计算库。我认为它使用了和Octave和Matlab相同的C和c++库。
You would be able to do the matrix multiplication like this:
你可以这样做矩阵乘法:
require 'nmatrix'
array_A = [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9]
array_B = [3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4]
vec_a = array_A.to_nm([1,array_A.length]) # create an NMatrix
vec_b = array_B.to_nm([1,array_B.length])
sum = vec_a.dot(vec_b.transpose)
I am not sure how the speed will compare using pure Ruby but I imagine it to be faster, especially for large and sparse vectors.
我不确定使用纯Ruby的速度会如何比较，但我认为它会更快，特别是对于大型和稀疏的向量。
#8
0
array1.zip(array2).map{|x| x.inject(&:*)}.sum
#9
0
EDIT: Vector is not fastest (Marc Bollinger is totally right).
编辑:Vector不是最快的(Marc Bollinger完全正确)。
Here is the modified code with vector and n-times:
这是矢量和n次的修改码:
require 'benchmark'
require 'matrix'
array_A = [1, 2, 1, 4, 5, 3, 2, 6, 5, 8, 9]
array_B = [3, 2, 4, 2, 5, 1, 3, 3, 7, 5, 4]
vector_A = Vector[*array_A]
vector_B = Vector[*array_B]
def matrix_method a1, a2
(Matrix.row_vector(a1) * Matrix.column_vector(a2)).element(0,0)
end
def vector_method a1, a2
a1.inner_product(a2)
end
n = 100000
Benchmark.bmbm do |b|
b.report('matrix method') { n.times { matrix_method(array_A, array_B) } }
b.report('array walking') { n.times { (0...array_A.count).to_a.inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array walking without to_a') { n.times { (0...array_A.count).inject(0) {|r, i| r + array_A[i]*array_B[i]} } }
b.report('array zip') { n.times { array_A.zip(array_B).map{|i,j| i*j }.inject(:+) } }
b.report('array zip 2') { n.times { array_A.zip(array_B).inject(0) {|r, (a, b)| r + (a * b)} } }
b.report('while loop') do
n.times do
sum, i, size = 0, 0, array_A.size
while i < size
sum += array_A[i] * array_B[i]
i += 1
end
sum
end
end
b.report('vector') { n.times { vector_method(vector_A, vector_B) } }
end
And the results:
结果:
Rehearsal --------------------------------------------------------------
matrix method 0.860000 0.010000 0.870000 ( 0.911755)
array walking 0.290000 0.000000 0.290000 ( 0.294779)
array walking without to_a 0.190000 0.000000 0.190000 ( 0.215780)
array zip 0.420000 0.010000 0.430000 ( 0.441830)
array zip 2 0.340000 0.000000 0.340000 ( 0.352058)
while loop 0.080000 0.000000 0.080000 ( 0.085314)
vector 0.310000 0.000000 0.310000 ( 0.325498)
----------------------------------------------------- total: 2.510000sec
user system total real
matrix method 0.870000 0.020000 0.890000 ( 0.952630)
array walking 0.290000 0.000000 0.290000 ( 0.340443)
array walking without to_a 0.220000 0.000000 0.220000 ( 0.240651)
array zip 0.400000 0.010000 0.410000 ( 0.441829)
array zip 2 0.330000 0.000000 0.330000 ( 0.359365)
while loop 0.080000 0.000000 0.080000 ( 0.090099)
vector 0.300000 0.010000 0.310000 ( 0.325903)
------
Too bad. :(
太糟糕了。:(