가중치 무작위 선택에서 대체와 비대체를 언제 사용해야 합니까?

가중 무작위 선택: 대체 vs. 비대체

가중 무작위 선택은 다양한 응용 분야에서 사용되는 기본 기술입니다. 여기에는 지정된 가중치에 따라 결정되는 확률 분포를 사용하여 주어진 목록에서 요소를 샘플링하는 작업이 포함됩니다. 대체 요소를 선택할 때 각 항목을 여러 번 선택할 수 있으므로 가중치가 더 높은 항목을 선택할 가능성이 높아집니다. 대조적으로, 치환 없는 선택은 일단 선택된 항목의 선택을 제한합니다.

가중 무작위 선택, 특히 치환을 사용하는 효율적인 알고리즘을 찾는 것은 어려울 수 있습니다. 수정된 저장소 알고리즘을 포함한 기존 방법은 작은 목록 크기에서 중요한 부분을 선택하는 데 적합하지 않은 것으로 입증되었습니다.

효율적인 접근 방식: 별칭 방법

이 시나리오에서 탁월한 한 가지 접근 방식 별칭 방법입니다. 이 기술은 각각 가중치 목록의 일부를 나타내는 구조화된 저장소 세트를 생성합니다. 비트 연산을 활용하면 빈을 효율적으로 인덱싱할 수 있어 이진 검색을 피할 수 있습니다. 각 bin에는 원래 목록의 두 요소가 포함되어 있어 분포를 효율적으로 표현할 수 있습니다.

예를 들어, 가중치가 동일하게 적용되는 5개의 선택 목록(a:1, b:1, c:1, d: 1, e:1). 별칭 방법은 각각 확률 질량이 0.125인 8개의 bin 세트를 생성합니다.

1. 정규화: 가중치의 합이 1.0이 되도록 조정합니다. 이 경우 (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2).
2. Partition: 파티션 확률(0.125)보다 낮은 가중치를 갖는 Bin을 할당합니다. 가장 낮은 무게로. 여기서 (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8).
3. 채우기: 파티션의 남은 공간을 가장 높은 파티션으로 채웁니다. 체중 변수. 예를 들어 (p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8)입니다.

런타임 선택:

런타임에 난수를 생성하고 비트 연산을 사용하여 확률 분포에 해당하는 빈을 효율적으로 결정합니다. Bin이 분할된 경우 난수의 소수 부분을 사용하여 Bin의 두 요소 중에서 선택합니다.

요약하면 별칭 방법은 대체를 통한 가중치 무작위 선택을 위한 효율적인 기술을 제공합니다. 빠른 빈 인덱싱을 위해 비트 연산을 활용하고 가중치를 관리 가능한 빈으로 신중하게 나누어 정확한 확률 분포를 달성합니다.

위 내용은 가중치 무작위 선택에서 대체와 비대체를 언제 사용해야 합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!