가중치 난수 V2 (동적 경우)

Question

이 질문은 아래 링크의 질문입니다.

Weighted random numbers

질문은 각 요소의 가중치는 동적 자주 변경된다는 추가 조건 가중 난수를 샘플링한다.

EDIT 다른 가중치로 선택할 N 개의 요소가 있다고 가정합니다.

정적 가중치의 경우 Walker의 별칭 방법은 별칭을 설정하는 데 O (N) 시간이 필요하지만 샘플링 비용은 O (1)이므로 내 목표를 달성하는 것이 가장 좋습니다.

이진 검색 방법

누적 어레이를 만들기 위해 또한 O (N)을 필요로 샘플링 선정 로그이다 (N) 내 경우 그러나

, 가중치는 자주 변경되기 때문에, 수정 가중치 시간 복잡도도 중대한.

그래서 데이터 구조를 수정하고 O (N) 미만으로 샘플링하는 시간 복잡성을 가진 기존 라이브러리 또는 알고리즘이 있는지 알고 싶습니다.

편집 제가 의견을 읽는 동안 추가 조건을 부과해야한다는 것을 알고 있습니다. 각 수정 단계는 소수의 숫자 (대부분 두 개) 만 수정되며이 수정은 총 무게 합 (정규화 조건)을 변경하지 않습니다.

해결 방법이 있다면 가중치가 실수 일 때도 사용할 수 있는지 알고 싶습니다.

Answer 1

나는 동일한 문제에 직면 해있다. 나는 그것을 해결하기위한 나의 현재의 계획을 설명 할 것이지만, 다른 제안들 및/또는 구현 지침들에 대해 감사 할 것이다.

현재 Cormen/Leiserson/Rivest의 "Introduction to Algorithms"섹션 14.1에 설명 된대로 동적 주문 통계에 대한 알고리즘을 적용하는 것이 현재 계획입니다. 키로 가중치를 사용하여 빨강 - 검정 나무와 같은 균형 이진 트리에 요소를 넣습니다. 각 노드가 하위 트리에 가중치의 합을 저장하도록 트리를 보강합니다. 그런 다음 루트는 전체 트리에 가중치의 합을 저장합니다 (예 : S). 하위 트리 합계는 동적 순서 통계의 하위 트리 크기와 동일한 방식으로 트리 작업 중에 업데이트 할 수 있습니다. 가중 샘플링을 수행하려면 [0..S]의 숫자를 일률적으로 샘플링하십시오 (예 : x). 트리에서 노드 N을 검색하여 순차적 탐색에서 인 N 앞에 오는 노드의 가중치의 합이 N의 가중치 인 >x - 동적 순서 통계의 OS- 선택 작업과 유사하게 검색하십시오.