Специальный метод выборки в реализации Map-Reduce

Question

У меня есть таблица с 4 * 10^8 (примерно) записями, и я хочу получить ее 4 * 10^6 (точно).

Но мой путь, чтобы получить образец как-то особенным:

1. Я выбираю 1 запись из 4 * 10^8 записей в случайном порядке (каждая запись имеет одинаковую вероятность быть выбор).
2. повторите шаг 1 4 * 10^6 раз (независимо от того, будет ли одна запись выбрана несколько раз).

Я придумать способ, чтобы решить эту проблему:

1. Генерировать таблицу A(num int), а там только один номер в каждой записи таблицы A, которая является случайным целым числом от 1 до п (п является размером моей первоначальной таблицы, примерно 4 * 10^8, как упоминалось выше).
2. Загрузите таблицу A в качестве файла ресурсов на каждую карту, и если порядковый номер записи, находящейся на решении, находится в таблице A, выведите эту запись, в противном случае отбросьте ее.

Я думаю, что мой метод не очень хорош, потому что, если я хочу попробовать больше записей из исходной таблицы, таблица A станет очень большой и не может быть загружена в качестве файла ресурсов.

Итак, может ли кто-нибудь предложить элегантный алгоритм?

Answer 1

Я не уверен, что означает «изящный», но, возможно, вас интересует нечто похожее на выборку коллектора. Пусть k - размер образца и инициализирует массив k-элементов с нулями. Элементы, из которых мы отбираем выборку, поступают один за другим. Когда приходит элемент jth (counting from 1), мы итерации через массив и для каждой ячейки заменяем его содержимое на текущий элемент независимо с вероятностью 1/j.

Наивно, время работы довольно плохое - образец k элементов из n с затратами на замену O (k n). Число записей в массиве, однако, равно 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