저수지 샘플링


난이도 중급
자주 묻는 질문 아마존 페이스북 서비스
배열

저수지 샘플링은 n이 매우 큰 n 개 항목 목록에서 k 개의 저수지 항목을 무작위로 선택하는 기술입니다.
예를 들어 Google, YouTube 등의 검색 목록입니다.

저수지 샘플링

저수지 샘플링을위한 순진한 접근 방식

저수지 건설 정렬 크기 k, 주어진 목록에서 무작위로 항목을 선택합니다. 선택한 항목이 저장소에 없으면 추가하고 다음 항목을 계속합니다.

  1. 크기가 k 인 저수지 배열을 만듭니다.
  2. curr을 0으로 초기화하고 curr는 채워질 저수지 어레이의 현재 위치를 나타냅니다. curr이 k 미만일 때 3 단계와 4 단계를 반복합니다.
  3. 0에서 n (포함되지 않음) 사이의 난수를 생성합니다. 생성 된 난수를 rand로 둡니다.
  4. stream [rand]의 요소가 이미 저수지 배열에있는 경우 3 단계를 반복합니다. 그렇지 않으면 저수지 [curr]를 stream [rand]로 설정하고 curr를 증가시킵니다.
  5. 저수지 배열의 요소를 인쇄합니다.

저수지 샘플링을위한 JAVA 코드

public class ReservoirSampling {
    private static void selectReservoir(int[] stream, int k) {
        int n = stream.length;
        int reservoir[] = new int[k];
        // Index where the current item has to be placed
        int curr = 0;

        while (curr < k) {
            // Randomly generate an index between 0 to n
            int i = (int) (Math.random() * n) % n;
            boolean found = false;
            // Check if it is already present
            for (int j = 0; j < curr; j++) {
                if (reservoir[j] == stream[i]) {
                    found = true;
                    break;
                }
            }
            // If not present add it to the reservoir list
            if (!found) {
                reservoir[curr] = stream[i];
                curr++;
            }
        }

        // Print the randomly selected items
        for (int i = 0; i < k; i++) {
            System.out.print(reservoir[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example
        int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int k = 5;
        selectReservoir(stream, k);
    }
}

Reservoir 샘플링을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

void selectReservoir(int stream[], int k, int n) {
    int reservoir[k];
    // Index where the current item has to be placed
    int curr = 0;
    
    srand(time(0));
    
    while (curr < k) {
        // Randomly generate an index between 0 to n
        int i = rand() % n;
        bool found = false;
        // Check if it is already present
        for (int j = 0; j < curr; j++) {
            if (reservoir[j] == stream[i]) {
                found = true;
                break;
            }
        }
        // If not present add it to the reservoir list
        if (!found) {
            reservoir[curr] = stream[i];
            curr++;
        }
    }
    
    // Print the randomly selected items
    for (int i = 0; i < k; i++) {
        cout<<reservoir[i]<<" ";
    }
    cout<<endl;
}

int main() {
    // Example
    int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int k = 5;
    int n = sizeof(stream) / sizeof(stream[0]);
    selectReservoir(stream, k, n);
    return 0;
}
2 12 9 3 5

코드가 저수지를 무작위로 선택하므로 출력이 다를 수 있습니다.

복잡성 분석

시간 복잡성 = 확인2
공간 복잡성 = O (1) 
여기서 k는 저장소 배열에있는 요소의 수입니다.

저수지 샘플링을위한 최적의 접근 방식

위의 문제는 주어진 스트림에 대해 효율적으로 해결할 수 있습니다.

  1. 크기가 k 인 저수지 배열을 만들고 스트림의 처음 k 개 항목을 배열에 복사합니다.
  2. 인덱스 (k + 1)에서 n으로 스트림을 이동합니다.
  3. 스트림의 i 번째 요소에 대해 j와 같이 임의의 숫자를 생성합니다. 숫자가 0과 (k – 1) 사이에 있으면 저수지 [j]를 스트림 [i]로 바꿉니다.
  4. 저수지 배열은 스트림에서 선택된 k 개의 난수를 포함하고 있습니다.

저수지 샘플링을위한 JAVA 코드

public class ReservoirSampling {
    private static void selectReservoir(int[] stream, int k) {
        int n = stream.length;
        int reservoir[] = new int[k];

        // Copy first k items to the reservoir array
        for (int i = 0; i < k; i++) {
            reservoir[i] = stream[i];
        }

        // Traverse the remaining stream
        for (int i = k; i < n; i++) {
            // Generate a random number between 0 to n
            int randomNumber = (int) (Math.random() * n) % n;
            // If this number lies between 0 to k, replace reservoir[randomNumber] with stream of i
            if (randomNumber >= 0 && randomNumber < k) {
                reservoir[randomNumber] = stream[i];
            }
        }

        // Print the reservoir array
        for (int i = 0; i < k; i++) {
            System.out.print(reservoir[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int k = 5;
        selectReservoir(stream, k);
    }
}

Reservoir 샘플링을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

void selectReservoir(int stream[], int k, int n) {
    int reservoir[k];
    
    // Copy first k items to the reservoir array
    for (int i = 0; i < k; i++) {
        reservoir[i] = stream[i];
    }
    
    srand(time(0));
    
    // Traverse the remaining stream
    for (int i = k; i < n; i++) {
        // Generate a random number between 0 to n
        int randomNumber = rand() % n;
        
        // If this number lies between 0 to k, replace reservoir[randomNumber] with stream of i
        if (randomNumber >= 0 && randomNumber < k) {
            reservoir[randomNumber] = stream[i];
        }
    }
    
    // Print the randomly selected items
    for (int i = 0; i < k; i++) {
        cout<<reservoir[i]<<" ";
    }
    cout<<endl;
}

int main() {
    // Example
    int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int k = 5;
    int n = sizeof(stream) / sizeof(stream[0]);
    selectReservoir(stream, k, n);
    return 0;
}
11 2 8 4 6

코드가 저수지를 무작위로 선택하므로 출력이 다를 수 있습니다.

복잡성 분석

시간 복잡성 = O (N) 
공간 복잡성 = O (1)
여기서 n은 스트림의 총 요소 수이고 k는 저수지 배열에 존재하는 요소의 수입니다.

참조