Performance of list vs. set equality operations

[Jack Diederich]

On Tue, Apr 6, 2010 at 2:11 PM, Gustavo Narea <me at gustavonarea.net> wrote:
> Hello!
>
> Could you please confirm whether my understanding of equality
> operations in sets and lists is correct? This is how I think things
> work, partially based on experimentation and the online documentation
> for Python:
>
> When you compare two lists, *every* element of one of the lists is
> compared against the element at the same position in the other list;
> that comparison is done by the __eq__() method (or the equivalent for
> builtin types). This is interrupted when a result is False.
>
> When you compare two sets, there's a loop over all the elements of the
> first set, where the hash for that element is looked up in the second
> set:
[snip]
> In other words: The more different elements two collections have, the
> faster it is to compare them as sets. And as a consequence, the more
> equivalent elements two collections have, the faster it is to compare
> them as lists.
>
> Is this correct?

Yes, but faster isn't the same thing as free.  I still get bitten
occasionally by code that blows away the difference by including a
set-wise assert() in a loop.   Also, lists can have mutable members so
there are times you really /do/ want to compare lists instead of
hashes.

-Jack