나는 세 가지 기본 방법 중 하나가 자주 규제가 포함되며 그 중 하나에는 추가 정보가 포함됩니다. 나는이 중 하나 또는 다른 것을하는 것이 피할 수 없다고 생각합니다. 추가 정보 하나부터 시작하겠습니다 :
각 노드에는 자손의 수를 나타내는 count
숫자를 저장하십시오. 모든 노드에 대해 왼쪽과 오른쪽으로 이동할지 여부를 왼쪽 노드의 자식 수와 비교하여 알려면 해당 노드에 대해 1에서 count
사이의 숫자가 필요합니다. 여기 알고리즘입니다 :
n := random integer between 1 and root.count
node := route
while node.count != 1
if n <= node.left.count
node = node.left
else
node = node.right
n = n - node.left.count
그래서, 기본적으로, 우리는 모든 노드에서 왼쪽에서 오른쪽 순서를 부과하고 왼쪽에서 n 번째 하나를 선택하고 있습니다. 이것은 상당히 빠르며 오직 O (tree of depth) 만 가지고 있습니다. 모든 노드 레이블을 포함하는 벡터를 만드는 것과 같은 일을하지 않고도 할 수있는 최선의 방법입니다. 또한 수를 정정해야하기 때문에 트리의 변경 사항에 O (트리의 깊이) 오버 헤드를 추가합니다. 다른 방법으로 나무를 전혀 바꾸지 않고 랜덤 노드를 많이 선택하려는 경우에는 글 머리 기호를 비트하고 모든 노드 레이블을 벡터에 넣으십시오. 그렇게하면 O (N) 초기 설정 시간 후에 O (1)에서 임의의 것을 선택할 수 있습니다.
그러나 저장 공간을 모두 사용하지 않으려는 경우에는 다음과 같이 많은 규제가 필요합니다. 먼저 트리의 깊이에 대한 경계 (B로 표시)를 찾아야합니다 (필요한 경우 N-1을 사용할 수 있지만 분명히 매우 느슨한 경계입니다.) 찾을 수있는 경계가 좁을수록 알고리즘이 빠릅니다 실행). 다음으로 무작위로 가능한 노드 레이블을 생성하겠습니다. 2^(B + 1) -1 개의 가능성이 있습니다. 예를 들어, 문자열 "0011"과 "11"은 완전히 다른 문자열이므로 2^B가 아닙니다. 결과적으로, 우리는 0과 B 사이의 모든 가능한 길이의 이진 문자열을 계산해야합니다. 분명히 우리는 길이가 2 i 인 문자열을 가지고 있습니다. 따라서 길이가 i 이하인 문자열의 경우 sum (i = 0 ~ B) {2^i} = 2^(B + 1) -1이됩니다. 따라서 0과 2^(B + 1) -2 사이의 숫자를 선택한 다음 해당 노드 레이블을 찾을 수 있습니다. 물론 숫자에서 노드 레이블로의 매핑은 간단하지 않으므로 여기에서 설명하겠습니다.
우리는 선택한 숫자를 일반적인 방식으로 비트 열로 변환합니다. 그런 다음 왼쪽에서부터 읽으면 첫 번째 숫자가 0이면 노드 레이블은 오른쪽에있는 나머지 문자열입니다 (사용하지 않을 가능성이있는 유효한 노드 레이블 일 수있는 빈 문자열 일 수도 있음). 첫 번째 숫자가 1이면 우리는 그것을 버리고이 과정을 반복합니다. 따라서, B = 4이면, 노드 레이블 "0001"은 "00001"의 번호에서 나옵니다.노드 레이블 "001"은 "10001"의 번호에서옵니다. 노드 레이블 "01"은 번호 "11001"에서 나옵니다. 노드 레이블 "1"은 숫자 "11101"에서옵니다. 그리고 노드 레이블 ""은 "11110"의 번호에서옵니다. 이 스킴에서는 유효한 해석이없는 2^(B + 1) -1 (이 경우 "11111") 숫자는 포함하지 않았습니다. 나는 독자들에게 길이 0에서 B까지의 모든 스트링이이 스킴 하에서 표현 될 수 있음을 증명하기위한 운동으로 남겨 둘 것이다. 그것을 증명하려고 노력하기보다는, 나는 그것이 작동 할 것이라고 단언 할 것입니다.
이제 노드 레이블이 생겼습니다. 다음 단계는 해당 레이블이 트리를 통과하여 존재하는지 확인하는 것입니다. 그렇다면 우리는 끝났어. 그렇지 않은 경우 새 번호를 선택하고 다시 시작하십시오 (즉, 조정 부분). 합법적 인 노드 레이블의 작은 부분 만 사용되기 때문에 엄청나게 규제해야 할 것 같지만 공정성을 왜곡시키지 않고 시간을 늘리십시오.
function num_to_binary_list(n,digits) =
if digits == 0 return()
if n mod 2 == 0 return 0 :: num_to_digits(n/2,digits-1)
else return 1 :: num_to_digits((n-1)/2,digits-1)
function binary_list_to_node_label_list(l) =
if l.head() == 0 return l.tail()
else return binary_list_to_node_label_list(l.tail())
function check_node_label_list_against_tree(str,node) =
if node == null return false,null
if str.isEmpty()
if node.isLeaf() return true,node
else return false,null
if str.head() == 0 return check_node_label_list_against_tree(str.tail(),node.left)
else check_node_label_list_against_tree(str.tail,node.right)
function generate_random_node tree b =
found := false
while (not found)
x := random(0,2**(b+1)-2) // We're assuming that this random selects inclusively
node_label := binary_list_to_node_label(num_to_binary_list(x,b+1))
found,node := check_node_label_list_against_tree(node_label,tree)
return node
이의 타이밍 분석은 물론, 꽤 끔찍한입니다 :
는 다음 네 가지 기능이 과정의 의사 코드 버전입니다. 기본적으로 while 루프는 평균 (2^(B + 1) -1)/N 번 실행됩니다. 그래서, 최악의 경우, 그것은 끔찍한 O ((2^N)/N)입니다. 가장 좋은 경우, B는 log (N)의 차수가 될 것이므로 대략 O (1)가 될 것입니다.하지만 그럴 경우 나무가 균형을 이루지 않아야합니다. 그래도 공간을 추가하지 않으려면이 방법을 사용합니다.
저는 정보를 저장하지 않고이 마지막 방법보다 더 잘 할 수 있다고 생각하지 않습니다. 나무를 횡단하여 무작위로 결정을 내리는 것이 매력적이지만 구조에 대한 추가 정보를 저장하지 않으면 그 일을 할 수 없을 것입니다. 분기 결정을 내릴 때마다 왼쪽에는 하나의 노드가 있고 오른쪽에는 백만 개의 노드가 있거나 왼쪽에는 백만 개의 노드가 있고 오른쪽에는 하나의 노드가있을 수 있습니다. 그 둘 모두 가능하고 어떤 경우인지 모르기 때문에 양측간에 무작위로 의사 결정을 내릴 수있는 방법이 없습니다. 분명히 50-50은 효과가 없으며 다른 선택은 비슷한 문제가 될 것입니다.
따라서 공간을 추가하지 않으려면 두 번째 방법이 효과적 일 수 있지만 느려질 수 있습니다. 약간의 여유 공간을 추가하는 데 신경 쓰지 않는다면 첫 번째 방법이 효과적 일 것입니다. 앞에서 말했듯이, 만약 당신이 나무를 바꾸지 않고 많은 무작위 노드를 선택한다면, 총알을 물고 나무를 가로 지르며 모든 잎 노드를 자기 성장 어레이에 붙이십시오 또는 벡터를 선택하고 그 다음부터 선택하십시오.
이 질문은 명확하지 않습니다. 임의의 집합을 선택하려면 무작위 요소를 선택 하시겠습니까? 답변을 얻으려면 자세한 내용을 제공해야한다고 생각합니다. –
스벤, 자세한 내용을 추가했습니다 – Maksee
전체 트리 구조를 아는 것이 쉽습니다. 즉, 어떤 노드에 뿌리를 둔 각 하위 트리 (요소 수)의 크기를 알고 있다면 가중치를 사용하여 균일하게 샘플링 할 수 있습니다. 그러나 항목 수를 알 수 없다고 명시합니다. 아마도 그러한 칭량 된 샘플링을 수행하기위한 "충분한"다른 메트릭스를 가질 수 있습니까? – gusbro