Python: оптимизация дерева оценки

Question

Я знаю, что дерево - это хорошо изученная структура.

Я пишу программу, которая случайным образом генерирует множество деревьев выражений, а затем сортирует и выбирает по атрибуту пригодности.

У меня есть класс MakeTreeInOrder (), который превращает дерево в строку, которую может вычислять eval.

но он вызывается много раз и должен быть оптимизирован для времени.

ниже - это функция, которая создает дерево, которое добавляет последовательные числа для использования в качестве теста.

Мне было интересно, есть ли оптимизированный способ оценки выражения в древовидной структуре. Я понял, что

что он используется довольно часто, и некоторые уже сделали это.

import itertools
from collections import namedtuple 

#Further developing Torsten Marek's second suggestion

KS = itertools.count()
Node = namedtuple("Node", ["cargo", "args"]) 

def build_nodes (depth = 5):     
    if (depth <= 0): 
        this_node = Node((str(KS.next())), [None, None])
        return this_node 
    else:
        this_node = Node('+', []) 
        this_node.args.extend( 
          build_nodes(depth = depth - (i + 1))                             
          for i in range(2)) 

        return this_node

Ниже приведен код, который, я думаю, можно сделать намного быстрее. И я надеялся на некоторые идеи.

class MakeTreeInOrder(object):
    def __init__(self, node):
        object.__init__(self)
        self.node = node
        self.str = ''
    def makeit(self, nnode = ''):
        if nnode == '':
            nnode = self.node
        if nnode == None: return
        self.str +='('
        self.makeit(nnode.args[0])
        self.str += nnode.cargo
        self.makeit(nnode.args[1])
        self.str+=')'
        return self.str

def Main():
    this_tree = build_nodes()
    expression_generator = MakeTreeInOrder(this_tree)
    this_expression = expression_generator.makeit()
    print this_expression
    print eval(this_expression)

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

Answer 1

Добавление оттенка ориентации объекта делает вещи проще. Иметь подклассы Node для каждой вещи в вашем дереве и использовать метод 'eval' для их оценки.

import random

class ArithmeticOperatorNode(object):
    def __init__(self, operator, *args):
        self.operator = operator
        self.children = args
    def eval(self):
        if self.operator == '+':
            return sum(x.eval() for x in self.children)
        assert False, 'Unknown arithmetic operator ' + self.operator
    def __str__(self):
        return '(%s)' % (' ' + self.operator + ' ').join(str(x) for x in self.children)

class ConstantNode(object):
    def __init__(self, constant):
        self.constant = constant
    def eval(self):
        return self.constant
    def __str__(self):
        return str(self.constant)

def build_tree(n):
    if n == 0:
        return ConstantNode(random.randrange(100))
    else:
        left = build_tree(n - 1)
        right = build_tree(n - 1)
        return ArithmeticOperatorNode('+', left, right)

node = build_tree(5)
print node
print node.eval()

Чтобы оценить дерево, просто вызовите .eval () на узле верхнего уровня.

node = build_tree(5)
print node.eval()

Я также добавил метод __str__ для преобразования дерева в строку, чтобы вы могли видеть, как это обобщается для других функций дерева. В данный момент он выполняет «+», но, надеюсь, понятно, как расширить это на весь спектр арифметических операций.

Answer 2

Ваш пример импортирует случайные и случайные числа, но никогда не использует их. У него также есть «для i в диапазоне (2))» без тела. Это явно недопустимый код Python.

Вы не определяете, какой «груз» и какие узлы должны содержать. Кажется, что «cargo» - это число, поскольку оно происходит из itertools.count (). Next (). Но это не имеет смысла, так как вы хотите, чтобы результат был eval'able строкой Python.

Если вы выполняете разовую оценку дерева, то самым быстрым решением было бы оценить его непосредственно на месте, но без реального примера данных, с которыми вы работаете, я не могу показать пример .

Если вы хотите сделать это еще быстрее, смотрите дальше вверх по течению. Почему вы генерируете дерево, а затем оцениваете его? Разве вы не можете оценить компоненты непосредственно в коде, который в настоящее время генерирует древовидную структуру? Если у вас есть такие операторы, как «+» и «*», рассмотрите возможность использования вместо этого operator.add и operator.mul, которые могут работать непосредственно с данными без промежуточного шага.

== Обновление ==

Это основано на ответе Пола Ханкина. Я убрал промежуточную древовидную структуру и просто оценил выражение напрямую.

def build_tree2(n):
    if n == 0:
        return random.randrange(100)
    else:
        left = build_tree2(n-1)
        right = build_tree2(n-1)
        return left+right

Это примерно в 5 раз быстрее, чем решение Павла.

Возможно, вам нужно знать фактическую древовидную структуру наилучшего решения или верхнюю часть k N, где k << N. Если это так, то вы можете восстановить эти деревья в последующем, если вы также сохраните отслеживание состояния ГСЧ, используемого для генерации результатов. Например: </p>

def build_tree3(n, rng=random._inst):
    state = rng.getstate()
    return _build_tree3(n, rng.randrange), state

def _build_tree3(n, randrange):
    if n == 0:
        return randrange(100)
    else:
        left = _build_tree3(n-1, randrange)
        right = _build_tree3(n-1, randrange)
        return left+right

Как только вы найдете лучшие значения, используйте ключ для восстановления дерева

# Build Paul's tree data structure given a specific RNG
def build_tree4(n, rng):
    if n == 0:
        return ConstantNode(rng.randrange(100))
    else:
        left = build_tree4(n-1, rng)
        right = build_tree4(n-1, rng)
        return ArithmeticOperatorNode("+", left, right)

# This is a O(n log(n)) way to get the best k.
# An O(k log(k)) time solution is possible.
rng = random.Random()
best_5 = sorted(build_tree3(8, rng) for i in range(10000))[:5]
for value, state in best_5:
    rng.setstate(state)
    tree = build_tree4(8, rng)
    print tree.eval(), "should be", value
    print "  ", str(tree)[:50] + " ..."

Вот как это выглядит, когда я запускаю его

10793 should be 10793
   ((((((((92 + 75) + (35 + 69)) + ((39 + 79) + (6 +  ...
10814 should be 10814
   ((((((((50 + 63) + (6 + 21)) + ((75 + 98) + (76 +  ...
10892 should be 10892
   ((((((((51 + 25) + (5 + 32)) + ((40 + 71) + (17 +  ...
11070 should be 11070
   ((((((((7 + 83) + (77 + 56)) + ((16 + 29) + (2 + 1 ...
11125 should be 11125
   ((((((((69 + 80) + (11 + 64)) + ((33 + 21) + (95 + ...