Recursion limit problems

[elventear]

Hello everyone,

I am runing into recursion limit problems. I have found that the
culprit was related to the __hash__ function that I had assigned to
the objects that were added to a set.

Basically my __hash__ function is the following:

def __hash__(self):
out_int = 0
for property,value in self:
out_int ^= hash( property )^hash( value )

return out_int

And the iterator for this object is:

def __iter__(self):
for property,value in self.__dict__.iteritems():
yield property,value

After commenting the __hash__ function and using the default provided
by Python (I suppose it is based on the position in memory of the
object), the recursion limit problems went away. (This problem was
happening even after increasing the recursion limit to the maximum of
my platform, MacOSX).

I am not that versed in Python, so I don't know exactly I could do to
overcome this problem, any ideas are deeply appreciated.

Thanks!

 

[Terry Reedy]

| Hello everyone,
|
| I am runing into recursion limit problems. I have found that the
| culprit was related to the __hash__ function that I had assigned to
| the objects that were added to a set.
|
| Basically my __hash__ function is the following:
|
| def __hash__(self):
| out_int = 0
| for property,value in self:
| out_int ^= hash( property )^hash( value )
|
| return out_int
|
| And the iterator for this object is:
|
| def __iter__(self):
| for property,value in self.__dict__.iteritems():
| yield property,value
|
| After commenting the __hash__ function and using the default provided
| by Python (I suppose it is based on the position in memory of the
| object), the recursion limit problems went away. (This problem was
| happening even after increasing the recursion limit to the maximum of
| my platform, MacOSX).
|
| I am not that versed in Python, so I don't know exactly I could do to
| overcome this problem, any ideas are deeply appreciated.

Without seeing the full code and the exception traceback, my guess is that
your __hash__ somehow calls itself due to a refence loop in your object. A
simple example of a loop:
a = []; a.append(a)
Now, list objects are not hashable, but if they were, and the hash were
value based (like your), then hash(a) would call hash(a) would call
hash(a)....

Suggestion: put print id(self) in __hash__ and see if you get a repeat.
And maybe reduce the recursion limit to reduce the traceback listing ;-)

Terry Jan Reedy

 

[Gabriel Genellina]

I am runing into recursion limit problems. I have found that the
culprit was related to the __hash__ function that I had assigned to
the objects that were added to a set.

As T. Reedy said, probably you have a recursive structure.

These comments about __hash__, mutability and dict behavior are applicable
to sets too <http://docs.python.org/ref/customization.html#l2h-196> :

"The only required property is that objects which compare equal have the
same hash value; it is advised to somehow mix together (e.g., using
exclusive or) the hash values for the components of the object that also
play a part in comparison of objects. If a class does not define a
__cmp__() method it should not define a __hash__() operation either; if it
defines __cmp__() or __eq__() but not __hash__(), its instances will not
be usable as dictionary keys. If a class defines mutable objects and
implements a __cmp__() or __eq__() method, it should not implement
__hash__(), since the dictionary implementation requires that a key's hash
value is immutable (if the object's hash value changes, it will be in the
wrong hash bucket)."

 

[elventear]

Without seeing the full code and the exception traceback, my guess is that
your __hash__ somehow calls itself due to a refence loop in your object. A
simple example of a loop:
a = []; a.append(a)
Now, list objects are not hashable, but if they were, and the hash were
value based (like your), then hash(a) would call hash(a) would call
hash(a)....

You were right, I had forgotten that in some instances I had some data
that recursively pointed to the source. Thanks!

 

[elventear]

En Fri, 11 May 2007 19:17:57 -0300, elventear <[email protected]>
escribió:
"The only required property is that objects which compare equal have the
same hash value; it is advised to somehow mix together (e.g., using
exclusive or) the hash values for the components of the object that also
play a part in comparison of objects. If a class does not define a
__cmp__() method it should not define a __hash__() operation either; if it
defines __cmp__() or __eq__() but not __hash__(), its instances will not
be usable as dictionary keys. If a class defines mutable objects and
implements a __cmp__() or __eq__() method, it should not implement
__hash__(), since the dictionary implementation requires that a key's hash
value is immutable (if the object's hash value changes, it will be in the
wrong hash bucket)."

Thanks for the information. I have a doubt regarding the wording in
the paragraph on top.

Since I am defining a hash for my object, it makes sense that I should
be able to define equality. But I am not sure about inequality, in my
specific case. The paragraph above mentions that __cmp__ should be
defined if I define a __hash__, but in the default behaviour of
__cmp__ inequality is included. So what should I do? Also why is
equality necessary to be defined? Do dicts only use __hash__ or do
they use equality as well?

Thanks!

 

[Terry Reedy]

En Fri, 11 May 2007 19:17:57 -0300, elventear <[email protected]>
escribió:
"The only required property is that objects which compare equal have the
same hash value; it is advised to somehow mix together (e.g., using
exclusive or) the hash values for the components of the object that also
play a part in comparison of objects. If a class does not define a
__cmp__() method it should not define a __hash__() operation either; if
it

I suspect/believe that the above should be __cmp__() or __eq__() both for
uniformity with the usage below and also because objects do not need to be
ordered (__cmp__) to be used as dict keys.

defines __cmp__() or __eq__() but not __hash__(), its instances will not
be usable as dictionary keys. If a class defines mutable objects and
implements a __cmp__() or __eq__() method, it should not implement
__hash__(), since the dictionary implementation requires that a key's
hash
value is immutable (if the object's hash value changes, it will be in the
wrong hash bucket)."

Thanks for the information. I have a doubt regarding the wording in
the paragraph on top.

Since I am defining a hash for my object, it makes sense that I should
be able to define equality. But I am not sure about inequality, in my
specific case. The paragraph above mentions that __cmp__ should be
defined if I define a __hash__, but in the default behaviour of
__cmp__ inequality is included. So what should I do? Also why is
equality necessary to be defined? Do dicts only use __hash__ or do
they use equality as well?
===============

Dicts first compare hashes and if they are equal, then check equality. If
two unequal strings have the same hash value, as is possible of course
(given only 2**32 possible hashes and many more possible strings), both can
still be used as different keys. Ditto for unequal numbers. Or for a
number and string with equal hashes. And so on. The first quoted
sentence, about mixing, is directed at minimizing such hash collisions.

Terry Jan Reedy

 

[Gabriel Genellina]

Since I am defining a hash for my object, it makes sense that I should
be able to define equality. But I am not sure about inequality, in my
specific case. The paragraph above mentions that __cmp__ should be
defined if I define a __hash__, but in the default behaviour of
__cmp__ inequality is included. So what should I do? Also why is
equality necessary to be defined? Do dicts only use __hash__ or do
they use equality as well?

Dicts and sets use the key's hash value to determine the "bucket" where
the key will be placed, and == to distingish between different objects
with the same hash value.
That is, you should define __hash__ and one of (__cmp__ or __eq__).
__neq__ (inequality) isn't required nor used by dict/set implementation.
(Anyway, Python will transform a!=b into not(a==b), if __neq__ isn't
defined). Neither <, <=, >, >= are used.
The important thing is that, if two objects compare equal, they must have
the same hash value. That is: (a==b) => (hash(a)==hash(b)) (the reciprocal
is not true).

 

[elventear]

Dicts first compare hashes and if they are equal, then check equality. If
two unequal strings have the same hash value, as is possible of course
(given only 2**32 possible hashes and many more possible strings), both can
still be used as different keys. Ditto for unequal numbers. Or for a
number and string with equal hashes. And so on. The first quoted
sentence, about mixing, is directed at minimizing such hash collisions.

Now my question is, since the definition mentions __cmp__ explicity.
Is that the only function it uses? What if __ne__, __eq__ are defined,
but not __cmp__?

Finally I am still confused about the inequality. Does dict only care
about the __cmp__ ouput being 0 and ignore the rest, or does it make
use of -1,1 as well? Could I just say that 0 defines equality in my
object and 1 otherwise, without regard of it being less than or
greater than?

Thanks!

 

[elventear]

Dicts and sets use the key's hash value to determine the "bucket" where
the key will be placed, and == to distingish between different objects
with the same hash value.
That is, you should define __hash__ and one of (__cmp__ or __eq__).
__neq__ (inequality) isn't required nor used by dict/set implementation.
(Anyway, Python will transform a!=b into not(a==b), if __neq__ isn't
defined). Neither <, <=, >, >= are used.
The important thing is that, if two objects compare equal, they must have
the same hash value. That is: (a==b) => (hash(a)==hash(b)) (the reciprocal
is not true).

Cool! I think this answers my last question.

Thanks!

 

[Diez B. Roggisch]

with the same hash value.

That is, you should define __hash__ and one of (__cmp__ or __eq__).
__neq__ (inequality) isn't required nor used by dict/set implementation.
(Anyway, Python will transform a!=b into not(a==b), if __neq__ isn't
defined). Neither <, <=, >, >= are used.

No, it won't:

http://docs.python.org/ref/customization.html#l2h-190

"""
There are no implied relationships among the comparison operators. The truth
of x==y does not imply that x!=y is false. Accordingly, when defining
__eq__(), one should also define __ne__() so that the operators will behave
as expected.
"""

---------------------
class Foo(object):

def __eq__(self, other):
print "__eq__"
return id(self) == id(other)


Foo() == Foo()
Foo() != Foo()

 

[Gabriel Genellina]

No, it won't:

http://docs.python.org/ref/customization.html#l2h-190

Ouch, sorry, my bad!