Forum: Ruby Fastest way to compute dot product (inner product) in Ruby?

219fcd6acd2770ee252cc4c08aa13bf6?d=identicon&s=25 theosib@gmail.com (Guest)
on 2007-11-02 01:10
(Received via mailing list)
Ruby seems to provide some nice, abstract ways of doing some
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[i] * l2[i]
    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 += l1[i] * l2[i]
    end
    sum
end

def dot_product_f l1, l2
    sum = 0
    l1.each_index do |i|
        sum += l1[i] * l2[i]
    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 v1[i], v2[i]
    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)
610397600a95f689c97dc256ce18f585?d=identicon&s=25 Golda Bence (Guest)
on 2007-11-02 02:21
(Received via mailing list)
theosib@gmail.com wrote:
> Ruby seems to provide some nice, abstract ways of doing some
> computationally intensive things quickly.  For instance, String#unpack
> [..]

Take a look at GSL bindings:

http://rb-gsl.rubyforge.org/

You'll find dot product below "Vector multiplication".
(http://rb-gsl.rubyforge.org/vector.html#3.7)

Cheers, Bence
47b1910084592eb77a032bc7d8d1a84e?d=identicon&s=25 Joel VanderWerf (Guest)
on 2007-11-02 03:06
(Received via mailing list)
theosib@gmail.com wrote:
> ...Anyhow, so I'm trying to find the fastest way to
> compute a dot product...

require 'narray' # not pure ruby
NVector[1,2,3] * NVector[3,6,9]
=> 42

Here's a benchmark:

require 'benchmark'
require 'narray'

def dot_product_e l1, l2
     sum = 0
     for i in 0...l1.size
         sum += l1[i] * l2[i]
     end
     sum
end

Benchmark.bmbm(12) do |x|

   n = 100_000
   u = NVector[1..20]
   v = NVector[21..40]

   x.report("u*v") do
     n.times do
       u*v
     end
   end

   x.report("dot_product_e") do
     n.times do
       dot_product_e u, v
     end
   end
end

__END__

Output:

Rehearsal -------------------------------------------------
u*v             0.380000   0.020000   0.400000 (  0.396224)
dot_product_e   3.370000   0.000000   3.370000 (  3.382755)
---------------------------------------- total: 3.770000sec

                     user     system      total        real
u*v             0.390000   0.000000   0.390000 (  0.398509)
dot_product_e   3.380000   0.010000   3.390000 (  3.385840)
219fcd6acd2770ee252cc4c08aa13bf6?d=identicon&s=25 theosib@gmail.com (Guest)
on 2007-11-02 03:53
(Received via mailing list)
On Nov 1, 10:05 pm, vj...@path.berkeley.edu wrote:
> theo...@gmail.com wrote:
> > ...Anyhow, so I'm trying to find the fastest way to
> > compute a dot product...
>
> require 'narray' # not pure ruby

This doesn't appear to be a standard library.  Is it available through
rubygems?
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2007-11-02 04:25
(Received via mailing list)
On Nov 1, 8:46 pm, "theo...@gmail.com" <theo...@gmail.com> wrote:
> On Nov 1, 10:05 pm, vj...@path.berkeley.edu wrote:
>
> > theo...@gmail.com wrote:
> > > ...Anyhow, so I'm trying to find the fastest way to
> > > compute a dot product...
>
> > require 'narray' # not pure ruby
>
> This doesn't appear to be a standard library.  Is it available through
> rubygems?

http://www.google.com/search?q=narray
Please log in before posting. Registration is free and takes only a minute.
Existing account

NEW: Do you have a Google/GoogleMail, Yahoo or Facebook account? No registration required!
Log in with Google account | Log in with Yahoo account | Log in with Facebook account
No account? Register here.