On Fri, 23 Feb 2001, Eugene Ventimiglia wrote:
> > A similar problem is for loopless graphs. Try the following:
> > def f(x); [x,x]; end
> > def g(x); f f f f f f f f x; end
> > (g g g 1) == (g g g 1) #=> true
> > This seems normal, but it takes 33 million comparisons, even though each
> > side of the equality has only 25 objects !!!
> Forgive me if I'm misreading this, but doesn't g(x) produce 512 objects?

No, it produces a chain of 8 arrays where each has two links to the
following one (the last one has two links to x). So there are 256 ways of
getting to x through the result of g(x).

(g g g 1) is a chain of 24 arrays, where you may take 256*256*256
different paths to the number 1. There are 48 array cells total, 46 of
which pointing to arrays and 2 containing the number 1. 

The comparison 1==1 is done 2**24 times, the last array comparisons are
done 2**23 times, ... the first array comparison is done 2**0 times.

This is sum(0..24) {|x| 2**x } comparisons. This may be written
"1 11111111 11111111 11111111" in binary, which is 2**25 - 1.

> irb(main):003:0> f f 1
> [[1, 1], [1, 1]]

You see here one array pointing twice to the same array pointing twice to
the number 1. Of course, performing an eval on that will give you 3
arrays, not two.

matju