From: Robert Dober <robert.dober@...>
Date: 2006-08-25T05:39:26+09:00
Subject: Re: OrderedHash - How to get it to work

------=_Part_120136_7461839.1156451964547
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 8/24/06, Mauricio Fernandez <mfp@acm.org> wrote:
>
> 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)...


There exists  an N from which on O(1) beats O(n) this  N might be a Gogol
though
BTW n  > N not 1 > 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)
>
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D
> Loaded suite ohash
> Started
> ....
> Finished in 0.01929 seconds.
>
> 4 tests, 209 assertions, 0 failures, 0 errors
>
>
> $ cat ohash.rb
>
> module ALib
> end
> Alib =3D ALib
> require 'orderedhash'
>
>
> # written in a hurry and incomplete, but OK for laughs
> class Assoc < Hash
>   Entry =3D Struct.new(:key, :value,:prev,:next)
>   def initialize
>     @last =3D nil
>     @first =3D nil
>   end
>
>   alias_method :orig_aref, :[]
>
>   def store(k,v)
>     if has_key?(k)
>       orig_aref(k).value =3D v
>     else
>       e =3D Entry.new(k, v, @last, nil)
>       if @last
>         @last =3D @last.next =3D e
>       else
>         @first =3D @last =3D e
>       end
>     end
>     super k, e
>   end
>   alias_method :[]=3D, :store
>
>   def [](key)
>     if has_key?(key)
>       return orig_aref(key).value
>     end
>     super
>   end
>
>   def delete(key)
>     if has_key?(key)
>       e =3D orig_aref(key)
>       e.prev.next =3D e.next if e.prev
>       e.next.prev =3D e.prev if e.next
>       super
>       @first =3D @last =3D nil if size =3D=3D 0
>     end
>     super
>   end
>
>   def each
>     e =3D @first
>     while e
>       yield e.key, e.value
>       e =3D 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 =3D=3D(o); self.keys =3D=3D o.keys && self.values =3D=3D o.values e=
nd
>
>   require 'enumerator'
>   def self.[](*a)
>     h =3D new
>     a.each_slice(2){|k,v| h[k] =3D v}
>     h
>   end
> end
>
>
> require 'benchmark'
> Benchmark.bmbm(10) do |bm|
> i =3D 0
> ITER =3D 10000
> it =3D lambda do |klass|
>   lambda do
>      h =3D klass.new
>      1.step(ITER, 3) do |i|
>        h[i] =3D h[i+1] =3D h[i+2] =3D h[i+3] =3D h[i+4] =3D i
>        h.delete(i+2)
>      end
>    end
> end
>
> bm.report "Assoc", &it[Assoc]
> bm.report "Alib::OrderedHash", &it[ALib::OrderedHash]
> end
>
> puts "=3D" * 80
> require 'test/unit'
> class TestAssoc < Test::Unit::TestCase
>   def setup; @a =3D Assoc.new end
>   def test_aset_aref
>     100.times do |i|
>       @a[i] =3D 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] =3D 1
>     @a[2] =3D 2
>     assert_equal([1,2], @a.keys)
>     @a[1] =3D 3
>     assert_equal([1,2], @a.keys)
>     assert_equal([3,2], @a.values)
>   end
>
>   def test_eq
>     a =3D Assoc[1,2,3,4,5,6,7,8]
>     4.times{|i| @a[2*i+1] =3D 2+2*i}
>     assert(a =3D=3D @a)
>   end
>
>   def test_delete
>     10.times{|i| @a[i] =3D 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
>
>


--=20
Deux choses sont infinies : l'univers et la b=EAtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

------=_Part_120136_7461839.1156451964547--