Hi,
Would anyone be able to tell me why my function below is getting stuck
in infinite recusion?
Maybe I'm just tired and missing something obvious?
def replace_within_ node(node,oldno de,newnode):
if node is oldnode:
return newnode
else:
for varname,value in node.__dict__.i tems():
node.__dict__[varname]=replace_within _node(value,old node,newnode)
return node
At the end of this email I pasted the whole text of the sample code in
case it would help to see it in context or maybe step through it?
--
Gregory Piñero
Chief Innovation Officer
Blended Technologies
( www.blendedtechnologies.com)
#This is the code that's causing my problem:
#----------------------------------------------------------------------
import random
import sys
class Test_Class:
pass
class Node:
def __init__(self):
self.arg0=0
self.arg1=0
self.arg2=0
self.arg3=0
def snip(node):
prob_of_returni ng_this_node=.4
if random.random() <=prob_of_retur ning_this_node:
return node
else:
if hasattr(node,'_ _dict__') and len(node.__dict __)>0:
return snip(random.cho ice(node.__dict __.values()))
else:
return node
def replace_within_ node(node,oldno de,newnode):
if node is oldnode:
return newnode
else:
if hasattr(node,'_ _dict__'):
for varname,value in node.__dict__.i tems():
node.__dict__[varname]=replace_within _node(value,old node,newnode)
return node
def generate_random _program(currde pth,mindepth=2, maxdepth=4):
node=Node()
if currdepth==maxd epth:
return node
else:
node=Node()
for varname,value in node.__dict__.i tems():
node.__dict__[varname]=generate_rando m_program(currd epth+1,mindepth ,maxdepth)
return node
def breed(father,mo ther):
#want to take subtree from each input parameter and swap them.
snip_from_mothe r=snip(mother.p rogram)
snip_from_fathe r=snip(father.p rogram)
program_for_fat her=replace_wit hin_node(father .program,snip_f rom_father,snip _from_mother)
program_for_mot her=replace_wit hin_node(mother .program,snip_f rom_mother,snip _from_father)
return program_for_fat her,program_for _mother
if __name__=='__ma in__':
dragons=[Test_Class() for i in range(10)]
for dragon in dragons:
dragon.program= generate_random _program(0)
for i in range(100):
breed(dragons[0],dragons[1]) 4 1373
On Sat, 04 Feb 2006 02:18:27 -0500, Gregory Piñero wrote: Hi,
Would anyone be able to tell me why my function below is getting stuck in infinite recusion? Maybe I'm just tired and missing something obvious?
Your code is quite confusing, especially since there is very little
documentation. But I'll make a few comments:
#This is the code that's causing my problem: #----------------------------------------------------------------------
import random import sys
class Test_Class: pass class Node: def __init__(self): self.arg0=0 self.arg1=0 self.arg2=0 self.arg3=0
You appear to be iterating over these attributes. Hint: as soon as you
have more than two pieces of data with names like foo0, foo1, foo2...
you probably want something like this:
def __init__(self):
self.trees = [0, 0, 0, 0] # they aren't args, they are sub-trees
You are iterating over everything in __dict__ which is probably not what
you want. Your code has serious side-effects, because you are iterating
over ALL instance attributes, even the ones which are not nodes.
for varname,value in node.__dict__.i tems():
node.__dict__[varname] = value
# this touches all instance attributes
This is safer:
for index, value in enumerate(node. trees):
node.trees[index] = value
# this only touches what you want
Now people (and you!) can subclass your Node class without breaking it.
def snip(node): prob_of_returni ng_this_node=.4 if random.random() <=prob_of_retur ning_this_node: return node else: if hasattr(node,'_ _dict__') and len(node.__dict __)>0: return snip(random.cho ice(node.__dict __.values())) else: return node
This becomes:
def snip(node):
prob_of_returni ng_this_node = 0.4
if random.random() <= prob_of_returni ng_this_node:
return node
else:
return snip(random.cho ice(node.trees) )
def replace_within_ node(node,oldno de,newnode): if node is oldnode: return newnode else: if hasattr(node,'_ _dict__'): for varname,value in node.__dict__.i tems(): node.__dict__[varname]=replace_within _node(value,old node,newnode) return node
becomes:
def replace_within_ node(node, oldnode, newnode):
if node is oldnode:
return newnode
else:
for indx, nd in node.trees:
node.trees[indx] = replace_within_ node(nd, oldnode, newnode)
return node
This is quite a complex function. It seems to me, and perhaps I'm wrong,
you are walking the nodes and ... doing what? When you call this function,
what are the initial arguments you give it? In other words, what are
oldnode and newnode, and where do they get set?
In another post, you wrote:
"By the way, all I'm trying to do here is take two trees, randomly find
a sub-tree of each and swap the sub-trees. So if anyone has a simple
method for doing that I'm certainly open to that too."
How about something like this?
random.shuffle( node.trees)
That does more than you ask, but maybe it is useful to you. If you only
want to swap two, maybe something like this:
a, b = random.randint( 0,3), random.randint( 0,3)
node.trees[a], node.trees[b] = node.trees[b], node.trees[a]
I think what you really need to do here is spend some time building a
general tree class, before getting bogged down in the mechanics of your
application. For example, it would be really useful to print your Node,
and all its subtrees, so you can actually confirm that it contains what
you think it contains.
Why is this important? Because if your tree of nodes contains a loop, such
that node 1 has a subtree with node 2 that has a subtree with node 3 that
has a subtree with node 1 again, most recursive algorithms will never
halt, just keep cycling through the tree forever. Could that be your
problem? There is no way for us to tell from the information we've got.
--
Steven.
Thanks for the advice guys. See below.
On 2/4/06, Steven D'Aprano <st***@removeth iscyber.com.au> wrote: On Sat, 04 Feb 2006 02:18:27 -0500, Gregory Piñero wrote:
class Node: def __init__(self): self.arg0=0 self.arg1=0 self.arg2=0 self.arg3=0 You appear to be iterating over these attributes. Hint: as soon as you have more than two pieces of data with names like foo0, foo1, foo2... you probably want something like this:
def __init__(self): self.trees = [0, 0, 0, 0] # they aren't args, they are sub-trees
I'll try this.
This is quite a complex function. It seems to me, and perhaps I'm wrong, you are walking the nodes and ... doing what? When you call this function, what are the initial arguments you give it? In other words, what are oldnode and newnode, and where do they get set?
I posted the whole code, so that should be in there.
In another post, you wrote:
"By the way, all I'm trying to do here is take two trees, randomly find a sub-tree of each and swap the sub-trees. So if anyone has a simple method for doing that I'm certainly open to that too."
How about something like this?
random.shuffle( node.trees)
That does more than you ask, but maybe it is useful to you. If you only want to swap two, maybe something like this:
a, b = random.randint( 0,3), random.randint( 0,3) node.trees[a], node.trees[b] = node.trees[b], node.trees[a]
That's not quite what I want. I want to walk down each tree and get a
random subtree at a random depth.
I think what you really need to do here is spend some time building a general tree class, before getting bogged down in the mechanics of your application. For example, it would be really useful to print your Node, and all its subtrees, so you can actually confirm that it contains what you think it contains.
I had a print method for the tree, but that was making an infinite
recursion too!
Why is this important? Because if your tree of nodes contains a loop, such that node 1 has a subtree with node 2 that has a subtree with node 3 that has a subtree with node 1 again, most recursive algorithms will never halt, just keep cycling through the tree forever. Could that be your problem? There is no way for us to tell from the information we've got.
This sounds like what must be happening. I don't know how else it
could get caught up in an infinite recursion. The problem is, I don't
really know how to tell either ;-0
I guess I need to rethink this whole algorithm. Maybe flatten the
trees somehow and then do the swap? I'll let you guys know what I
come up with.
-- Steven.
-- http://mail.python.org/mailman/listinfo/python-list
--
Gregory Piñero
Chief Innovation Officer
Blended Technologies
( www.blendedtechnologies.com)
Gregory Piñero wrote: .... I want to walk down each tree and get a random subtree at a random depth.
Can you quantify that randomness? Should it be uniform at each level?
Thinking about this may be fruitful. I don't yet know whether you need
to see all leaves before you know which subtree to choose.
Because I am a clueless American, so I don't know if Piñero is a common
name or not. Are you perhaps related to the playwright?
--Scott David Daniels sc***********@a cm.org
Ok, I finally got it working! See below
On 2/4/06, Steven D'Aprano <st***@removeth iscyber.com.au> wrote: On Sat, 04 Feb 2006 02:18:27 -0500, Gregory Piñero wrote: class Node: def __init__(self): self.arg0=0 self.arg1=0 self.arg2=0 self.arg3=0
You appear to be iterating over these attributes. Hint: as soon as you have more than two pieces of data with names like foo0, foo1, foo2... you probably want something like this:
def __init__(self): self.trees = [0, 0, 0, 0] # they aren't args, they are sub-trees
You are iterating over everything in __dict__ which is probably not what you want. Your code has serious side-effects, because you are iterating over ALL instance attributes, even the ones which are not nodes.
for varname,value in node.__dict__.i tems(): node.__dict__[varname] = value # this touches all instance attributes
This is safer:
for index, value in enumerate(node. trees): node.trees[index] = value # this only touches what you want
Yep, this is what fixed it. Thanks Steve. I turns out that there is
a lot of other stuff in __dict__ that was messing me up and causing
the infinite recursion.
Terry was also kind of right in that I was never hitting my base case,
since I was getting stuck on a var in __dict__ and recursing forever
before I ever got to the base case.
-Greg This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: peter |
last post by:
Hello all,
Recently I've started to refactor my code ...(I'm using python 2.3.4)
I tried to add extra functionality to old functions non-intrusively.
When I used a construct, which involves renaming functions etc... I
came across some recursive problems. (a basic construct can be found
under the section BASIC CODE)
These problems do not occur when renaming objects. (see section EXTRA
CODE)
|
by: Andrew Edwards |
last post by:
The following function results in an infinite loop! After 5+ hours of
debugging, I am still unable to decipher what I am incorrectly. Any
assistance is greatly appreciated.
Thanks in advance,
Andrew
==========>Code<==========
//--------------------------------------------------------------------
|
by: Bill Borg |
last post by:
Hello,
I call a function recursively to find an item that exists *anywhere* down
the chain. Let's say I find it five layers deep. Now I've got what I need and
want to break out of that whole stack and continue execution at the point of
the initial call. Is that possible?
Thanks,
Bill
|
by: Microsoft |
last post by:
I've a table of users like this
id_user id_ref flg_enabled
1 0 1
2 1 1
3 1 0
4 2 1
id_user 1 created id_user 2 and 3
id_user 2 created id_user 4
|
by: Csaba Gabor |
last post by:
Inside a function, I'd like to know the call stack. By this I mean
that I'd like to know the function that called this one, that one's
caller and so on.
So I thought to do:
<script type='text/javascript'>
function myFunc(lev) {
// if (lev) return myFunc(lev-1);
var aStack=;
nextFunc = arguments.callee;
| |
by: pereges |
last post by:
Hello I need some ideas for designing a recursive function for my ray
tracing program.
The idea behind ray tracing is to follow the electromagnetic rays from
the source, as they hit the object.The object is triangulated. The
rays can undergo multiple reflections, diffractions etc of the same
object i.e. a ray hits a surface of the object, undergoes reflection
resulting in a reflected ray which can again hit a surface, corner or
edge...
|
by: ThEoNeAnDOnLy |
last post by:
I recently had an issue with my recursive project in class. Here is the code.
// Recursion.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <conio.h>
#include <iostream>
using namespace std;
|
by: Pivot_Tables |
last post by:
Hi,
I have created a recursive SQL Query in DB2 and it works fine until
some point in the tree where the data gets into infinite loop. Below
are some sample data from my relationship table.
Relationship Table
PARENT FIELD CHILD FIELD
AAA BBB
AAA CCC
|
by: KevinADC |
last post by:
This snippet of code provides several examples of programming techniques that can be applied to most programs.
using hashes to create unique results
static variable
recursive function
serialization
The code itself generates a list of strings comprised of random numbers. No number will be repeated within a string, and no string will be repeated within the list of strings. Following the code is a brief discussion of how the above...
|
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...
|
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...
| |
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,...
|
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...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
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...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
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
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |