From: Ben Tilly <ben_tilly@...>
Date: 2001-02-28T13:52:12+09:00
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

class Object
  def  eq? (other, cache)
    id == other.id ?
      true :
      self == other
  end

  def cmp (other, cache)
    id == other.id ?
      0 :
      self <=> other
  end
end

class SeenCache
  attr :seen

  def initialize
    @seen = Hash.new nil
  end

  def visited? (this, that)
    if @seen[this].nil?
      @seen[this] = [ that ]
    else
      return true if @seen[this].include? that
      @seen[this].push that
    end
    false
  end

end

class Array
  def <=> (other)
    cmp(other, SeenCache.new)
  end

  def cmp (other, cache)
    if (id == other.id or cache.visited? (id, other.id))
      return 0
    else
      other_a = other.to_ary
      min = length < other_a.length ?
        length :
        other_a.length
      for i in 0..(min - 1)
        val = self[i].cmp(other[i], cache)
        return val unless val == 0
      end
      length <=> other_a.length
    end
  end

  def == (other)
    eq? (other, SeenCache.new)
  end

  def eq? (other, cache)
    if (other.kind_of? (Array) and length == other.length)
      if (id != other.id and not cache.visited? (id, other.id))
        for i in 0...(length - 1) do
          return false unless self[i].eq? (other[i], cache)
        end
      end
      return true
    else
      return false
    end
  end

end

_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com