FW: Set and {} comparison confusion

[Roman Yakovenko]

From: Alex Martelli [mailto:[email protected]]

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

 

[Alex Martelli]

classes have __eq__, __ne__. Classes are mutable - I can't define
__hash__ function. __lt__ - I can implement but it will be meaningless.

As long as it respects the fundamental semantics constraints such as:
a < b and b < c imply a < c
a < b implies not (a == b)
a < b implies (a != b)
not (a < a) for any a
and so on, your __lt__will not be 'meaningless' but very useful.

Basically, __lt__ is meaningful if it's transitive, non-reflective, and
compatible with your == and != (which I assume are compatible with each
other); a transitive non-reflective < defines implicitly an equivalence
relation, a eqv b <--> not (a < b or b < a), and you need your == to
express exactly that equivalence relation... so if your == is
meaningful, your < can't really be 'meaningless'!-)

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.

Yes, that does seem to make sense to me. Once two lists without
duplicates are sorted, they're equal as sets iff they're == as lists;
and yes, maintaining sorted order is typically quite cheap in Python due
to Tim Peters' powerful natural mergesort algorithm as implemented
inside list.sort (though it might be worth having a look at the bisect
module, it's likely going to be faster to just sort the lists each
time).

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.

Ah, isn't set documented to need hashable elements? It should be. Of
course, _why_ your class appears to be hashable when it defines __eq__
and not __hash__ I dunno -- Python should diagnose that, but it does't
appear to...


Alex