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,oldnode,newnode):
if node is oldnode:
return newnode
else:
for varname,value in node.__dict__.items():
node.__dict__[varname]=replace_within_node(value,oldnode,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_returning_this_node=.4
if random.random()<=prob_of_returning_this_node:
return node
else:
if hasattr(node,'__dict__') and len(node.__dict__)>0:
return snip(random.choice(node.__dict__.values()))
else:
return node
def replace_within_node(node,oldnode,newnode):
if node is oldnode:
return newnode
else:
if hasattr(node,'__dict__'):
for varname,value in node.__dict__.items():
node.__dict__[varname]=replace_within_node(value,oldnode,newnode)
return node
def generate_random_program(currdepth,mindepth=2,maxde pth=4):
node=Node()
if currdepth==maxdepth:
return node
else:
node=Node()
for varname,value in node.__dict__.items():
node.__dict__[varname]=generate_random_program(currdepth+1,mindepth,maxd epth)
return node
def breed(father,mother):
#want to take subtree from each input parameter and swap them.
snip_from_mother=snip(mother.program)
snip_from_father=snip(father.program)
program_for_father=replace_within_node(father.prog ram,snip_from_father,snip_from_mother)
program_for_mother=replace_within_node(mother.prog ram,snip_from_mother,snip_from_father)
return program_for_father,program_for_mother
if __name__=='__main__':
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 1350
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__.items():
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_returning_this_node=.4 if random.random()<=prob_of_returning_this_node: return node else: if hasattr(node,'__dict__') and len(node.__dict__)>0: return snip(random.choice(node.__dict__.values())) else: return node
This becomes:
def snip(node):
prob_of_returning_this_node = 0.4
if random.random() <= prob_of_returning_this_node:
return node
else:
return snip(random.choice(node.trees))
def replace_within_node(node,oldnode,newnode): if node is oldnode: return newnode else: if hasattr(node,'__dict__'): for varname,value in node.__dict__.items(): node.__dict__[varname]=replace_within_node(value,oldnode,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***@removethiscyber.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***********@acm.org
Ok, I finally got it working! See below
On 2/4/06, Steven D'Aprano <st***@removethiscyber.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__.items(): 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...
|
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,...
|
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...
|
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...
|
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...
| |
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...
|
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...
|
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.
...
|
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...
|
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...
|
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...
| |
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...
|
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,...
|
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...
|
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...
|
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 ...
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |