Ниже я суммировал некоторые из наиболее очевидных усилий по оптимизации, не особо затрагивая алгоритм. Все настройки выполняются на Python 2.6.4 в системе Linux x86-64.
Начальное время: 8,3 с
Низко висящие фрукты
желе уже указали на некоторые. Простое исправление уже немного улучшает время выполнения. Замена повторных вызовов на Operators.keys() путем повторного использования одного и того же списка также экономит некоторое время.
Время: 6,6 с
Использование itertools.count
Указано Дейвом Кирби , простое использование itertools.count также экономит ваше время:
from itertools import count
KS = count()
Время: 6,2 с
Улучшение конструктора
Поскольку вы не устанавливаете все атрибуты Node в ctor, вы можете просто переместить объявления атрибутов в тело класса:
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), если вам нужны другие значения, сначала прочитайте этот ответ по атрибутам класса .
Время: 5.2с
Использование namedtuple
В вашем коде вы больше не изменяете дерево выражений, поэтому вы также можете использовать неизменяемый объект. Node также не имеет никакого поведения, поэтому использование namedtuple является хорошим вариантом. Это, однако, имеет значение, поскольку элемент parent должен был быть отброшен на данный момент. Судя по тому факту, что вы могли бы вводить операторы с более чем двумя аргументами, вам в любом случае придется заменить влево / вправо список дочерних элементов, который снова будет изменяемым и позволит создать родительский узел перед всеми дочерними элементами.
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,1 с
Куда пойти отсюда
Если вы хотите иметь поддержку более двух операторов и / или поддержку родительского атрибута, используйте что-то вроде следующего кода:
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
Этот код также уменьшает глубину в зависимости от положения оператора.