Home Original page

FW: Set and {} comparison confusion

Roman Yakovenko roman.yakovenko at actimize.com
Thu Sep 9 05:07:24 EDT 2004 
> From: Alex Martelli [mailto:aleaxit at yahoo.com]
> 
> 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.

Right, this is exactly my constraints:  
classes have __eq__, __ne__. Classes are mutable - I can't define 
__hash__ function. __lt__ - I can implement but it will be meaningless.


> 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

I agree with you: it's horrible. 

Thank you for help. I think I have a dicision:
1. I will implement meaningless __lt__
2. I will sort ( I don't have duplicated items ) every time I need to compare
2.1 Because sort is happen in place next time it will take less time to sort.

Again - Thanks for help. It was very usefull. It seems that I had wrong expectation
from set - " unordered set collection based only on comparison operators".
My mistake. 

Roman
More information about the Python-list mailing list