Home Original page

Set and {} comparison confusion

Alex Martelli aleaxit at yahoo.com
Thu Sep 9 04:18:31 EDT 2004 
Roman Yakovenko <roman.yakovenko at actimize.com> wrote:

> Thanks. I have an other question, more general:
> 
> I have class A that defines __eq__ and __ne__.
> I have 2 lists of instances of A
> 
> What is the right way to find out whether those lists
> are equal (as sets) or not? 
> 
> Thanks for help

If instances of class A are not hashable, there is unfortunately no fast
way.  Tim Peters, in the Python Cookbook (first edition), shows an
elaborate way to turn a list into a list of unique elements which is as
fast as feasible depending on the list elements' properties, which the
recipe discovers automatically by fielding errors raised by usage that
the list items don't support -- but even that would be thrown off the
rails if the instances of A _appear_ to be hashable but violate the key
semantic constraint (equality of instance MUST imply equality of hash).

I assume from your specific mention of __eq__ and __ne__ that you can't
even SORT a list of such instances -- that they don't define __lt__ or
define it in such ways as to violate the key semantic constraint on THAT
operation -- so you can't even use the second-best approach (after
hashing), which starts with sorting.

Under such dire, horrible conditions you will have to resort to the
extremely slow approach, O(M*N) where M and N are the lengths of the two
lists -- at least it can be expressed simply...:

def same_as_sets(onelist, another):
    for item in onelist:
        if item in another: return False
    for item in another:
        if item in onelist: return False
    return True

It's horrible, but then that class appears to be designed to fight
against attempts to solve this problem more smartly, at least
extrapolating from what little you tell us about it.


Alex
More information about the Python-list mailing list