473,671 Members | 2,430 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Recursion limit problems

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__.i teritems():
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!

May 11 '07 #1
10 3316

"elventear" <el*******@gmai l.comwrote in message
news:11******** **************@ u30g2000hsc.goo glegroups.com.. .
| 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__.i teritems():
| 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


May 12 '07 #2
En Fri, 11 May 2007 19:17:57 -0300, elventear <el*******@gmai l.com>
escribió:
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.h tml#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)."

--
Gabriel Genellina

May 12 '07 #3
On May 11, 11:54 pm, "Terry Reedy" <tjre...@udel.e duwrote:
>
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!

May 14 '07 #4
On May 12, 12:25 am, "Gabriel Genellina" <gagsl-...@yahoo.com.a r>
wrote:
En Fri, 11 May 2007 19:17:57 -0300, elventear <elvent...@gmai l.com
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!

May 14 '07 #5

"elventear" <el*******@gmai l.comwrote in message
news:11******** **************@ y80g2000hsf.goo glegroups.com.. .
On May 12, 12:25 am, "Gabriel Genellina" <gagsl-...@yahoo.com.a r>
wrote:
En Fri, 11 May 2007 19:17:57 -0300, elventear <elvent...@gmai l.com>
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

May 14 '07 #6
En Mon, 14 May 2007 12:35:16 -0300, elventear <el*******@gmai l.com>
escribió:
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).

--
Gabriel Genellina

May 14 '07 #7
On May 14, 1:20 pm, "Terry Reedy" <tjre...@udel.e duwrote:
>
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!

May 14 '07 #8
On May 14, 2:03 pm, "Gabriel Genellina" <gagsl-...@yahoo.com.a r>
wrote:
>
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!

May 14 '07 #9
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()
---------------

will give you only one call to __eq__

Diez
May 15 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
44947
by: Georgy Pruss | last post by:
Sometimes I get this error. E.g. >>> sum = lambda n: n<=1 or n+sum(n-1) # just to illustrate the error >>> sum(999) 499500 >>> sum(1000) ............ RuntimeError: maximum recursion depth exceeded
10
2509
by: paulw | last post by:
Hi Please give problems that "HAS TO" to use recursion (recursive calls to itself.) Preferrably real world examples, not knights tour. I'm thinking about eliminating the use of stack... Thanks.
9
6715
by: pengypenguin | last post by:
As we know, Javascript suffers an insufferable lack of a wait() or sleep() function, and so setTimeOut must step in to take up the slack. A function can use setTimeOut like sleep() by calling itself after x seconds. This begs a few questions: Is this design building enormous calling stacks to nowhere? Will the users machine eventually run out of memory space to contain this stack? How can this be avoided? Thanks, -- Whit Nelson
13
4516
by: robert | last post by:
My code does recursion loops through a couple of functions. Due to problematic I/O input this leads sometimes to "endless" recursions and after expensive I/O to the Python recursion exception. What would be a good method to detect recursion loops and stop it by user-Exception (after N passes or some complex criteria) without passing a recursion counter parameter through all the funcs? Robert
6
2933
by: Andre Kempe | last post by:
hej folks. i have a heap with fixed size and want to determine the depth of a element with given index at compile-time. therefore i wrote some templates. however, when i use template index_properties<unsigned int>, i get a compiler-error, complaining about the template-recursion of __index_properties__. when i add a partially specialized template (the three commented lines) to stop the template-recursion, it works. does anyone how to...
14
2659
by: asit | last post by:
#include <stdio.h> int main() { int i; for(i=1;i<=10;i++) main(); printf("C is urs.."); return 0; }
2
6561
by: Victor Lin | last post by:
Hi, I encounter a problem with pickle. I download a html from: http://www.amazon.com/Magellan-Maestro-4040-Widescreen-Navigator/dp/B000NMKHW6/ref=sr_1_2?ie=UTF8&s=electronics&qid=1202541889&sr=1-2 and parse it with BeautifulSoup. This page is very huge. When I use pickle to dump it, a RuntimeError: maximum recursion depth
30
8293
by: Jeff Bigham | last post by:
So, it appears that Javascript has a recursion limit of about 1000 levels on FF, maybe less/more on other browsers. Should such deep recursion then generally be avoided in Javascript? Surprisingly, deep recursion actually isn't that slow for what I'm doing. Programming this task recursively is so much more straightforward to me, but currently I'm forced to use an ugly hack to avoid going over the 1000 level limit. Of course, it could...
35
4717
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
8481
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8400
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
8924
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8672
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7441
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
4412
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2817
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2058
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
2
1814
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.