[Raesputin]

Hi! I am working on a school assignment where we are gives a node-tree, and a node which we must find. Then we are to search the tree in a depth-first search(dfs) and breadth-search (bfs) and return the level the node is on (ratatosk is the node we have to find)

My code currently runs 4865ms for DFS and 4458 for BFS, im trying to optimize this a bit. I am not the greatest python coder but know some basic stuff. Any hints or suggestions would be great!

def bfs(rot):
    n = deque()
    n.append((rot, 0))
    while n:
        inga, lvl = n.popleft()
        if inga.ratatosk:
            return lvl
        if inga.barn:
            for i in inga.barn:
                n.append((i,lvl+1))

(Side note, input is given as a text file and which search is run is later in my code, just say if any of that is needed)

Thanks Dream!

[Nallo]

Maybe appending all children at once insted of one by one is faster?
Try to replace

if inga.barn:
    for i in inga.barn:
        n.append((i, lvl + 1))

with

if inga.barn:
    n.extend(zip(inga.barn, [lvl + 1] * len(inga.barn)))

You replace the for loop that runs at "python time" with something that runs at "C time" (at least I hope so).

Maybe you can get rid of the if as well:

n.extend(zip(inga.barn,[lvl + 1] * len(inga.barn)))

edit: on second thought it might be better to use a lazy evaluating version of zip, so that zip doesnt create an object in memory:

import itertools
n.extend(itertools.izip(inga.barn, itertools.repeat(lvl+1)))

though that only matters if the node.barn iterables tend to be long.

This post has been edited by Nallo: 02 September 2010 - 09:20 AM

[Raesputin]

Great I was actually just looking into using extend on my deque but wasn't quite sure I would be able to use it. Yes unfortunately some of the nodes have 'children' while others don't. Thanks for the tip!

[Nallo]

oops, my bad. I edited my post when there already was a reply. I should get rid of this bad habit.
Please look at the edited version of my above post.
And by the way I would like to know if performance really improved :-)