Re: The naive test for equality

David Cressey wrote:
>
> Well, I could always be wrong. It's happened before. But I think the group
> of things that can be obtained by permuting the components gets real big,
> real fast.

Yes, it grows with the factorial of the size. (The phrase "real big, real
fast" makes me think of the Busy Beaver function, which grows uncomputably
fast. Now that's fast! I wish my car went that fast.)

> The next step in the discussion involves representation and synonyms,
> again.
>
> If a single referent can be signalled by more than one representation,
> that's what I'm calling "the synonym problem".
> In this case, an equality test of the referents may require some kind of
> equivalence test of the references.

Sure. I'd say "value" instead of "referent", but I get you.

> [...] But, in order to avoid confusion, the floating
> point hardware generally takes one more step before returning the result.
> This step is generally called "normalizing" (sigh).

I'm not sure why you sigh; that's exactly the right word for it.

> Now for SQL tables. In the definition of SQL tables, it's quite clear that
> the order of the rows is immaterial. This means that, if you have two table
> values, where one can be obtained by permuting the rows of the other, the
> two values represent the same thing. They are synonyms. This means that,
> when we test two SQL table values for equality, we have to test the two
> table values for equivalence under permutation, and not for equality.

I'd say, they are equal, but I understand your terms.

This isn't hugely difficult, though. You can do it any number of ways. One way would be to sort the two tables (or "normalize" them) and then you can compare more directly. This can O(n logn) and O(n) in space. We can then do something approximating the naive test for equality.

What we've learned is that, while the naive equality test executes in linear time, it might not always be possible to implement the equals function for a give type in linear time.

Marshall Received on Thu Aug 04 2005 - 06:25:45 CEST