Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's the efficient way to multiply two arrays and get sum of multiplied values in Ruby?

Tags:

arrays

ruby

What's the efficient way to multiply two arrays and get sum of multiply values in Ruby? I have two arrays in 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.

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.

like image 750
Kevin Hua Avatar asked Sep 10 '11 14:09

Kevin Hua


2 Answers

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.

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.

I still prefer inject method because it's more ruby-ish, but if speed matters then the while loop seems to be the way.

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.

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
like image 101
Fabio Avatar answered Oct 26 '22 16:10

Fabio


Walking through each element should be a must

(0...array_A.count).inject(0) {|r, i| r + array_A[i]*array_B[i]}
like image 29
PeterWong Avatar answered Oct 26 '22 15:10

PeterWong