From: Mauricio Fernandez <mfp@...>
Date: 2006-08-25T00:12:07+09:00
Subject: Re: OrderedHash - How to get it to work

On Thu, Aug 24, 2006 at 03:03:09PM +0900, Jeremy Kemper wrote:
> On 8/23/06, Mauricio Fernandez <mfp@acm.org> wrote:
> 
> >class OrderedHash < Array #:nodoc:
> >
> >is very telling. I also wonder why it's not defined in the ActiveSupport
> >namespace; some other classes are.
> >
> 
> The class is namespaced in trunk (will become Rails 1.2).

That's good.

While we're at it, this makes ActiveSupport::OrderedHash over 5 times faster
and saves some lines of code:


Index: activesupport/lib/active_support/ordered_options.rb
===================================================================
--- activesupport/lib/active_support/ordered_options.rb (revision 4814)
+++ activesupport/lib/active_support/ordered_options.rb (working copy)
@@ -2,7 +2,7 @@
 module ActiveSupport
   class OrderedHash < Array #:nodoc:
     def []=(key, value)
-      if pair = find_pair(key)
+      if pair = assoc(key)
         pair.pop
         pair << value
       else
@@ -11,7 +11,7 @@
     end
 
     def [](key)
-      pair = find_pair(key)
+      pair = assoc(key)
       pair ? pair.last : nil
     end
 
@@ -22,12 +22,6 @@
     def values
       collect { |key, value| value }
     end
-
-    private
-      def find_pair(key)
-        self.each { |i| return i if i.first == key }
-        return false
-      end
   end
 end



The benchmark:

class OrderedHash1 < Array #:nodoc:
  def []=(key, value)
    if pair = find_pair(key)
      pair.pop
      pair << value
    else
      self << [key, value]
    end
  end

  def [](key)
    pair = find_pair(key)
    pair ? pair.last : nil
  end
  
  # ...
  private
    def find_pair(key)
      self.each { |i| return i if i.first == key }
      return false
    end
end

class OrderedHash2 < Array #:nodoc:
  def []=(key, value)
    if pair = assoc(key)
      pair.pop
      pair << value
    else
      self << [key, value]
    end
  end

  def [](key)
    pair = assoc(key)
    pair ? pair.last : nil
  end
end

require 'benchmark'
Benchmark.bmbm(10) do |bm|
  i = 0
  ITER = 1000
  bm.report("find_pair") do
    h = OrderedHash1.new
    1.step(ITER, 3){|i| h[i] = h[i+1] = h[i+2] = h[i+3] = h[i+4] = i  } # collision, on purpose
  end
  bm.report("assoc") do
    h = OrderedHash2.new
    1.step(ITER, 3){|i| h[i] = h[i+1] = h[i+2] = h[i+3] = h[i+4] = i  } # collision, on purpose
  end
end
# >> Rehearsal ---------------------------------------------
# >> find_pair   0.580000   0.000000   0.580000 (  1.208422)
# >> assoc       0.110000   0.000000   0.110000 (  0.213973)
# >> ------------------------------------ total: 0.690000sec
# >> 
# >>                 user     system      total        real
# >> find_pair   0.580000   0.010000   0.590000 (  1.216815)
# >> assoc       0.110000   0.000000   0.110000 (  0.221488)

-- 
Mauricio Fernandez  -   http://eigenclass.org   -  singular Ruby