我编写了一个生成随机表达式然后使用遗传技术选择适合度的程序。
程序的以下部分生成随机表达式并将其存储在树结构中。
由于这在运行期间可能被调用数十亿次，我认为应该针对时间进行优化。
我是编程新手，我自己工作(玩)，就像我在 inernet 上搜索一样多
想法，我想要一些意见，因为我觉得我是在孤立地做这件事。
瓶颈似乎是Node.init()，(占总时间的22%)和random.choice()，(占总时间的14%)
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()
请您参考如下方法:
下面，我总结了一些更明显的优化工作，但并未真正触及算法。所有计时均在 Linux x86-64 系统上使用 Python 2.6.4 完成。
初始时间:8.3s
唾手可得的果实
jellybean已经指出了一些。只需修复这些问题就可以稍微改善运行时间。通过一次又一次地使用相同的列表来替换对 Operators.keys() 的重复调用也可以节省一些时间。
时间:6.6s
使用 itertools.count
由 Dave Kirby 指出, 只需使用 itertools.count还可以节省您一些时间:
from itertools import count
KS = count()
时间:6.2s
改进构造函数
因为你没有在 ctor 中设置 Node 的所有属性，你可以只将属性声明移动到类主体中:
class Node(object):
isRoot = False
left = None
right = None
parent = None
branch = None
seq = 0
def __init__(self, cargo):
self.cargo = cargo
就您而言，这不会改变类的语义，因为类主体中使用的所有值都是不可变的(False、None、0)，如果你需要其他值，阅读this answer on class attributes首先。
时间:5.2s
使用命名元组
在您的代码中，您不再更改表达式树，因此您不妨使用一个不可变的对象。 Node 也没有任何行为，所以使用 namedtuple是一个不错的选择。但这确实有一个含义，因为现在必须删除 parent 成员。从您可能会引入带有两个以上参数的运算符这一事实来看，您无论如何都必须将 left/right 替换为子节点列表，这又是可变的，并且允许在所有子节点之前创建父节点。
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
我保留了操作数循环的原始行为，即在每次迭代时递减深度。我不确定这是想要的行为，但更改它会增加运行时间，因此无法进行比较。
结束时间:4.1s
从这里去哪里
如果您希望支持两个以上的运算符和/或支持 parent 属性，请使用类似于以下代码的内容:
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
此代码还随着运算符(operator)的位置减少深度。
