OrderedHash - How to get it to work

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

Facets: dictionary.rb

http://facets.rubyforge.org

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

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.
[…]

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.

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.

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


Mauricio F. - 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…

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

On Thu, 24 Aug 2006, Paul wrote:

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:
   a: 0
   b: 1
   c: 2
 oh.values_at('b', 'c'):
 - 1
 - 2
 oah:
   A:
     a: 4
     b: 2
   B:
     a:
       a: 4
       b: 2

the OrderedAutoHash is really nice for generating reports/yaml.

regards.

-a

On 8/23/06, Mauricio F. [email protected] 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).

jeremy

On Thu, Aug 24, 2006 at 03:03:09PM +0900, Jeremy K. wrote:

On 8/23/06, Mauricio F. [email protected] 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
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
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)

On Fri, 25 Aug 2006, Mauricio F. wrote:

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 :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 8/24/06, Mauricio F. [email protected] wrote:

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,

#–}}}
./orderedhash.rb:127: warning: `&’ interpreted as argument prefix
Loaded suite ohash
end
end
else
end
end
end
h = new
it = lambda do |klass|
bm.report “Alib::OrderedHash”, &it[ALib::OrderedHash]
assert_equal(i+1, @a[i])
assert_equal([1,2], @a.keys)
10.times{|i| @a[i] = i}


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

On Fri, Aug 25, 2006 at 12:49:51AM +0900, [email protected] wrote:

On Fri, 25 Aug 2006, Mauricio F. wrote:

On Thu, Aug 24, 2006 at 03:03:09PM +0900, Jeremy K. wrote:

On 8/23/06, Mauricio F. [email protected] 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 :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)

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
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.
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[2i+1] = 2+2i}
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