[Sampling] Reservoir Sampling

1. Reservoir Sampling

• 정의
  
  • n개의 항목 목록에서 k 개의 샘플을 무작위로 선택하기 위한 무작위 알고리즘으로, 여기서 n은 매우 크거나 알 수 없는 숫자이다. 일반적으로 n은 목록이 주 메모리에 맞지 않을 정도로 크다. 예를 들어 Google 및 Facebook의 검색어 목록이다.

• 특징
  • 데이터 스트림에서 샘플링하는 알고리즘

 

2. Process

• 단순화하기 위해 숫자의 큰 배열 (또는 스트림)이 주어지며 1 < = k < = n 인 k 숫자를 무작위로 선택하는 효율적인 함수를 작성해야한다. 입력 배열을  stream[] 으로 하자.
• 간단한 해결책은 최대 크기 k의 배열 저장소 reservoir[]를 만드는 것이다. 스트림 [0..n-1]에서 항목을 하나씩 무작위로 선택한 뒤, 선택한 항목이 이전에 선택되지 않은 경우 reservoir[]에 넣는다. 항목이 이전에 선택되었는지 확인하려면 reservoir[]에서 항목을 검색해야 하는데, 이 알고리즘의 시간 복잡도는 O (k ^ 2)이다. k가 크면 비용이 많이 들 수 있고, 입력이 스트림 형식인 경우 효율적이지 않다.
• O (n) 시간으로 해결할 수 있다. 이 솔루션은 스트림 형태의 입력에도 적합하다.
  1) 배열 reservoir [0..k-1]를 만들고 stream[]의 처음 k 항목을 복사한다.
  2) 이제 (k + 1) 번째 항목부터 n번째 항목까지 모든 항목을 하나씩 고려하라.
      a) 0에서 i까지의 난수를 생성하자. 여기서 i는 stream[]에있는 현재 항목의 인덱스이다. 생성된 난수를 j라고 한다.
      b) j가 0에서 k-1 범위에 있으면 reservoir [j]를 stream[i]로 바꾼다.

 

# An efficient Python3 program
# to randomly select k items
# from a stream of items
import random
# A utility function
# to print an array
def printArray(stream,n):
    for i in range(n):
        print(stream[i],end=" ");
    print();
 
# A function to randomly select
# k items from stream[0..n-1].
def selectKItems(stream, n, k):
        i=0;
        # index for elements
        # in stream[]
         
        # reservoir[] is the output
        # array. Initialize it with
        # first k elements from stream[]
        reservoir = [0]*k;
        for i in range(k):
            reservoir[i] = stream[i];
         
        # Iterate from the (k+1)th
        # element to nth element
        while(i < n):
            # Pick a random index
            # from 0 to i.
            j = random.randrange(i+1);
             
            # If the randomly picked
            # index is smaller than k,
            # then replace the element
            # present at the index
            # with new element from stream
            if(j < k):
                reservoir[j] = stream[i];
            i+=1;
         
        print("Following are k randomly selected items");
        printArray(reservoir, k);
     
# Driver Code
 
if __name__ == "__main__":
    stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
    n = len(stream);
    k = 5;
    selectKItems(stream, n, k);

 

 

[참고 자료]

1. Coding Interview Questions-Reservoir Sampling | by Zaid Alissa Almaliki | Towards Data Science
2. Reservoir Sampling - GeeksforGeeks