Как сгенерировать список восходящих случайных целых чисел

Question

У меня есть внешняя коллекция, содержащая n элементов, которые я хочу выбрать из них (k) из них случайным образом, выведя индексы этих элементов в какой-то сериализованный файл данных. Я хочу, чтобы индексы выводились в строгом порядке возрастания, а для дубликатов не было. Как n, так и k могут быть довольно большими, и обычно нецелесообразно просто хранить целые массивы в памяти такого размера.

Первый алгоритм, с которым я столкнулся, состоял в том, чтобы выбрать случайное число r [0] от 1 до nk ... и затем выбрать последовательные случайные числа r [i] из r [i-1] +1 в n -k + i, только нужно хранить две записи для «r» в любой момент времени. Однако довольно простой анализ показывает, что вероятность выбора небольших чисел не согласуется с тем, что могло бы быть, если бы весь набор был равномерно распределен. Например, если n был миллиардом и k составлял полмиллиарда, вероятность выбора первой записи с подходом, который я только что описал, очень крошечная (1 в пол-миллиарда), где на самом деле, поскольку половина записей выбранный, первый должен быть выбран в 50% случаев. Даже если я использую внешнюю сортировку для сортировки k случайных чисел, мне придется отбросить любые дубликаты и повторить попытку. Когда k приближается к n, количество попыток продолжит расти, без гарантии прекращения.

Я хотел бы найти алгоритм O (k) или O (k log k) для этого, если это вообще возможно. Язык реализации, который я буду использовать, - это C++ 11, но описания в псевдокоде могут по-прежнему быть полезными.

Answer 1

Вы можете решить эту проблему рекурсивно в O (к лог-к), если вы разделите в середине своего диапазона, и случайным образом выборку из hypergeometric probability distribution выбрать, сколько значения лежат выше и ниже средней точки (т.е. значения к каждой подпоследовательности), то для каждой рекурсии:

int sample_hypergeometric(int n, int K, int N) // samples hypergeometric distribution and 
// returns number of "successes" where there are n draws without replacement from 
// a population of N with K possible successes. 
// Something similar to scipy.stats.hypergeom.rvs in Python. 
// In this case, "success" means the selected value lying below the midpoint. 
{ 
    std::default_random_engine generator; 
    std::uniform_real_distribution<double> distribution(0.0,1.0); 

    int successes = 0; 
    for(int trial = 0; trial < n; trial++) 
    { 
     if((int)(distribution(generator) * N) < K) 
     { 
      successes++; 
      K--; 
     } 
     N--; 
    } 
    return successes; 
} 

select_k_from_n(int start, int k, int n) 
{ 
    if(k == 0) 
     return; 
    if(k == 1) 
    { 
     output start + random(1 to n); 
     return; 
    } 

    // find the number of results below the mid-point: 
    int k1 = sample_hypergeometric(k, n >> 1, n); 
    select_k_from_n(start, k1, n >> 1); 
    select_k_from_n(start + (n >> 1), k - k1, n - (n >> 1)); 
} 

Отбора проб из binomial distribution также может быть использованы для аппроксимации гипергеометрического распределения с р = (п >> 1)/N, отклоняющие образцами, где k1> (n >> 1).

Answer 2

Как упоминалось в моем комментарии, используйте std::set<int> для хранения случайных целых чисел, так что полученный контейнер по сути сортируется и не содержит дубликатов. Пример фрагмента кода:

#include <random> 
#include <set> 

int main(void) { 
    std::set<int> random_set; 
    std::random_device rd; 
    std::mt19937 mt_eng(rd()); 
    // min and max of random set range 
    const int m = 0; // min 
    const int n = 100; // max 
    std::uniform_int_distribution<> dist(m,n); 

    // number to generate 
    const int k = 50; 
    for (int i = 0; i < k; ++i) { 
     // only non-previously occurring values will be inserted 
     if (!random_set.insert(dist(mt_eng)).second) 
      --i; 
    } 
} 

Answer 3

Не могли бы вы отрегулировать каждый восходящий индексный выбор таким образом, чтобы компенсировать искажение вероятности, которое вы описываете?

IANAS, но я предполагаю, что если вы выберете случайное число r между 0 и 1 (вы можете масштабировать до полного оставшегося диапазона индекса после настройки), вы можете настроить его, вычислив r^(х) (сохраняя диапазон в 0..1, но увеличивая вероятность меньших чисел), причем х выбирается путем решения уравнения для вероятности первой записи?

Answer 4

Предполагая, что вы не можете хранить k случайных чисел в памяти, вам придется генерировать числа в строгом произвольном порядке. Один из способов сделать это - создать число от 0 до n/k. Позвоните по этому номеру x. Следующий номер, который вы должны сгенерировать, находится между x+1 и (n-x)/(k-1). Продолжайте таким образом, пока вы не наберете k чисел.

В принципе, вы делите оставшийся диапазон на количество оставшихся значений для генерации, а затем генерируете число в первом разделе этого диапазона.

Пример. Вы хотите сгенерировать 3 числа от 0 до 99 включительно. Поэтому вы сначала генерируете число от 0 до 33. Скажите, что вы выбрали 10.

Итак, теперь вам нужно число от 11 до 99. Оставшийся диапазон состоит из 89 значений, и у вас есть два значения для выбора. Итак, 89/2 = 44. Вам нужно число от 11 до 54. Скажите, что вы выбрали 36.

Ваш оставший диапазон составляет от 37 до 99, и у вас есть один номер налево. Поэтому выберите номер в случайном порядке между 37 и 99.

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

Этот псевдокод показывает основную идею.

pick_k_from_n(n, k) 
{ 
    num_left = k 
    last_k = 0; 
    while num_left > 0 
    { 
     // divide the remaining range into num_left partitions 
     range_size = (n - last_k)/num_left 
     // pick a number in the first partition 
     r = random(range_size) + last_k + 1 
     output(r) 
     last_k = r 
     num_left = num_left - 1 
    } 
} 

Обратите внимание, что это занимает время O (k) и требует O (1) дополнительного пространства.

Answer 5

Вы можете сделать это в O (k) времени с помощью алгоритма Флойда (не Floyd-Warshall, это кратчайший путь). Единственная структура данных, которая вам нужна, это 1-битная таблица, которая сообщит вам, был ли уже выбран номер. Поиск хеш-таблицы может быть O (1), поэтому это не будет бременем и может храниться в памяти даже для очень больших n (если n действительно огромно, вам придется использовать фильтр b-tree или bloom или что-то).

Для выбора K элементов из числа п:

for j = n-k+1 to n: 
    select random x from 1 to j 
    if x is already in hash: 
    insert j into hash 
    else 
    insert x into hash 

Вот и все. В конце ваша хеш-таблица будет содержать равномерно выбранный образец из k элементов из числа n. Прочитайте их по порядку (вам может понадобиться выбрать хеш-таблицу, которая позволяет это).

Answer 6

Если на практике к имеет тот же порядок величины, что и п, может быть очень простой О (п) алгоритм будет достаточно:

assert(k <= n); 
std::uniform_real_distribution rnd; 
for (int i = 0; i < n; i++) { 
    if (rnd(engine) * (n - i) < k) { 
     std::cout << i << std::endl; 
     k--; 
    } 
} 

Он производит все восходящие последовательности с равной вероятностью.