On Thu, Nov 24, 2005 at 12:03:48AM +0900, Steven D. Arnold wrote:
> On Nov 23, 2005, at 9:06 AM, David A. Black wrote:
> >You could define an appropriate default behavior for the hash of
> >hashes:
> >
> >  unique_hashes = Hash.new do |hash,key|
> >    existing = hash.keys.find {|k| k == key }
> >    if existing
> >      hash[existing] += 1
> >    else
> >      hash[key] = 1
> >    end
> >  end
> 
> This is a cool idea (and taught me about the block approach to  
> creating hashes, thanks!).  The one (seeming) flaw is the  
> hash.keys.find, which would do an O(n) search on the hash.keys array,  
> giving O(n) instead of a hash's normal O(ln(n)) behavior.  

[O(1)]

Yes.

unique_hashes = Hash.new do |h,k|
  k2 = Struct.new(:h) do 
         def eql?(o); h == o.h end 
	 def hash; h.to_a.hash end
       end.new(k)   # hoise the Struct def or use singleton methods for better
                    # performance
  h.has_key?(k2) ? h[k2] += 1 : h[k2] = 1
end

unique_hashes[{1 => 2}] # => 1
[{1 => 2}.object_id, {1 => 2}.object_id] # => [-605360772, -605360782]
unique_hashes[{2 => 3}] # => 1
unique_hashes[{1 => 2}] # => 2
unique_hashes[{1 => 2}] # => 3
RUBY_VERSION # => "1.8.3"

You can also redefine Hash#{eql?,hash} globally or using singleton
methods, of course.

-- 
Mauricio Fernandez