OrderedHash - How to get it to work

[Paul]

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

 

[Trans]

Facets: dictionary.rb

http://facets.rubyforge.org

 

[Mauricio Fernandez]

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.

[...]

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]

Facets: dictionary.rb

http://facets.rubyforge.org

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

T.

 

[Paul]

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.

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

 

[Paul]

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

Paul

 

[ara.t.howard]

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

 

[Mauricio Fernandez]

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 [](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 = 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 = 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)

 

[ara.t.howard]

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

 

[Mauricio Fernandez]

(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.newkey, :value,rev,:next)
def initialize
@last = nil
@first = nil
end

alias_method rig_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 = 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+1
assert_equal(i+1, @a.size)
assert_equal(i+1, @a)
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}
(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