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

Discussion in 'Ruby' started by theosib@gmail.com, Nov 2, 2007.

  1. Guest

    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 * 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 += l1 * l2
    end
    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 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)
    , Nov 2, 2007
    #1
    1. Advertising

  2. Guest

    , Nov 2, 2007
    #2
    1. Advertising

  3. Guest

    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 * l2
    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)

    --
    vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
    , Nov 2, 2007
    #3
  4. Guest

    On Nov 1, 10:05 pm, wrote:
    > 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?
    , Nov 2, 2007
    #4
  5. Phrogz Guest

    On Nov 1, 8:46 pm, "" <> wrote:
    > On Nov 1, 10:05 pm, wrote:
    >
    > > 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
    Phrogz, Nov 2, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Samuël van Laere

    To dot or not to dot?

    Samuël van Laere, Oct 16, 2003, in forum: HTML
    Replies:
    8
    Views:
    423
    Samuël van Laere
    Oct 16, 2003
  2. Christopher M. Lusardi

    volatile struct in dot h vs dot c

    Christopher M. Lusardi, May 11, 2004, in forum: C Programming
    Replies:
    3
    Views:
    473
    Peter Shaggy Haywood
    May 15, 2004
  3. Nathan Sokalski
    Replies:
    11
    Views:
    702
    AAaron123
    Aug 14, 2009
  4. PerlFAQ Server
    Replies:
    0
    Views:
    265
    PerlFAQ Server
    Feb 2, 2011
  5. Replies:
    6
    Views:
    245
    Thomas 'PointedEars' Lahn
    Dec 12, 2005
Loading...

Share This Page