고정 비율 선택

Question

필자는 일련의 요소를 가지고 있으며 그 중 하나의 요소를 선택해야합니다. 각 요소는 백분율 기회와 관련되어 있습니다. 백분율로 100을 더합니다.

요소를 선택할 확률이 백분율 값과 같아야합니다. 따라서 요소에 25 %의 확률이있는 경우 25 %의 확률로 선택됩니다. 즉, 요소를 1 백만 번 선택하면 해당 요소는 250K 시간 근처에서 선택되어야합니다.

Answer 1

당신이 설명하는 것은 다항 프로세스입니다. 그들은 방법 랜덤 프로세스를 생성하는

http://en.wikipedia.org/wiki/Multinomial_distribution#Sampling_from_a_multinomial_distribution

은 다음과 같이이다 : (나는 의사 코드를 사용합니다하지만 실제 코드에서 그것을 쉽게 만들 수 있어야합니다.)

1. 정렬 (. 필요하지가 그냥 최적화)는 예를 들어, 값이 너무 = [0.45,0.3,0.15,0.1]

: 그 확률의 역순으로 '상자'

2. 그런 다음 인덱스가 < = i 인 모든 요소의 합계 인 '누적'분포를 만듭니다. 의사 : http://php.net/manual/en/function.rand.php

3. :

4. 은 PHP 용 0 내지 1 x를 균일 한 난수를 확인이 사례에서 cumulant =

   cumulant=[0,0,0,0] // initiate it 
   s=0 
   for j=0 to size()-1 { 
       s=s+values[i] ; 
       cumulant[i]=s 
   } 
   

   [1 0.45,0.70,0.85,] 그 결과 무작위 박스 인덱스 i는

   이고, 가장 큰 i는 cumulant [i]가 <x

의사 :이

for j=0 to size()-1 { 
    if !(cumulant[i]<){ 
    print "your index is ",i 
    break; 
    } 

입니다. 포인트 3로 돌아가 다른 임의의 인덱스 i를 얻으십시오.

위와 같이 정렬하면 최종 검색이 빨라집니다. 예를 들어,이 확률 벡터가있는 경우 : 0.001 0.001 0.001 0.001 0.996, 정렬 할 때 난수 x가 거의 항상 0.996보다 작으므로 거의 항상 색인 i = 0 만 봐야합니다. . 만약 당신이 같은 '상자'를 반복적으로 사용한다면 그 종류에 따라 돈을 지불 할 수 있습니다. 250k로 시도하면 많은 도움이됩니다. 상자 인덱스는 정렬 된 벡터에 대한 것입니다.

Answer 2

필자가 지금까지했던 것을 보여주기보다는 그것을 작성하는 것이 더 빠르다고 생각합니다.

아마 가장 좋은 해결책은 아니지만 그것이 그대로있는 것만 큼 당신이 가진 것 같습니다. 여기

당신은 이동 : 요한의 대답에 영감을

$elements = array(
    'This' => 25, 
    'is' => 15, 
    'a' => 15, 
    'crappy' => 20, 
    'list' => 25 
); 

asort($elements); 
$elements = array_reverse($elements); 

// Precalc cumulative value 
$cumulant = 0; 
foreach ($elements as $key => &$value) { 
    $cumulant += $value; 
    $value = $cumulant; 
} 

function pickAnElement($elements) { 
    $random = rand(1, 100); 
    foreach ($elements as $key => $value) { 
     if ($random <= $value) { 
      return $key; 
     } 
    } 
} 

$picks = array(); 

for ($i = 0; $i < 10000; $i++) { 
    $element = pickAnElement($elements); 
    if (!array_key_exists($element, $picks)) { 
     $picks[$element] = 0; 
    } 
    $picks[$element]++; 
} 

var_dump($picks); 

, 나는 정렬과 cumulant을 미리 계산하는 루프를 추가했다.