Map-Reduce 구현의 특수 샘플 메소드

Question

4 * 10^8 (대략) 레코드가있는 테이블이 있고 그 중 4 * 10^6 샘플을 얻고 싶습니다.

그러나 샘플을 얻을 내 방법은 어떻게 든 특별 :

1. 나는 (모든 레코드가 선택 될 수있는 동일한 확률을 가지고) 무작위로 4 * 10^8 레코드에서 한 레코드를 선택합니다.
2. 반복 단계 1 4 * 10^6 번 (하나의 레코드가 여러 번 선택 되더라도 상관 없음). 1부터 n까지 임의의 정수이다 (n은 크기가
   1. 테이블 A(num int)를 생성하고, 테이블 A의 모든 레코드에 하나 개의 번호 :

   은 내가이 해결하는 방법을 생각한다 내 원본 테이블, 위에서 언급 한 대략 4 * 10^8).

3. 모든 맵에 리소스 파일로 테이블 A을로드하고 결정중인 레코드의 서수가 테이블 A에 있으면이 레코드를 출력하고 그렇지 않으면 폐기합니다.

원본 테이블에서 더 많은 레코드를 샘플링하려고하면 테이블 A이 매우 커져서 리소스 파일로로드 될 수 없기 때문에 내 방법이 좋지 않을 것이라고 생각합니다.

그럼, 어느 누구도 우아한 알고리즘을 제공 할 수 있습니까?

Answer 1

"우아함"이 무엇을 의미하는지 모르겠지만 아마도 저수지 샘플링과 비슷한 것에 관심이있을 것입니다. k를 샘플 크기로하고 k 요소 배열을 널 (NULL)로 초기화하십시오. 샘플링하는 요소가 하나씩 도착합니다. j 번째 (1에서부터 셀 수) 요소가 도착하면 배열을 반복하고 각 셀에 대해 확률 1/j로 현재 요소로 내용을 대체합니다.

Naively, 실행 시간은 꽤 나쁘다 - 교체 비용 O (k n)로 n에서 k 개의 요소를 샘플링하는 것. 그러나 배열의 쓰기 횟수는 예상되는 O (k log n)입니다. 스트림의 이후 요소가 쓰기 작업을 거의하지 않기 때문입니다. 다음은 exponential distribution을 기반으로하는 효율적인 방법입니다 (경고 : 가볍게 테스트 된 Python을 앞두고). 실행 시간은 O (n + k log n)입니다.

import math 
import random 


def sample_from(population, k): 
    for i, x in enumerate(population): 
     if i == 0: 
      sample = [x] * k 
     else: 
      t = float(k) * math.log(1.0 - 1.0/float(i + 1)) 
      while True: 
       t -= math.log(1.0 - random.random()) 
       if t >= 0.0: 
        break 
       sample[random.randrange(k)] = x 
    return sample