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)

on 2007-11-02 01:10

on 2007-11-02 02:21

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

on 2007-11-02 03:06

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)

on 2007-11-02 03:53

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?

on 2007-11-02 04:25

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