프로그래밍에서 가중 난수를 생성하는 방법: 거부 샘플링과 반복 검색?

프로그래밍에서 가중 난수 생성

가중 난수는 범위 내의 특정 값이 선택될 확률이 다른 다양한 시나리오에 적용됩니다. 이 기사에서는 이를 달성하기 위한 두 가지 효과적인 접근 방식을 살펴보겠습니다.

원래 질문자가 제안한 첫 번째 접근 방식은 거부 샘플링입니다. 이 방법은 범위의 요소로 채워진 조회 테이블을 생성합니다. 여기서 각 요소는 해당 가중치에 비례하는 횟수만큼 나타납니다. 이어서, 난수를 검색하기 위해 조회 테이블에서 무작위 인덱스가 선택됩니다. 여기서 절충점은 조회 테이블을 구축하기 위한 선형 시간 복잡도와 큰 가중치 사양에 대한 잠재적인 메모리 소비에 있습니다.

또는 반복 검색 방법은 가중치의 합을 반복적으로 계산합니다. 무게 사양을 순회하는 동안. 이 합을 0~1 사이에서 임의로 생성된 숫자와 비교합니다. 합이 난수를 초과하면 해당 값이 난수로 반환됩니다. 거부 샘플링과 달리 이 접근 방식은 초기 비용이 발생하지 않지만 가중치 사양의 항목 수에 선형적인 평균 시간 복잡도를 나타냅니다.

JavaScript에서 두 접근 방식을 모두 시연하려면:

// Rejection Sampling
function weightedRand(spec) {
  var i, j, table = [];
  for (i in spec) for (j = 0; j < spec[i] * 10; j++) table.push(i);
  return function() { return table[Math.floor(Math.random() * table.length)]; };
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});

// Iterative Search
function weightedRand2(spec) {
  var i, sum = 0, r = Math.random();
  for (i in spec) { sum += spec[i]; if (r <= sum) return i; }
}

접근 방식 선택은 특정 애플리케이션 요구 사항, 시간 복잡성, 메모리 사용량 및 결정적 동작의 균형에 따라 달라집니다. 거부 샘플링은 선행 테이블 구성 비용으로 일정한 시간 조회를 제공하는 반면, 반복 검색은 선형 시간 성능으로 더 간단한 구현을 제공합니다. 프로그래머는 이러한 기술을 활용하여 다양한 프로그래밍 요구 사항에 맞는 가중치 난수를 효과적으로 생성할 수 있습니다.

위 내용은 프로그래밍에서 가중 난수를 생성하는 방법: 거부 샘플링과 반복 검색?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!