이것은 선택된 텍스트 행의 확률이 1/X 인 X 행의 텍스트에서 임의의 행을 선택하는 원래 질문의 확장입니다. 트릭은 범위가 [0,1] 인 임의 변수 Y를 쿼리하고 1/J보다 작은 값을 반환하는 경우 J 번째 라인을 선택하는 것입니다.텍스트 파일에서 K 개의 무작위 라인을 선택하십시오.
이제이 새로운 버전의 문제에서 우리는 K가 X보다 작은 K 개의 임의의 라인을 선택해야합니다. 각 라인의 확률은 K/X 여야한다고 생각합니다.
원래 솔루션을 K 회선으로 확장하는 방법에 대해 고민하고 있습니다. 가능한가? 어떤 설명이라도 좋을 것입니다.
이것은 원래 알고리즘의 일반화를 사용하여 해결할 수 있습니다. 직관은 다음과 같습니다. 첫 번째 k 줄에 처음 시드되는 파일에서 k 개의 후보 줄 목록을 유지합니다. 그런 다음 그 시점부터 파일의 n 번째 줄을 볼 때 :
이것은 확률 k/n (여기서 n은 파일의 총 줄 수)으로 각 요소를 올바르게 샘플링한다는 증거는 다음과 같습니다. n ≥ k라고 가정합니다. 우리는 각 요소가 z 요소를 본 후에 그 요소 각각이 선택 될 확률 k/z를 가짐을 보여 주어 확률 k/n이 선택된다는 것을 유도에 의해 증명합니다. 특히 이것은 n 개의 원소를 본 후에 각각이 필요에 따라 확률 k/n을 갖는다는 것을 의미합니다.
우리의 귀납적 인 기초로서, 정확하게 k 개의 원소를 보면, 각각이 선택됩니다. 따라서, 선택 될 확률은 필요에 따라 k/k이다.
유도 단계에 대해, 일부 z ≥ k에 대해, 각각의 제 1 z 요소가 확률 k/z로 선택되고 (z + 1) 번째 요소를 고려한다고 가정합니다. [1, z + 1]의 범위에서 임의의 자연수를 선택합니다. 확률 k/(z + 1)로, 우리는이 요소를 선택하기로 결정한 다음, 일부 오래된 요소를 제거합니다. 이것은 새로운 요소가 확률 k/(z + 1)로 선택된다는 것을 의미합니다. 각각의 z 원래 요소에 대해이 시점에서 선택 될 확률은 첫 번째 z 요소가 검사 된 후 우리가 선택한 가능성 (우리의 귀납적 가설에 의한 확률 k/z)과 우리가 확률 1/(z + 1)로 바꿔 놓기 때문에 z/(z + 1)을 유지하라. 따라서 그것이 선택되는 새로운 확률은 (k/z) (z/(z + 1)) = k/(z + 1)이다. 따라서 모든 첫 번째 z + 1 요소는 확률 k/(z + 1)로 선택되어 유도를 완료합니다.
또한이 알고리즘은 O (n) 시간에 실행되며 O (k) 공간 만 사용합니다. 즉, 런타임이 k 값과 독립적입니다. 이것을 보시려면, 각 반복은 O (1)을하고, 총 O (n) 개가 있다는 것을 유념하십시오.
궁금한 점이 있으면이 알고리즘을 C++ STL 스타일 알고리즘 available here on my personal site으로 구현했습니다.
희망이 도움이됩니다.
뛰어난 설명! 고맙습니다. –
이 줄은 "size_t index = rng() % (count + 1);"을 업데이트해야 할 수도 있습니다. 그 말은 비록 무작위 값을 양자화하는 더 좋은 방법이 있다고 믿지만 말은 잘못하지 않았습니다. –
먼저 첫 번째 알고리즘을 사용하여 X 줄에서 첫 번째 요소를 임의로 선택합니다. 나머지 X-1 라인 중 두 번째 라인을 선택하십시오. 이 프로세스를 K 번 실행합니다.
주어진 K 줄 집합의 확률은 (X choose K)입니다. 이 알고리즘이 원하는 균일 분포를 제공하는지 확인하기 위해 여러분에게 맡길 것입니다.
원래 솔루션 'k'번을 적용하지 않으시겠습니까? –