[ruby-talk:11803] RE: Comparison Caching

> From: Ben Tilly [mailto:[e-mail]]
> Sent: Tuesday, February 27, 2001 08:52 PM
> To: ruby-talk ML
> Subject: [ruby-talk:11739] Comparison Caching
> 
> 
> OK, this is my latest entry in the "solve testing
> equality with a recursive data structure" discussion.
> Unfortunately on my machine the test suite that others
> are using fails miserably after exhausting the stack,
> but when I scale it back this seems to be a tad faster.
> But note that it is optimized for the case where we
> see each object compared to very few others.
> 
> I have changed names of methods a little bit.  Feel
> free to change them back.  I also did both <=> and
> == (but only for arrays).
> 
> I tried a caching scheme of hashes of hashes, that
> was consistently somewhat slower.  But there are
> definitely cases where it would be faster...
> 
> Cheers,
> Ben
[...]

As discussed in a private email your and my (optimisitic) algorithm are 
identical(modulo details). My main objection about your current version
is that it depends on the Hash-Hash realization of an ``Idbag'' and does
not abstract this away as an implementation detail. 
In principle a Hash - Hash (of Integer) encoding and the (Sym)Id_pair
encoding are actually more or less identical and in an ideal version 
you would write the whole ID-bag class in C. 
(I appended a version of IdBag based on Hash which is a bit faster on 
my Machine then my original (faster module (Non symetric) IdBag2) version 
- the main reason is that no intermediate IdPair Objects are created - 
I don't know if if Guy's C-implementation does the same thing).  

I also think that your objections towards symmetrization - i.e. swapping
are not valid since they cost very little compared to the reminder division 
invoked in any hashing scheme and running the interpreter it self of course
(in my test it makes virtually non difference if you swap or don't swap - 
even so swapping does not gain anything in the ``examples'') 
- swapping IMO simply feels more robust.
 

Christoph

------------

module IdBag1
class IdBag
def initialize
	@bag = {}
end
attr_accessor :bag
def  sym_pair_include?  a, b 
	if  a < b then
	      if (tmp =@bag[a])
	      	return tmp[b]
	      else
	      	false
	      end
	 else
	  	if (tmp =@bag[b])
	 	      	return tmp[a]
	 	      else
	 	      	false
	      end
	 end
end	 
def  sym_pair_include a, b
	if  a < b then
		if (tmp= @bag[a])
			tmp[b] = true			
		else
			tmp= @bag[a] ={}
			tmp[b] = true
		end
	else
		if (tmp= @bag[b])
			tmp[a] = true
		else
			tmp= @bag[b] ={}
			tmp[a] = true
		end
	end
end
end                        
end

module IdBag2
class IdBag
def initialize
	@bag = {}
end
def  include_pair a, b
	@bag[IdPair.new a.id,b.id] =true
end	
def included_pair? a,b
	@bag.key? (IdPair.new a.id,b.id)
end

private
class IdPair
def initialize l,r
	@l = l; @r = r
end
def hash;	@l end
def eql?(other)
	@r.eql?  (other.r)
end	
protected 
attr_reader :l, :r
end
end                        
end