대체를 통한 가중 무작위 선택에 적합한 접근 방식은 무엇입니까?

가중 무작위 선택: 대체 제한 극복

최근 많은 개발자는 목록에서 요소를 가중치 무작위 선택하는 문제에 직면했습니다. 교체 유무. 비가중 선택과 비복원 가중치 선택에 대한 효과적인 알고리즘이 존재하지만 대체가 있는 가중치 선택에 적합한 솔루션을 찾는 것은 어려운 것으로 입증되었습니다.

효율성과 단순성을 달성하는 혁신적인 접근 방식 중 하나는 별칭 방법입니다. 가중치 목록에 대해 동일한 크기의 저장소를 생성하여 작동합니다. 이러한 저장소는 비트 작업을 사용하여 효율적으로 인덱싱되므로 시간이 많이 소요되는 이진 검색을 피할 수 있습니다.

별칭 조회 테이블을 구성하려면:

1. 가중치 합계를 1.0으로 정규화합니다(예: (1 , 1, 1, 1, 1)에서 (0.2, 0.2, 0.2, 0.2, 0.2)).
2. 변수 개수보다 크거나 같은 2의 가장 작은 거듭제곱을 결정하고 해당 개수의 파티션을 만듭니다. . 5가지 선택 항목의 예에서는 8개의 파티션을 생성합니다.
3. 빈 파티션에 가장 작은 남은 가중치를 할당합니다(예: 파티션 1의 가중치는 0.075입니다).
4. 파티션이 가득 차지 않은 경우 , 가장 큰 가중치도 할당합니다(예: 파티션 2의 가중치는 이제 0.075와 0.15입니다).

모든 원래 가중치가 할당될 때까지 3단계와 4단계를 반복합니다.

런타임:

1. [0, 1] 범위(예: 0.001100000)의 난수를 생성합니다.
2. 난수를 log2(num_partitions)만큼 이동하여 관련 파티션( 예를 들어 001.1은 파티션 2)에 매핑됩니다.
3. 파티션이 분할된 경우 이동된 난수의 소수 부분을 사용하여 분할을 결정합니다.

이 방법은 가중치가 부여된 무작위를 효과적으로 처리합니다. 교체를 통한 선택은 특히 목록의 많은 부분을 선택할 때 저장소 기반 접근 방식에 비해 상당한 성능 향상을 제공합니다.

위 내용은 대체를 통한 가중 무작위 선택에 적합한 접근 방식은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!