T

#### theosib

computationally intensive things quickly. For instance, String#unpack

is a very nice and efficient way to convert between formats when doing

I/O and such. Unfortunately, it doesn't seem to have an efficient way

to compute functions on vectors. It sure would be nice, for instance,

if I could add two vectors and get another vector which is the

component-wise sum. But alas, it's also important to be able to

concatenate arrays. Anyhow, so I'm trying to find the fastest way to

compute a dot product, and I was hoping I could get some help from

others out there who surely know more about this than I do.

I'd like to begin by saying that Array#zip sucks. Ok, I'm sure

there's a case where it's useful, but I haven't found it. Every one

of the dot product suggestions I've found through Google suggests

using zip, and I have found that zip imposes a huge amount of

overhead. I suspect the main problem is that zip isn't lazy about

creating the new array but instead actually allocates the memory and

fully computes the combined array before passing it on. That takes a

long time, even though it's being done "under the hood" in C where it

should be faster.

To make a long story short, I've put together a benchmark that

compares a number of different solutions. Unfortunately, the

"dumbest" most straight-forward solution seems to be, by far, the

fastest. There's got to be a better way, and I'm hoping someone on

this newsgroup can make a suggestion.

To jump to the answer, this one is consistently the winner:

def dot_product_e l1, l2

sum = 0

for i in 0...l1.size

sum += l1

** l2*

end

sum

end

Here's the benchmark I ran:

require 'benchmark'

# The following from http://c2.com/cgi/wiki?DotProductInManyProgrammingLanguages

def dot_product_a l1, l2

l1.zip(l2).inject(0) { |sum,els| sum+els[0]*els[1] }

end

def dot_product_b l1, l2

l1.zip(l2).map { |a,b| a*b }.inject {|sum,el| sum+el}

end

def dot_product_c l1, l2

sum=0

for a,b in l1.zip(l2)

sum+= a*b

end

sum

end

def dot_product_d l1, l2

sum=0

l1.zip(l2){|a, b| sum+=a*b}

sum

end

# The next two, I wrote

def dot_product_e l1, l2

sum = 0

for i in 0...l1.size

sum += l1end

sum

end

Here's the benchmark I ran:

require 'benchmark'

# The following from http://c2.com/cgi/wiki?DotProductInManyProgrammingLanguages

def dot_product_a l1, l2

l1.zip(l2).inject(0) { |sum,els| sum+els[0]*els[1] }

end

def dot_product_b l1, l2

l1.zip(l2).map { |a,b| a*b }.inject {|sum,el| sum+el}

end

def dot_product_c l1, l2

sum=0

for a,b in l1.zip(l2)

sum+= a*b

end

sum

end

def dot_product_d l1, l2

sum=0

l1.zip(l2){|a, b| sum+=a*b}

sum

end

# The next two, I wrote

def dot_product_e l1, l2

sum = 0

for i in 0...l1.size

sum += l1

** l2*

end

sum

end

def dot_product_f l1, l2

sum = 0

l1.each_index do |i|

sum += l1end

sum

end

def dot_product_f l1, l2

sum = 0

l1.each_index do |i|

sum += l1

** l2*

end

sum

end

# And lastly, I copied code from the standard matrix.rb module

def each2(v1, v2)

0.upto(v1.size - 1) do |i|

yield v1end

sum

end

# And lastly, I copied code from the standard matrix.rb module

def each2(v1, v2)

0.upto(v1.size - 1) do |i|

yield v1

*, v2*

end

end

def dot_product_g l1, l2

sum = 0

each2(l1, l2) { |a,b| sum += a*b }

sum

end

a = []

b = []

for i in 0...1000000

a.push(rand)

b.push(rand)

end

n = 500000

Benchmark.bm do |x|

x.report { dot_product_a(a, b) }

x.report { dot_product_b(a, b) }

x.report { dot_product_c(a, b) }

x.report { dot_product_d(a, b) }

x.report { dot_product_e(a, b) }

x.report { dot_product_f(a, b) }

x.report { dot_product_g(a, b) }

end

On an Apple MacBook Pro with a Core 2 Duo, 2.33GHz, with Ruby compiled

through Fink, these are the results (repeated runs nearly identical):

user system total real

1.960000 0.050000 2.010000 ( 2.022095)

1.890000 0.140000 2.030000 ( 2.046605)

1.230000 0.020000 1.250000 ( 1.261263)

1.270000 0.010000 1.280000 ( 1.277588)

0.790000 0.000000 0.790000 ( 0.793650)

1.180000 0.000000 1.180000 ( 1.198618)

1.340000 0.000000 1.340000 ( 1.344791)end

end

def dot_product_g l1, l2

sum = 0

each2(l1, l2) { |a,b| sum += a*b }

sum

end

a = []

b = []

for i in 0...1000000

a.push(rand)

b.push(rand)

end

n = 500000

Benchmark.bm do |x|

x.report { dot_product_a(a, b) }

x.report { dot_product_b(a, b) }

x.report { dot_product_c(a, b) }

x.report { dot_product_d(a, b) }

x.report { dot_product_e(a, b) }

x.report { dot_product_f(a, b) }

x.report { dot_product_g(a, b) }

end

On an Apple MacBook Pro with a Core 2 Duo, 2.33GHz, with Ruby compiled

through Fink, these are the results (repeated runs nearly identical):

user system total real

1.960000 0.050000 2.010000 ( 2.022095)

1.890000 0.140000 2.030000 ( 2.046605)

1.230000 0.020000 1.250000 ( 1.261263)

1.270000 0.010000 1.280000 ( 1.277588)

0.790000 0.000000 0.790000 ( 0.793650)

1.180000 0.000000 1.180000 ( 1.198618)

1.340000 0.000000 1.340000 ( 1.344791)