From: "Benjamin J. Tilly" <ben_tilly@...>
Date: 2001-03-11T01:35:50+09:00
Subject: [ruby-talk:12383] Re: Q re looping structures

>===== Original Message From "Benjamin J. Tilly" <ben_tilly@operamail.com> 
=====
[...]
>As for the other problem, you have found a worst case
>performance case.  It is still only quadratic in the
>real size of the intial data structures.  And it is
>sufficiently hard to get into that I don't think that
>people will do it by accident.
[...]

Hmmm..it is cubic.  As I said when posting my original code
I was using a hash of arrays because it was fastest in the
usual case, but a hash of hashes is better.

Try this untangling code and see if performance isn't
slightly better...

Cheers,
Ben

class Object
  def  eq? (other, cache)
    self == other
  end
end

class SeenCache
  attr :seen

  def initialize
    @seen = Hash.new nil
  end

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

end

class Array

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

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

end

-------------------------------------------
The Fastest Browser on Earth now for FREE!!
Download Opera 5 for Windows now! Get it at
http://www.opera.com/download/
-------------------------------------------