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 
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
#–{{{
#–}}}
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
