가중치 항목의 빠른 샘플링 및 업데이트 (적 - 검은 나무와 같은 데이터 구조)

Question

이 작업에 적합한 데이터 구조는 무엇입니까?

나는 N 개의 항목으로 구성되어 있습니다. N은 크다. 각 항목에는 양수 가중치가 있습니다.

나는 빨리, 다음을 수행하고 싶습니다 :

내부 루프 :

샘플 항목, 그것의 무게에 따라.

[공정 ...]

업데이트 K 상품의 중량, 여기서 K < < N.

I 중량 샘플을 말할 때, 이것은 균일 샘플링 다르다. 아이템의 우도는 그 무게에 비례합니다. 따라서 두 개의 항목이 있고 하나의 가중치가 .8이고 다른 하나의 가중치가 .2 인 경우 각각 80 %와 20 %의 가능성이 있습니다.

항목 수 N은 고정되어 있습니다. 가중치는 한정된 범위, 즉 [0, 1]입니다. 가중치가 항상 1로 합 해지는 것은 아닙니다.

순진한 접근법은 샘플링에 O (n) 시간 단계를 필요로합니다. O (log (n)) 알고리즘이 있습니까?

이 작업에 적합한 데이터 구조는 무엇입니까? 빨강 - 검정 나무는 각 항목을 동일한 무게로 취급하기 때문에 부적절하다고 생각합니다.

Answer 1

실제로, (수정 된) RB 트리를 사용할 수 있습니다. 또한, 균형 트리 (반드시 바이너리는 아님)의 수정이 가능합니다.

트릭은 각 노드에 추가 정보를 저장하는 것입니다. 귀하의 경우에는 노드에 뿌리를 둔 서브 트리의 전체 가중치가 될 수 있습니다.

트리를 업데이트 (삽입/삭제)하면 원하는 트리의 알고리즘을 따라야합니다. 구조를 변경하면 노드의 합계 (예 : 회전 및 B- 트리 스플릿 및 조인에 대한 O (1) 연산)를 다시 계산하면됩니다. 항목의 가중치를 변경하면 노드의 조상의 합계를 업데이트합니다.

샘플링 할 때 수정 된 버전의 검색을 실행합니다. 나무의 모든 무게의 합계 (즉, 뿌리의 합)를 얻고 이보다 더 낮은 양의 난수를 생성합니다. 그런 다음 검색 알고리즘을 실행합니다. 여기서 왼쪽 노드의 합계보다 작은 숫자 (검색 할 분위수) 인 경우 왼쪽 노드로 이동합니다. 오른쪽 노드로 가면 Quantile에서 왼쪽 합계를 뺍니다.

이 설명은 다소 혼란 스럽지만 도움이되기를 바랍니다.

Answer 2

나는 jpalecek의 대답을 좋아한다. 난 당신의 임의의 숫자를 얻을 수있는 가장 간단한 방법은 (1) 제복 (0,1) 배포판에서 유를 생성하는 것입니다. (2) 트리의 모든 가중치의 합으로 u를 곱합니다.

Answer 3

N은 고정되어 있으므로 v [i + 1] = v [i] + weight [i], v [1] = weight [0] 인 배열을 사용하여이를 해결할 수 있습니다. v [0] = 0이고 0과 가중치의 합계 사이에 균일하게 분포 된 난수의 하한에 대해 log (N) 인 이진 검색에 의해 샘플링합니다.

K 항목의 Naive 업데이트는 O (KN)이고, 더 사려 깊은 것은 O (N)입니다. 잘난척의 원 :

Answer 4

이에 의해 또 다른 인터뷰 질문을 망치고

는

좀 몬테카를로 시뮬레이션에 해결했던 문제이다. 아래의 링크에서 현재의`binary tree '를 볼 수 있습니다. 나는 그것을 공정하게 STL과 같이 만들려고 노력했다. 내 나무에는 고정 된 용량이 있습니다. 검정 - 나무 접근법을 사용하여 둥글게 할 수 있습니다. 그것은 본질적으로 jpacelek에 의해 설명 된 아이디어의 구현입니다.

이 방법은 나무에서 같은 수준에 있기 때문에 거의 같은 양의 합계를 계산하고 비교하기 때문에 정확하지 않은 부동 소수점 숫자를 처리하는 데 매우 강력합니다.

http://mopssuite.svn.sourceforge.net/viewvc/mopssuite/utils/trunk/include/binary_tree.hpp?view=markup