OrderedHash - How to get it to work

ruby-talk
1

First a bit of a rant. I CAN'T BELIEVE RUBY HASN'T IMPLEMENTED THIS!!!

Ok.. I feel better now. I am used to a verrry rich set of collection
classes in Smalltalk.

I know there has been a lot of discussion on this lately but I noticed
that the folks over at http://raa.ruby-lang.org/project/orderedhash/
have produced a class for us! It supports a pretty robust protocol.

However, if you download the gem and install it, it will error out. I
get a "superclass mismatch for class OrderedHash" error when my rails
controller gets loaded.

It turns out that rails also defined this class in it's initialize.rb
package. Burned on a namespace collision! Therefore, we can't use
OrderedHash as it's packaged from raa.ruby-lang.org. My solution was to
rename the ordered_hash.rb package to raa_ordered_hash.rb and then
rename the OrderedHash class within it to RaaOrderedClass.

Here is the full procedure I used.

1. Download the "GoodLibs-1.2006.07.13.gem" file from here:
http://raa.ruby-lang.org/project/orderedhash/
2. Run "gem install GoodLibs-1.2006.07.13.gem" from the directory you
downloaded it to.
3. Rename ordered_hash.rb to raa_ordered_hash.rb in the
"ruby\lib\ruby\gems\1.8\gems\GoodLibs-1.2006.07.13\lib" directory.
4. Edit the raa_ordered_hash.rb file and change the class to
RaaOrderedHash (in several places).
5. Use it in your code as follows:
    require 'rubygems'
    require 'raa_ordered_hash'
    BOOKCHAPTERS = RaaOrderedHash["MAT", 28, "MAR", 16, "LUK", 24,
"JOH", 21]
    BOOKCHAPTERS.each do |key, value| puts key +"," + value.to_s end

    MAT,28
    MAR,16
    LUK,24
    JOH,21

6. Restart you server

If someone has a better way let me know.

Thanks,
Paul

2

Facets: dictionary.rb

  http://facets.rubyforge.org

3

[...]

Ideally, it's Rails which should be renaming its class.
It's not even close to being a hash (it misses even the most basic complexity
premises).

class OrderedHash < Array #:nodoc:

is very telling. I also wonder why it's not defined in the ActiveSupport
namespace; some other classes are.

And they should use Array#assoc while they're at it.

···

On Thu, Aug 24, 2006 at 07:20:06AM +0900, Paul wrote:

I know there has been a lot of discussion on this lately but I noticed
that the folks over at http://raa.ruby-lang.org/project/orderedhash/
have produced a class for us! It supports a pretty robust protocol.

However, if you download the gem and install it, it will error out. I
get a "superclass mismatch for class OrderedHash" error when my rails
controller gets loaded.

It turns out that rails also defined this class in it's initialize.rb
package. Burned on a namespace collision! Therefore, we can't use
OrderedHash as it's packaged from raa.ruby-lang.org. My solution was to
rename the ordered_hash.rb package to raa_ordered_hash.rb and then
rename the OrderedHash class within it to RaaOrderedClass.

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

4

Trans wrote:

Facets: dictionary.rb

  http://facets.rubyforge.org

I should add that Dictionary is a slightly modified version of Jan
Molic's great work.

T.

5

Ideally, it's Rails which should be renaming its class.
It's not even close to being a hash (it misses even the most basic complexity
premises).

class OrderedHash < Array #:nodoc:

is very telling. I also wonder why it's not defined in the ActiveSupport
namespace; some other classes are.

And they should use Array#assoc while they're at it.

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

You are absolutely correct. Someone needed to override Hash with just a
few methods and named the class OrderedHash. I don't want to undermine
the tremendous effort that has been pouring into rails though. Perhaps
they should prefix internal classes with Rails...

6

The class is namespaced in trunk (will become Rails 1.2).

jeremy

···

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.

7

Trans wrote:

Trans wrote:
> Facets: dictionary.rb
>
> http://facets.rubyforge.org

I should add that Dictionary is a slightly modified version of Jan
Molic's great work.

T.

Thanks Trans - great extensions! I will definitely scan through these
and add to the tool box :slight_smile:

Paul

8

You are absolutely correct. Someone needed to override Hash with just a few
methods and named the class OrderedHash.

     harp:~ > cat a.rb
     require 'yaml'
     require 'rubygems'
     require 'alib' # gem install alib
     include Alib

     oh = OrderedHash.new
     oh['a'] = 0
     oh['b'] = 1
     oh['c'] = 2
     y 'oh' => oh
     y "oh.values_at('b', 'c')" => oh.values_at('b', 'c')

     oah = OrderedAutoHash.new
     oah['A']['a'] = 4
     oah['A']['b'] = 2
     oah['B']['a']['a'] = 4
     oah['B']['a']['b'] = 2
     y 'oah' => oah

     harp:~ > ruby a.rb
     oh:
       b: 1
       c: 2
     oh.values_at('b', 'c'):
     - 1
     - 2
     oah:
       A:
         b: 2
       B:
         a:
           b: 2

the OrderedAutoHash is really nice for generating reports/yaml.

regards.

-a

···

On Thu, 24 Aug 2006, Paul wrote:
       a: 0
         a: 4
           a: 4
--
to foster inner awareness, introspection, and reasoning is more efficient than
meditation and prayer.
- h.h. the 14th dali lama

9

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

···

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).

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

10

and this makes it about two orders of magnitude faster :wink:

   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

···

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:

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

11

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

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)

···

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:

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

12

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

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,

···

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:

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

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

- Albert Einstein