The calendar is gone.
Click here to view posts

Large numbers of n

I found my self need to find the greatest number in an array of random numbers as fast as I can. Which sounds like a comp sci 101 problem visit every node and keep track of the highest number. I came up with a few different ways to do this with ruby's arrays and set up benchmarking.

n = 1000
marray = Array.new(6000)
range = (0...6000)
range.each{|i| marray[i]=rand(4000000)}

require "benchmark"
Benchmark.bmbm(1) do |test|
  test.report("Sort!:") do
    n.times{
      array =Array.new(marray)
      array.sort!
      array.last
    }
  end
  test.report("max:") do
    n.times{
      array =Array.new(marray)
      array.max
      }
  end
  test.report("Sort:") do
    n.times{
      array =Array.new(marray)
      array.sort.last
    }
  end
  test.report("range index:") do
    n.times{
      max=0
      array =Array.new(marray)
      range.each{|x| max=array[x] if array[x]>max}
    }
  end
  test.report("index:") do
    n.times{
      max=0
      array =Array.new(marray)
      array.each_index{|x| max=array[x] if array[x]>max}
    }
  end
  test.report("size indexing:") do
    n.times{
      max=0
      array =Array.new(marray)
      (0...array.size).each{|x| max=array[x] if array[x]>max}
    }
  end
  test.report("each:") do
    n.times{
      max=0
      array =Array.new(marray)
      array.each{|x| max=x if x>max}
    }
  end
  test.report("uniq each:") do
    n.times{
      max=0
      array =Array.new(marray)
      array.uniq!
      array.each{|x| max=x if x>max}
    }
  end
  test.report("pop:") do
    n.times{
      max=0
      array =Array.new(marray)
      while x=array.pop
        max = x if x>max
      end
    }
  end
end 

And the winner is Schwartzian transform with max as a close second!

#Rehearsal --------------------------------------------------
#Sort!:           1.380000   0.050000   1.430000 (  1.462959)
#max:             1.920000   0.010000   1.930000 (  1.932106)
#Sort:            1.380000   0.030000   1.410000 (  1.409176)
#range index:     8.060000   0.030000   8.090000 (  8.121491)
#index:           8.100000   0.070000   8.170000 (  8.200113)
#size indexing:   8.120000   0.060000   8.180000 (  8.194519)
#each:            4.840000   0.020000   4.860000 (  4.884708)
#uniq each:       7.140000   0.060000   7.200000 (  7.203439)
#pop:             5.590000   0.020000   5.610000 (  5.611432)
#---------------------------------------- total: 46.880000sec

#                     user     system      total        real
#Sort!:           1.380000   0.040000   1.420000 (  1.415057)
#max:             1.920000   0.020000   1.940000 (  1.927911)
#Sort:            1.380000   0.040000   1.420000 (  1.418863)
#range index:     8.050000   0.020000   8.070000 (  8.060964)
#index:           8.070000   0.010000   8.080000 (  8.079052)
#size indexing:   8.070000   0.030000   8.100000 (  8.085902)
#each:            4.820000   0.010000   4.830000 (  4.825778)
#uniq each:       7.160000   0.070000   7.230000 (  7.271699)
#pop:             5.600000   0.030000   5.630000 (  5.662141)

Some might say its not fair. That I changed the out come by measuring it, but I had to do it. Thats right sorting a random array to find the largest value of that array is the quickest way I can find. I have also tried this with 60k and 600k arrays with the same relative speeds. Since Ruby 1.8 it has used the Schwartzian transform[1] for its sort method. Which is clearly faster then each but why is each_index twice as slow as each? I thought the size indexing test was slower because of the range object creation but I tried it with a precompiled range and it still was 8 seconds.

[1] http://en.wikipedia.org/wiki/Schwartzian_transform

Tags: ruby benchmark