저수지 샘플링

Reservoir 샘플링은 무작위 알고리즘입니다. 이 알고리즘에서는 n개의 다른 항목이 있는 목록에서 k개의 항목이 선택됩니다.

배열을 k 크기의 저장소로 생성하여 해결할 수 있습니다. 그런 다음 기본 목록에서 무작위로 하나의 요소를 선택하고 해당 항목을 저수지 목록에 배치합니다. 한 항목을 한 번 선택하면 다음에는 선택되지 않습니다. 그러나 그의 접근 방식은 효과적이지 않습니다. 우리는 이 방법으로 복잡성을 증가시킬 수 있습니다.

저수지 목록에서 목록의 처음 k개 항목을 이제 목록의 (k+1)번째 숫자에서 하나씩 복사하여 현재 선택된 항목을 인덱스 i에 배치합니다. 0에서 i까지의 임의의 인덱스를 찾아 j에 저장합니다. j가 0에서 k의 범위에 있으면 저장소[j]를 list[i]로 교체합니다.

입력 및 출력

Input:
The list of integers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, The value of k = 6
Output:
K-Selected items in the given array: 8 2 7 9 12 6

알고리즘

chooseKItems(array, n, k)

입력: 배열, 배열의 요소 수, 선택할 요소 수.

출력: k개의 요소를 무작위로 선택합니다.

Begin
   define output array of size [k]
   copy k first items from array to output

   while i < n, do
      j := randomly choose one value from 0 to i
      if j < k, then
         output[j] := array[i]
      increase i by 1
   done
   display output array
End

예시

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void display(int array[], int n) {
   for (int i = 0; i < n; i++)
      cout << array[i] << " ";
}

void chooseKItems(int array[], int n, int k) {        //it will choose k items from the array
   int i;
   int output[k];
   for (i = 0; i < k; i++)
      output[i] = array[i];

   srand(time(NULL));        //use time function to get different seed value

   while(i < n) {
      int j = rand() % (i+1);         //random index from 0 to i

      if (j < k)          //copy ith element to jth element in the output array
         output[j] = array[i];
      i++;
   }

   cout << "K-Selected items in the given array: ";
   display(output, k);
}

int main() {
   int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
   int n = 12;
   int k = 6;
   chooseKItems(array, n, k);
}

출력

K-Selected items in the given array: 8 2 7 9 12 6