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

On Fri, Aug 25, 2006 at 12:49:51AM +0900, ara.t.howard@noaa.gov wrote:
> 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. 
> >
> >While we're at it, this makes ActiveSupport::OrderedHash over 5 times
> >faster and saves some lines of code:

(it only changed the constant, not the asymptotic complexity)

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

O(1) sure beats O(n)...

BTW,


--- orderedhash.rb.orig 2006-08-24 19:15:33.000000000 +0200
+++ orderedhash.rb      2006-08-24 19:20:49.000000000 +0200
@@ -196,7 +196,7 @@
     alias :merge! update
     def merge hsh2
 #--{{{
-        self.dup update(hsh2)
+        self.dup.update(hsh2)
 #--}}}
     end
     def select



Turnabout is fair play... Alib::OrderedHash#delete is an easy target.


$ ruby ohash.rb 
./orderedhash.rb:122: warning: `&' interpreted as argument prefix
./orderedhash.rb:127: warning: `&' interpreted as argument prefix
Rehearsal -----------------------------------------------------
Assoc               0.100000   0.000000   0.100000 (  0.101419)
Alib::OrderedHash   1.450000   0.000000   1.450000 (  1.459775)
-------------------------------------------- total: 1.550000sec

                        user     system      total        real
Assoc               0.100000   0.000000   0.100000 (  0.095813)
Alib::OrderedHash   1.450000   0.000000   1.450000 (  1.462457)
================================================================================
Loaded suite ohash
Started
....
Finished in 0.01929 seconds.

4 tests, 209 assertions, 0 failures, 0 errors


$ cat ohash.rb

module ALib
end
Alib = ALib
require 'orderedhash'


# written in a hurry and incomplete, but OK for laughs
class Assoc < Hash
  Entry = Struct.new(:key, :value,:prev,:next)
  def initialize
    @last = nil
    @first = nil
  end

  alias_method :orig_aref, :[]
  
  def store(k,v)
    if has_key?(k)
      orig_aref(k).value = v
    else
      e = Entry.new(k, v, @last, nil)
      if @last
        @last = @last.next = e
      else
        @first = @last = e
      end
    end
    super k, e
  end
  alias_method :[]=, :store

  def [](key)
    if has_key?(key)
      return orig_aref(key).value
    end
    super
  end
  
  def delete(key)
    if has_key?(key)
      e = orig_aref(key)
      e.prev.next = e.next if e.prev
      e.next.prev = e.prev if e.next
      super
      @first = @last = nil if size == 0
    end
    super
  end

  def each
    e = @first
    while e
      yield e.key, e.value
      e = e.next
    end
    self
  end
  alias_method :each_pair, :each
  def each_key; each{|k,v| yield k} end
  def each_value; each{|k,v| yield v} end
  # OK O(n) but Hash's too
  def keys; map{|k,v| k} end
  def values; map{|k,v| v} end
  def ==(o); self.keys == o.keys && self.values == o.values end

  require 'enumerator'
  def self.[](*a)
    h = new
    a.each_slice(2){|k,v| h[k] = v}
    h
  end
end


require 'benchmark'
Benchmark.bmbm(10) do |bm|
 i = 0
 ITER = 10000
 it = lambda do |klass|
  lambda do
     h = klass.new
     1.step(ITER, 3) do |i|
       h[i] = h[i+1] = h[i+2] = h[i+3] = h[i+4] = i
       h.delete(i+2)
     end
   end
 end

 bm.report "Assoc", &it[Assoc]
 bm.report "Alib::OrderedHash", &it[ALib::OrderedHash]
end

puts "=" * 80
require 'test/unit'
class TestAssoc < Test::Unit::TestCase
  def setup; @a = Assoc.new end
  def test_aset_aref
    100.times do |i|
      @a[i] = i+1
      assert_equal(i+1, @a.size)
      assert_equal(i+1, @a[i])
    end
    assert_equal((0..99).to_a, @a.keys)
    assert_equal((1..100).to_a, @a.values)
  end

  def test_aset
    @a[1] = 1
    @a[2] = 2
    assert_equal([1,2], @a.keys)
    @a[1] = 3
    assert_equal([1,2], @a.keys)
    assert_equal([3,2], @a.values)
  end

  def test_eq
    a = Assoc[1,2,3,4,5,6,7,8]
    4.times{|i| @a[2*i+1] = 2+2*i}
    assert(a == @a)
  end

  def test_delete
    10.times{|i| @a[i] = i}
    (0...20).sort_by{rand}.each{|i| @a.delete(i)}
    assert_equal(0, @a.size)
    assert_equal([], @a.keys)
    assert_equal([], @a.values)
  end
end


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