STL random_sample이 감소 확률로 바꿉니다.

STL random_sample 함수는 주어진 간격에서 샘플링하기 위해 대체 전략을 사용합니다. 왜 우리는 감소 확률이 필요합니까, 나는 대체 확률을 감소시키지 않고 유사한 알고리즘을 보았습니다. 그 차이점은 무엇입니까? 이는 첫 번째 요소 (실제로, 제 n 요소) 1 확률 (이하 "을 기입"단계)로 선택되어야한다는 것을 분명STL random_sample이 감소 확률로 바꿉니다.

/*This is an excerpt from STL implementation*/ 
template <class InputIterator, class RandomAccessIterator, class Distance> 
RandomAccessIterator __random_sample(InputIterator first, InputIterator last, 
             RandomAccessIterator out, 
           const Distance n) 
{ 
    Distance m = 0; 
    Distance t = n; 
    for (; first != last && m < n; ++m, ++first) //the strategy is also used in mahout 
    out[m] = *first;//fill it 

    while (first != last) { 
     ++t; 
     Distance M = lrand48() % t; 
     if (M < n) 
      out[M] = *first;//replace it with a decreasing probability 
     ++first; 
    } 

    return out + m; 
}

출처

2013-08-29 zoujyjs

선행 밑줄이있는 전역 이름을 만들지 마십시오. 예약되어 있습니다. –

그리고 여러분의 함수가 표준 라이브러리의 함수와 다른 점은 무엇입니까? –

@JoachimPileborg 이것은 STL 구현의 발췌 부분이며, 버전은 sgi-2.9입니다. 물론 이것은 내부에서 사용되는 함수이며 사용자 인터페이스의 일부가 아닙니다. 내 질문은 왜 전략이 사용되는지, 기본적으로 나는 확률이 감소하고있는 것을 방황하고있다. – zoujyjs

:으로하는 코드이다. 마지막 샘플에 남아 있으려면이 첫 번째 요소가 m-n 가능한 대체물을 유지해야합니다. 즉, 샘플에있는 확률이 n/m으로 줄어 듭니다. 반면에, 마지막 요소는 오직 하나의 교체에 참여한다. 따라서 처음부터 n/m 확률로 샘플에 추가해야합니다.

간단히 말하자면,이 대체 전략을 사용하여 m 중에서 하나의 요소 만 선택해야한다고 가정하십시오 (갑자기 끝까지 반복 할 때까지 반복하십시오). 첫 번째 요소를 가져다가 1의 확률로 유지합니다 (아는 바로는 이것이 유일한 요소입니다). 그런 다음 두 번째 요소를 발견하면 동전을 던져 1/2의 확률로 지폐를 버리거나 버립니다. 이 시점에서 처음 두 요소는 각각 1/2의 확률을가집니다.

이제 세 번째 요소가 표시되며 확률은 1/3입니다. 처음 두 요소의 각각은 1/2이이 만남에 참여할 확률을 가지고 있었고 2/3은 살아 남았습니다 - 합계가 1/2 * 2/3 == 1/3이 될 가능성이 여전히 있습니다. 다시 말하지만, 처음 세 요소 각각은이 시점에서 1/3 확률로 선택됩니다.

t 요소가 검사 된 후, 첫 번째 t 요소의 각각은 1/t 확률을 가지며 판독기의 연습 문제로 남게된다는 것을 증명하는 유도 단계. 증거의 확장은 크기가 n > 1 인 표본까지입니다.

출처

2013-08-29 13:34:02

STL random_sample이 감소 확률로 바꿉니다.

답변

관련 문제