Python: Optimizing, or at least getting fresh ideas for a tree generator.

Question

I have written a program that generates random expressions and then uses genetic techniques to select for fitness.

The following part of the program generates the random expression and stores it in a tree structure.

As this can get called billions of times during a run, I thought it should be optimized for time.

I'm new to programming and I work (play) by myself so, as much as I search on the inernet for

ideas, I'd like some input as I feel like I'm doing this in isolation.

The bottlenecks seem to be Node.init (), (22% of total time) and random.choice(), (14% of total time)

import random

def printTreeIndented(data, level=0):
    '''utility to view the tree
    '''
    if data == None:
         return
    printTreeIndented(data.right, level+1)
    print '  '*level + '  '+ str(data.cargo)#+ '  '+ str(data.seq)+ '  '+ str(data.branch)
    printTreeIndented(data.left, level+1)

#These are the global constants used in the Tree.build_nodes() method.
Depth = 5
Ratio = .6 #probability of terminating the current branch.
Atoms = ['1.0','2.0','3.0','4.0','5.0','6.0','7.0','8.0','9.0','x','x','x','x']
#dict of operators. the structure is: operator: number of arguements
Operators = {'+': 2, '-': 2, '*': 2, '/': 2, '**': 2}


class KeySeq:
    '''Iterator to produce sequential 
    integers for keys in Tree.thedict
    '''
    def __init__(self, data = 0):
        self.data = data
    def __iter__(self):
        return self
    def next(self):
        self.data = self.data + 1
        return self.data
KS = KeySeq()

class Node(object):
    '''
    '''
    def __init__(self, cargo, left=None, right=None):
        object.__init__(self)
        self.isRoot = False
        self.cargo = cargo
        self.left  = left
        self.right = right
        self.parent = None
        self.branch = None
        self.seq = 0


class Tree(object):
    def __init__(self):
        self.thedict = {}     #provides access to the nodes for further mutation and
        # crossbreeding.
        #When the Tree is instantiated, it comes filled with data.
        self.data = self.build_nodes()

# Uncomment the following lines to see the data and a crude graphic of the tree.
#        print 'data: '
#        for v in  self.thedict.itervalues():
#            print v.cargo,
#        print
#        print
#        printTreeIndented(self.data)

    def build_nodes (self,  depth = Depth, entry = 1,  pparent = None,
     bbranch = None):
        '''
        '''
        r = float()
        r = random.random()

        #If r > Ratio, it forces a terminal node regardless of
        #the value of depth.
        #If entry = 1, then it's the root node and we don't want
        # a tree with just a value in the root node.

        if (depth <= 0) or ((r > Ratio) and (not (entry))):
            '''
            Add a terminal node.
            '''
            this_atom = (random.choice(Atoms))
            this_atom = str(this_atom)
            this_node = Node(this_atom)
            this_node.parent = pparent
            this_node.branch = bbranch
            this_node.seq = KS.next()
            self.thedict[this_node.seq] = this_node
            return this_node

        else:
            '''
            Add a node that has branches.
            '''
            this_operator = (random.choice(Operators.keys()))

            this_node = Node(this_operator)
            if entry:
                this_node.isRoot = True
            this_node.parent = pparent
            this_node.branch = bbranch
            this_node.seq = KS.next()
            self.thedict[this_node.seq] = this_node
            #branch as many times as 'number of arguements'
            # it's only set up for 2 arguements now.
            for i in range(Operators[this_operator]):
                depth =(depth - 1)
                if i == 0:
                    this_node.left = (self.build_nodes(entry = 0, depth =(depth),
                     pparent = this_node, bbranch = 'left'))
                else:
                    this_node.right = (self.build_nodes(entry = 0, depth =(depth),
                     pparent = this_node, bbranch = 'right'))
            return this_node


def Main():
    for i in range(100000):
        t = Tree()
    return t

if __name__ == '__main__':
    rresult = Main()

Answer 1

You can omit lots of braces in your code, that's one of Python's benefits. E.g. when putting braces around conditions, like

if (depth <= 0) or ((r > Ratio) and (not (entry))):

just write

if depth <= 0 or (r > Ratio and not entry):

And I think there are a couple of redundant calls, e.g.

this_atom = str(this_atom)

(this_atom will already be a string, and building strings is always expensive, so just omit this line)

or the call to the object constructor

object.__init__(self)

which isn't necessary, either.

As for the Node.__init__ method being the "bottleneck": I guess spending most of your time there cannot be avoided, since when constructing trees like this there's not much else you'll be doing but creating new Nodes.

Answer 2

You can replace the KeySeq generator with itertools.count which does exactly the same thing but is implemented in C.

I don't see any way of speeding up the Node constructor. The call to random.choice you could optimise by inlining the code - cut & paste it from the source for the random module. This will eliminate a function call, which are relatively expensive in Python.

You could speed it up by running under psyco, which is a kind of JIT optimiser. However this only works for 32 bit Intel builds of Python. Alternatively you could use cython - this converts python(ish) code into C, which can be compiled into a Python C module. I say pythonish since there some things that cannot be converted, and you can add C data type annotations to make the generated code more efficient.

Answer 3

Below, I've summarized some of the more obvious optimization efforts, without really touching the algorithm much. All timings are done with Python 2.6.4 on a Linux x86-64 system.

Initial time: 8.3s

Low-Hanging Fruits

jellybean already pointed some out. Just fixing those already improves the runtime a little bit. Replacing the repeated calls to Operators.keys() by using the same list again and again also saves some time.

Time: 6.6s

Using itertools.count

Pointed out by Dave Kirby, simply using itertools.count also saves you some time:

from itertools import count
KS = count()

Time: 6.2s

Improving the Constructor

Since you're not setting all attributes of Node in the ctor, you can just move the attribute declarations into the class body:

class Node(object):
    isRoot = False
    left  = None
    right = None
    parent = None
    branch = None
    seq = 0

    def __init__(self, cargo):
        self.cargo = cargo

This does not change the semantics of the class as far as you're concerned, since all values used in the class body are immutable (False, None, 0), if you need other values, read this answer on class attributes first.

Time: 5.2s

Using namedtuple

In your code, you're not changing the expression tree any more, so you might as well use an object that is immutable. Node also does not have any behavior, so using a namedtuple is a good option. This does have an implication though, since the parent member had to be dropped for now. Judging from the fact that you might introduce operators with more than two arguments, you would have to replace left/right with a list of children anyway, which is mutable again and would allow creating the parent node before all the children.

from collections import namedtuple
Node = namedtuple("Node", ["cargo", "left", "right", "branch", "seq", "isRoot"])
# ...
    def build_nodes (self,  depth = Depth, entry = 1,  pparent = None,
         bbranch = None):
        r = random.random()

        if (depth <= 0) or ((r > Ratio) and (not (entry))):
            this_node = Node(
                random.choice(Atoms), None, None, bbranch, KS.next(), False)
            self.thedict[this_node.seq] = this_node
            return this_node

        else:
            this_operator = random.choice(OpKeys)

            this_node = Node(
              this_operator,
              self.build_nodes(entry = 0, depth = depth - 1,
                               pparent = None, bbranch = 'left'),
              self.build_nodes(entry = 0, depth = depth - 2,
                               pparent = None, bbranch = 'right'),
              bbranch, 
              KS.next(), 
              bool(entry))

            self.thedict[this_node.seq] = this_node    
            return this_node

I've kept the original behavior of the operand loop, that decrements the depth at each iteration. I'm not sure this is wanted behavior, but changing it increases runtime and therefore makes comparison impossible.

Final time: 4.1s

Where to go from here

If you want to have support for more than two operators and/or support for the parent attribute, use something along the lines of the following code:

from collections import namedtuple
Node = namedtuple("Node", ["cargo", "args", "parent", "branch", "seq", "isRoot"])

    def build_nodes (self,  depth = Depth, entry = 1,  pparent = None,
         bbranch = None):
        r = random.random()

        if (depth <= 0) or ((r > Ratio) and (not (entry))):
            this_node = Node(
                random.choice(Atoms), None, pparent, bbranch, KS.next(), False)
            self.thedict[this_node.seq] = this_node
            return this_node

        else:
            this_operator = random.choice(OpKeys)

            this_node = Node(
              this_operator, [], pparent, bbranch,
              KS.next(), bool(entry))
            this_node.args.extend(
              self.build_nodes(entry = 0, depth = depth - (i + 1),
                               pparent = this_node, bbranch = i)
              for i in range(Operators[this_operator]))

            self.thedict[this_node.seq] = this_node    
            return this_node

This code also decreases the depth with the operator position.