FW: Set and {} comparison confusion

[Roman Yakovenko]

[color=blue]
> From: Alex Martelli [mailto:aleaxit@ yahoo.com]
>
> Roman Yakovenko <roman.yakovenk o@actimize.com> wrote:
> [color=green]
> > 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[/color]
>
> 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.[/color]

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.

[color=blue]
> 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(on elist, 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[/color]

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]

Re: FW: Set and {} comparison confusion

Roman Yakovenko <roman.yakovenk o@actimize.com> wrote:
...[color=blue]
> classes have __eq__, __ne__. Classes are mutable - I can't define
> __hash__ function. __lt__ - I can implement but it will be meaningless.[/color]

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'!-)
[color=blue]
> 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.[/color]

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).

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

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