Python : 트리 평가자 최적화

Question

트리는 잘 연구 된 구조라는 것을 알고 있습니다.

나는 무작위로 많은 수식 트리를 생성 한 다음 적합성 속성으로 정렬하고 선택하는 프로그램을 작성하고 있습니다.

나는 'eval'이 평가할 수있는 문자열로 트리를 변환하는 클래스 MakeTreeInOrder()를 가지고있다.

하지만 여러 번 호출되며 시간에 맞게 최적화되어야합니다.

아래에는 테스트로 사용할 연속 번호를 추가하는 트리가 작성됩니다.

트리 구조에있는 표현식을 평가하는 데 최적화 된 방법이 있는지 궁금합니다. 나는 그것을 생각했다.

꽤 많이 사용되고 일부는 이미 이렇게했다.

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

이 예제에서는 numpy와 random을 가져 오지만 사용하지는 않습니다. 또한 몸이없는 "for i in range (2)"를 가지고 있습니다. 분명히 유효한 Python 코드는 아닙니다.

'cargo'와 노드가 포함해야하는 것을 정의하지 않습니다. '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 배 빠릅니다.

최상의 솔루션의 실제 트리 구조 또는 N의 상위 k (k < < N)가 필요한 경우 일 수 있습니다. 그렇다면 해당 트리를 다시 게시 할 수 있습니다. 결과를 생성하는 데 사용 된 RNG 상태를 추적합니다.예를 들어 :

당신이 최고 값을 찾았 으면

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 + ...