473,714 Members | 2,539 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 3324

"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
44950
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
2516
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
6724
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
4525
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
2936
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
2661
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
6563
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
8299
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
4727
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
8797
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
8704
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
9171
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9071
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
1
6629
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4462
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
3156
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
2514
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2107
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.