Как вы эффективно генерируете список из K неповторяющихся целых чисел от 0 до верхней границы N [дубликат]
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
На этот вопрос уже есть ответ здесь:
В вопросе приведены все необходимые данные:каков эффективный алгоритм для генерации последовательности K неповторяющиеся целые числа в пределах заданного интервала [0,N-1].Тривиальный алгоритм (генерирующий случайные числа и, прежде чем добавлять их в последовательность, просматривающий их, чтобы увидеть, были ли они уже там) очень дорог, если K является большим и достаточно близким к N.
Алгоритм, приведенный в Эффективный выбор набора случайных элементов из связанного списка кажется более сложным, чем необходимо, и требует некоторой реализации.Я только что нашел другой алгоритм, который, кажется, отлично справляется с задачей, если вы знаете все соответствующие параметры, за один проход.
Решение
Тот Самый случайный модуль использование библиотеки Python делает это чрезвычайно простым и эффективным:
from random import sample
print sample(xrange(N), K)
sample функция возвращает список из K уникальных элементов, выбранных из заданной последовательности.
xrange является "эмулятором списка", т.е.он ведет себя как список последовательных чисел, не создавая его в памяти, что делает его сверхбыстрым для задач, подобных этой.
Другие советы
В Искусство компьютерного программирования, Том 2:Полузначные алгоритмы, Третье издание, Кнут описывает следующий алгоритм выборки выборки:
Алгоритм Ы (Метод выборочного отбора).Для случайного выбора n записей из набора N, где 0 < n ≤ N.
S1.[Инициализировать.] Установите t ← 0, m ← 0.(В ходе этого алгоритма m представляет собой количество записей, выбранных на данный момент, а t - общее количество входных записей, с которыми мы имели дело.)
S2.[Сгенерировать U.] Сгенерируйте случайное число U, равномерно распределенное между нулем и единицей.
S3.[Тест.] Если (N – t)U ≥ n - m, перейдите к шагу S5.
S4.[Выберите.] Выберите следующую запись для выборки и увеличьте m и t на 1.Если m < n, переходите к шагу S2;в противном случае выборка считается завершенной, и алгоритм завершается.
S5.[Пропустить.] Пропустите следующую запись (не включайте ее в образец), увеличьте значение t на 1 и вернитесь к шагу S2.
Следовать реализации может быть проще, чем описанию.Вот реализация Common Lisp, которая выбирает n случайных элементов из списка:
(defun sample-list (n list &optional (length (length list)) result)
(cond ((= length 0) result)
((< (* length (random 1.0)) n)
(sample-list (1- n) (cdr list) (1- length)
(cons (car list) result)))
(t (sample-list n (cdr list) (1- length) result))))
И вот реализация, которая не использует рекурсию, и которая работает со всеми видами последовательностей:
(defun sample (n sequence)
(let ((length (length sequence))
(result (subseq sequence 0 n)))
(loop
with m = 0
for i from 0 and u = (random 1.0)
do (when (< (* (- length i) u)
(- n m))
(setf (elt result m) (elt sequence i))
(incf m))
until (= m n))
result))
На самом деле это возможно сделать в пространстве, пропорциональном количеству выбранных элементов, а не размеру набора, из которого вы выбираете, независимо от того, какую долю от общего набора вы выбираете.Вы делаете это, генерируя случайную перестановку, а затем выбирая из нее следующим образом:
Выберите блочный шифр, например ЧАЙ или XTEA.Использование XOR складной чтобы уменьшить размер блока до наименьшей степени в два раза больше, чем выбранный вами набор.Используйте случайное начальное значение в качестве ключа к шифру.Чтобы сгенерировать элемент n в перестановке, зашифруйте n с помощью шифра.Если выходного номера нет в вашем наборе, зашифруйте его.Повторяйте до тех пор, пока число не окажется внутри набора.В среднем вам придется выполнять менее двух операций шифрования на каждый сгенерированный номер.Это имеет дополнительное преимущество в том, что если ваше начальное значение криптографически защищено, то и вся ваша перестановка тоже.
Я писал об этом гораздо более подробно здесь.
Следующий код (на C, неизвестного происхождения), по-видимому, решает проблему чрезвычайно хорошо:
/* generate N sorted, non-duplicate integers in [0, max[ */
int *generate(int n, int max) {
int i, m, a;
int *g = (int *)calloc(n, sizeof(int));
if ( ! g) return 0;
m = 0;
for (i=0; i<max; i++) {
a = random_in_between(0, max - i);
if (a < n - m) {
g[m] = i;
m ++;
}
}
return g;
}
Кто-нибудь знает, где я могу найти еще такие драгоценные камни, как этот?
Сгенерировать массив 0...N-1 заполненный a[i] = i.
Затем перетасуйте первый K Товары.
Перетасовка:
- Начать
J = N-1 - Выберите случайное число
0...J(сказать,R) - поменять местами
a[R]сa[J]- с тех пор как
Rможет быть равноJ, элемент может быть заменен самим собой
- с тех пор как
- вычтите
1ОтJи повторите.
Наконец, возьмите K последние элементы.
По сути, это выбирает случайный элемент из списка, перемещает его, затем выбирает случайный элемент из оставшегося списка и так далее.
Работает в O(K) и O (N) время, требующее O (N) Хранение.
Часть перетасовки называется Перетасовка Фишера-Йейтса или Перетасовка Кнута, описанный во 2 - м томе Искусство компьютерного программирования.
Ускорьте выполнение тривиального алгоритма, сохранив K чисел в хранилище хеширования.Знание K до того, как вы начнете, устраняет всю неэффективность вставки в хэш-карту, и вы по-прежнему получаете преимущество быстрого поиска.
Мое решение ориентировано на C ++, но я уверен, что его можно было бы перевести на другие языки, поскольку оно довольно простое.
- Сначала сгенерируйте связанный список из K элементов, начиная от 0 до K
- Затем, пока список не пуст, генерируйте случайное число в диапазоне от 0 до размера вектора
- Возьмите этот элемент, вставьте его в другой вектор и удалите из исходного списка
Это решение включает в себя только две итерации цикла и никаких поисков по хэш-таблице или чего-либо подобного.Итак, в реальном коде:
// Assume K is the highest number in the list
std::vector<int> sorted_list;
std::vector<int> random_list;
for(int i = 0; i < K; ++i) {
sorted_list.push_back(i);
}
// Loop to K - 1 elements, as this will cause problems when trying to erase
// the first element
while(!sorted_list.size() > 1) {
int rand_index = rand() % sorted_list.size();
random_list.push_back(sorted_list.at(rand_index));
sorted_list.erase(sorted_list.begin() + rand_index);
}
// Finally push back the last remaining element to the random list
// The if() statement here is just a sanity check, in case K == 0
if(!sorted_list.empty()) {
random_list.push_back(sorted_list.at(0));
}
Шаг 1:Сгенерируйте свой список целых чисел.
Шаг 2:Выполнять Кнут Перетасовывает.
Обратите внимание, что вам не нужно перетасовывать весь список, поскольку алгоритм Knuth Shuffle позволяет применять только n перетасовок, где n - количество возвращаемых элементов.Генерация списка по-прежнему займет время, пропорциональное размеру списка, но вы можете повторно использовать существующий список для любых будущих потребностей в перетасовке (при условии, что размер останется прежним) без необходимости предварительной перетасовки частично перетасованного списка перед перезапуском алгоритма перетасовки.
Основной алгоритм для Knuth Shuffle заключается в том, что вы начинаете со списка целых чисел.Затем вы меняете первое целое число местами с любым числом в списке и возвращаете текущее (новое) первое целое число.Затем вы меняете второе целое число местами с любым числом в списке (кроме первого) и возвращаете текущее (новое) второе целое число.Затем... и так далее...
Это абсурдно простой алгоритм, но будьте осторожны при включении текущего элемента в список при выполнении подкачки, иначе вы нарушите алгоритм.
Версия для отбора проб из резервуара довольно проста:
my $N = 20;
my $k;
my @r;
while(<>) {
if(++$k <= $N) {
push @r, $_;
} elsif(rand(1) <= ($N/$k)) {
$r[rand(@r)] = $_;
}
}
print @r;
Это $ N случайно выбранных строк из STDIN.Замените <>/$_ дополните чем-нибудь другим, если вы не используете строки из файла, но это довольно простой алгоритм.
Если список отсортирован, например, если вы хотите извлечь K элементов из N, но вас не волнует их относительный порядок, в статье предлагается эффективный алгоритм Эффективный алгоритм последовательной случайной выборки (Джеффри Скотт Виттер, Операции ACM с математическим программным обеспечением, Том 1.13, Нет.1, март 1987, стр. 56-67.).
отредактированный добавить код на c ++ с помощью boost.Я только что набрал его, и там может быть много ошибок.Случайные числа берутся из библиотеки boost с глупым начальным значением, так что не делайте с этим ничего серьезного.
/* Sampling according to [Vitter87].
*
* Bibliography
* [Vitter 87]
* Jeffrey Scott Vitter,
* An Efficient Algorithm for Sequential Random Sampling
* ACM Transactions on MAthematical Software, 13 (1), 58 (1987).
*/
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <boost/random/linear_congruential.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/uniform_real.hpp>
using namespace std;
// This is a typedef for a random number generator.
// Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand
typedef boost::minstd_rand base_generator_type;
// Define a random number generator and initialize it with a reproducible
// seed.
// (The seed is unsigned, otherwise the wrong overload may be selected
// when using mt19937 as the base_generator_type.)
base_generator_type generator(0xBB84u);
//TODO : change the seed above !
// Defines the suitable uniform ditribution.
boost::uniform_real<> uni_dist(0,1);
boost::variate_generator<base_generator_type&, boost::uniform_real<> > uni(generator, uni_dist);
void SequentialSamplesMethodA(int K, int N)
// Outputs K sorted random integers out of 0..N, taken according to
// [Vitter87], method A.
{
int top=N-K, S, curr=0, currsample=-1;
double Nreal=N, quot=1., V;
while (K>=2)
{
V=uni();
S=0;
quot=top/Nreal;
while (quot > V)
{
S++; top--; Nreal--;
quot *= top/Nreal;
}
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
Nreal--; K--;curr++;
}
// special case K=1 to avoid overflow
S=floor(round(Nreal)*uni());
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
}
void SequentialSamplesMethodD(int K, int N)
// Outputs K sorted random integers out of 0..N, taken according to
// [Vitter87], method D.
{
const int negalphainv=-13; //between -20 and -7 according to [Vitter87]
//optimized for an implementation in 1987 !!!
int curr=0, currsample=0;
int threshold=-negalphainv*K;
double Kreal=K, Kinv=1./Kreal, Nreal=N;
double Vprime=exp(log(uni())*Kinv);
int qu1=N+1-K; double qu1real=qu1;
double Kmin1inv, X, U, negSreal, y1, y2, top, bottom;
int S, limit;
while ((K>1)&&(threshold<N))
{
Kmin1inv=1./(Kreal-1.);
while(1)
{//Step D2: generate X and U
while(1)
{
X=Nreal*(1-Vprime);
S=floor(X);
if (S<qu1) {break;}
Vprime=exp(log(uni())*Kinv);
}
U=uni();
negSreal=-S;
//step D3: Accept ?
y1=exp(log(U*Nreal/qu1real)*Kmin1inv);
Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real));
if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true
//step D4 Accept ?
y2=0; top=Nreal-1.;
if (K-1 > S)
{bottom=Nreal-Kreal; limit=N-S;}
else {bottom=Nreal+negSreal-1.; limit=qu1;}
for(int t=N-1;t>=limit;t--)
{y2*=top/bottom;top--; bottom--;}
if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv))
{//Accept !
Vprime=exp(log(uni())*Kmin1inv);
break;
}
Vprime=exp(log(uni())*Kmin1inv);
}
// Step D5: Select the (S+1)th record
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
curr++;
N-=S+1; Nreal+=negSreal-1.;
K-=1; Kreal-=1; Kinv=Kmin1inv;
qu1-=S; qu1real+=negSreal;
threshold+=negalphainv;
}
if (K>1) {SequentialSamplesMethodA(K, N);}
else {
S=floor(N*Vprime);
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
}
}
int main(void)
{
int Ntest=10000000, Ktest=Ntest/100;
SequentialSamplesMethodD(Ktest,Ntest);
return 0;
}
$ time ./sampling|tail
выдает следующий вывод на моем ноутбуке
99990 : 9998882
99991 : 9998885
99992 : 9999021
99993 : 9999058
99994 : 9999339
99995 : 9999359
99996 : 9999411
99997 : 9999427
99998 : 9999584
99999 : 9999745
real 0m0.075s
user 0m0.060s
sys 0m0.000s
Этот Ruby-код демонстрирует Отбор проб из пласта, Алгоритм R способ.В каждом цикле я выбираю n=5 уникальные случайные целые числа из [0,N=10) диапазон:
t=0
m=0
N=10
n=5
s=0
distrib=Array.new(N,0)
for i in 1..500000 do
t=0
m=0
s=0
while m<n do
u=rand()
if (N-t)*u>=n-m then
t=t+1
else
distrib[s]+=1
m=m+1
t=t+1
end #if
s=s+1
end #while
if (i % 100000)==0 then puts i.to_s + ". cycle..." end
end #for
puts "--------------"
puts distrib
выходной сигнал:
100000. cycle...
200000. cycle...
300000. cycle...
400000. cycle...
500000. cycle...
--------------
250272
249924
249628
249894
250193
250202
249647
249606
250600
250034
все целые числа в диапазоне от 0 до 9 были выбраны с почти одинаковой вероятностью.
Это, по сути, Алгоритм Кнута применяется к произвольным последовательностям (действительно, у этого ответа есть ЛИСП-версия этого).Алгоритм таков O (N) со временем и может быть O(1) в памяти, если последовательность передается в нее потоком, как показано на Ответ Майкла Крамера от @MichaelCramer.
Вот способ сделать это в O (N) без дополнительного хранилища.Я почти уверен, что это не чисто случайное распределение, но оно, вероятно, достаточно близко для многих применений.
/* generate N sorted, non-duplicate integers in [0, max[ in O(N))*/
int *generate(int n, int max) {
float step,a,v=0;
int i;
int *g = (int *)calloc(n, sizeof(int));
if ( ! g) return 0;
for (i=0; i<n; i++) {
step = (max-v)/(float)(n-i);
v+ = floating_pt_random_in_between(0.0, step*2.0);
if ((int)v == g[i-1]){
v=(int)v+1; //avoid collisions
}
g[i]=v;
}
while (g[i]>max) {
g[i]=max; //fix up overflow
max=g[i--]-1;
}
return g;
}
Это Perl-код.Grep - это фильтр, и, как всегда, я не тестировал этот код.
@list = grep ($_ % I) == 0, (0..N);
- I = интервал
- N = Верхняя граница
Получайте только те числа, которые соответствуют вашему интервалу, с помощью оператора модуля.
@list = grep ($_ % 3) == 0, (0..30);
вернет 0, 3, 6, ...30
Это псевдо-Perl-код.Возможно, вам потребуется настроить его, чтобы заставить компилироваться.
