[Edu-sig] Basic dictionary question

[Guido van Rossum]

Alas, you can't do that, and the problem isn't a deficiency of dicts,
but the fact that "almost equal" is not a transitive relationship.
Think about it. (Boy that brings back memories of math classes in
college, way, way, back, where a professor pointed this out casually
as an counter-illustration of transitive relationships.)

Superficially, the problem you have is that you're overriding __eq__
without __hash__. The dict implementation uses the __hash__ method
partitions objects into (conceptual) buckets with the same hash value,
so that if two objects are equal, they occur in the same hash bucket,
but not necessarily the other way around -- two objects in the same
hash bucket may still be unequal.

But because you're defining equality in the peculiar way that you do,
it's impossible to create a non-trivial __hash__ method that satisfies
this requirement. A near-solution would be to make __hash__ return a
constant; that will cause you a serious degradation of the dict
performance, but more seriously, it will cause undefined behavior.
Here's why.

Consider three numbers A, B and C such that A == B == B but A != C. In
your example, where e is 0.01, we could pick A = 1, B = 1.007, C =
1.014 in one dimension, and equal in the others. Now if you put A and
C in the dict, the dict will have two keys. But when you add B, will
it map to A or to C? That depends on the order in which the dict
probes the values!

You never said what you wanted to do with these points -- are you
looking to find which points are in fact close enough to be considered
the same point? I suppose you could sort them by the vector length
(sqrt(x**2 + y**2 + z**2), that sort of thing) and then you only have
to compare points that are close together in the sorted list (as long
as the abs values are closer than your epsilon). Or you could divide
3-space up into cubes with sides equal epsilon, and then you'd only
have to look for points that end up in the same or in adjacent cubes.

--Guido

On 10/8/05, Kirby Urner <urnerk at qwest.net> wrote:
>
> So here's my situation.  I have a set of XYZ tuples that'll come very close
> to matching, most of them in pairs, but thanks to floating point, I can only
> rely on "fuzzy equality" i.e. within a tolerance of say |e| per each x,y,z.
> In other words, for all intents and purposes, I could consider (1.0, 0.0,
> 0.0) and (1.001, 0.0, 0.0) to be the same.
>
> My thought was to use a dictionary, indexing with these tuples.  Except they
> wouldn't be primitive tuples, I'd define an object with fuzzy equality
> implemented as __eq__.  Then (1.0, 0.0, 0.0) and (1.001, 0.0, 0.0) would
> both key to the same value, cuz they're equal i.e. are both the same key,
> right?
>
> Wrong I think, per the session below.  The one object (1.0, 0.0, 0.0) is
> "in" a list of other objects (o1), thanks to fuzzy equality, but in adding
> to a dictionary, they key separately.  Instead of figuring it all out, lemme
> just put this out and there see if I fish up any expert patter.
>
> Kirby
>
>
>
> >> class Sometuple(object):
>         e = 0.01
>         def __init__(self,value):
>                 self.thetuple = value
>         def __eq__(self, other):
>                 if abs(self.thetuple[0]-other.thetuple[0])<self.e \
>                    and abs(self.thetuple[1]-other.thetuple[1])<self.e \
>                    and abs(self.thetuple[2]-other.thetuple[2])<self.e :
>                         return True
>                 else:
>                         return False
>
>
> >>> o0 = Sometuple((1,0,0))
> >>> o1 = Sometuple((1.001,0,0))
> >>> o0==o1
> True
> >>> thedict = {o0:'a'}
> >>> thedict
> {<__main__.Sometuple object at 0x00C93B90>: 'a'}
> >>> thedict[o1]='b'
> >>> thedict
> {<__main__.Sometuple object at 0x00C93B90>: 'a', <__main__.Sometuple object
> at 0x00C93D10>: 'b'}
>
> >>> o0 in [o1,o1,01]
> True
> >>> o0 in [o1,o1,o1]
> True
>
> >>> o1 in thedict.keys()
> True
> >>> o0 in thedict.keys()
> True
>
>
> _______________________________________________
> Edu-sig mailing list
> Edu-sig at python.org
> http://mail.python.org/mailman/listinfo/edu-sig
>


--
--Guido van Rossum (home page: http://www.python.org/~guido/)