대체 유무에 따른 가중 무작위 선택

프로그래밍 문제에 대응하여 목록에서 가중치 무작위 선택을 위한 효율적인 알고리즘을 찾습니다. 교체 유무에 관계없이 모두 가능합니다.

대체를 통한 가중치 선택

교체를 통한 가중치 선택은 별칭 방법입니다. 이 기술은 각 가중치 요소에 대해 동일한 크기의 저장소 집합을 만듭니다. 비트 연산을 활용하면 이진 검색을 사용하지 않고도 이러한 빈을 효율적으로 인덱싱할 수 있습니다. 각 bin은 원래 가중치가 적용된 요소 사이의 경계를 나타내는 단일 백분율을 저장합니다.

가중치가 동일한 5개 요소(a, b, c, d, e)의 예를 생각해 보세요.

별칭 메서드 구현

1. 가중치 정규화: 각 가중치를 합계로 나누어 합계를 얻습니다. 1.0.
2. 요소 수(여기서는 8)보다 크거나 같은 2의 가장 작은 거듭제곱을 결정합니다.
3. 각 요소에 빈 파티션을 할당합니다.

4. 모든 가중치가 분산될 때까지 다음 단계를 반복합니다.

   • 남은 가중치가 가장 적은 요소를 빈 공간에 배치합니다. partition.
   • 파티션이 채워지지 않은 경우 가장 무거운 나머지 요소를 추가합니다.

예를 들어 여러 번 반복한 후에 다음과 같은 파티션이 생성됩니다.

• p1: {a, 1.0}
• p2: {a, b, 0.6}

런타임 선택

1. 0과 1 사이의 난수를 생성합니다.
2. 난수를 비트쉬프트하여 다음을 찾습니다. 파티션 인덱스.
3. 파티션이 분할된 경우 비트 이동된 숫자의 소수 부분을 사용하여 분할할 요소를 결정합니다. return.

교체 없는 가중치 선택

가중 저장소 방법과 같은 알고리즘은 대체 없이 비가중 선택에 대해 존재하지만 이 문제는 아직 해결되지 않은 상태로 남아 있습니다.