트리 탐색에서 메모리 관리 루아 함수

Question

노드에 0-N 하위 노드가있을 수있는 임의의 노드를 반환하는 두 개의 알고리즘이 있습니다 (현재 노드는 node이고 노드의 첫 번째 자식 노드는 node[1] 등). 첫 번째 알고리즘 인 uniform selection은 트리에서 임의로 임의의 노드를 선택합니다. 반환 할 노드를 트리 아래로 이동할 때이 노드를 현재 확률 1/(지금까지 본 노드 수)로 대체합니다. 아래 루아 코드.

function uniformSelect(node) 
    local chosen = node 

    function choose(node, counter) 
     counter = counter + 1 
     local probability = 1/counter 
     if math.random() < probability then 
      chosen = node 
     end 

     for i = 1, node.arity do 
      choose(node[i], counter) 
     end 
    end 

    choose(node, 0) 
    return chosen 
end 

은 두 번째 알고리즘은, 그것은 현재이며,이 노드가 반환되지 않으면 P. 다음 노드의 아이들에게 이동의 확률이 P1이다 주어진 확률로 돌려 노드보고, 나무를 아래로 이동 P2 ... PN 아래 1. 루아 코드.

function select(node, prob) 
    local r = math.random() 
    if r < prob or node.arity == 0 then 
     return node 
    end 

    local p = {} 
    if node.arity == 1 then 
     table.insert(p, 1) 
    else 
     local total = count(node) -- total number of nodes below this one 
     for i = 1, node.arity do 
      -- insert probability of moving to child i into p 
      table.insert(p, (count(node[i])+1)/total) 
     end 

    end 
    -- move to a child node chosen by roulette wheel selection 
    return select(node[roulette(p)], prob) 
end 

이러한 알고리즘은 유전 프로그래밍 프레임 워크에서 사용됩니다. 첫 번째 알고리즘 인 유니폼 선택을 사용하면 속도와 메모리면에서 처음에는 잘 작동합니다. 그러나 두 번째는 많은 세대에 걸쳐 많은 수의 사람들과 사용할 수 없으며 사용하는 메모리는 폭발합니다. 나는이 메모리 증가를 그래프로 그렸습니다. 파란색 선 "prob"는 두 번째 알고리즘 인 select입니다. 이 꼬리 재귀처럼

은 나에게, select 보인다. 또한 가비지 컬렉터에게 도움이되는지 확인하기 위해 명시 적으로 시도했지만, 성장 속도는 조금 느려지지만 성장은 여전히 ​​엄청납니다.

아무도이 차이를 일으키는 원인을 말해 줄 수 있습니까?

Answer 1

나는 생산되는 나무의 평균 깊이를 그래프로 표시하고 답을 찾았습니다. select 함수를 사용한 교차 작업은 모집단에있는 나무의 평균 깊이를 늘려 프로그램이 느려지고 더 많은 메모리를 사용하게 만듭니다. 이 페이지에서 값을 잡고 로컬 [지역 rand_idx = 룰렛 (P)]에 저장하면 어떻게됩니까