From: ara.t.howard@...
Date: 2006-08-25T00:49:51+09:00
Subject: Re: OrderedHash - How to get it to work

On Fri, 25 Aug 2006, Mauricio Fernandez wrote:

> 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:

and this makes it about two orders of magnitude faster ;-)


   harp:~ > ruby a.rb
   Rehearsal -----------------------------------------------------
   find_pair           0.920000   0.000000   0.920000 (  0.925936)
   assoc               0.160000   0.000000   0.160000 (  0.152839)
   Alib::OrderedHash   0.000000   0.000000   0.000000 (  0.004061)
   -------------------------------------------- total: 1.080000sec

                           user     system      total        real
   find_pair           0.960000   0.000000   0.960000 (  0.962423)
   assoc               0.150000   0.000000   0.150000 (  0.154931)
   Alib::OrderedHash   0.000000   0.000000   0.000000 (  0.004245)



   harp:~ > cat a.rb
   require 'rubygems'
   require 'active_support'
   require 'alib'

   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
    it = lambda do |klass|
     lambda do
        h = klass.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

    bm.report "find_pair", &it[OrderedHash1]
    bm.report "assoc", &it[OrderedHash2]
    bm.report "Alib::OrderedHash", &it[Alib::OrderedHash]
   end


regards.

-a
-- 
to foster inner awareness, introspection, and reasoning is more efficient than
meditation and prayer.
- h.h. the 14th dali lama