0 から上限 N までの K 個の非繰り返し整数のリストを効率的に生成するにはどうすればよいですか [重複]
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
この質問にはすでに答えがあります:
- O(1) に含まれる一意の (反復しない) 乱数? 21 件の回答
質問には必要なデータがすべて含まれています。シーケンスを生成する効率的なアルゴリズムは何ですか? K 指定された間隔内で繰り返さない整数 [0,N-1]. 。単純なアルゴリズム (乱数を生成し、それらをシーケンスに追加する前に、それらが既に存在するかどうかを確認するために検索する) は、次の場合に非常に高価です。 K 大きくて十分近くにあります N.
で提供されるアルゴリズム リンクされたリストからランダムな要素のセットを効率的に選択する 必要以上に複雑なようで、何らかの実装が必要です。関連するパラメーターをすべて知っていれば、1 回のパスでうまく機能しそうな別のアルゴリズムを見つけました。
解決
Pythonライブラリのランダムモジュールにより、簡単で効果的：
from random import sample
print sample(xrange(N), K)
sample関数は、指定されたシーケンスから選択されたK個の一意の要素のリストを返します。
xrangeは<！> quot; list emulator <！> quot;です。つまり、メモリ内に作成せずに連続した数字のリストのように動作するため、このようなタスクに対して超高速になります。
他のヒント
The Art of Computer Programmingでは、第2巻：半数値アルゴリズム、第3版 、Knuthは次の選択サンプリングアルゴリズムについて説明しています。
アルゴリズムS（選択サンプリング手法）。 Nのセットからn個のレコードをランダムに選択するには、0 <！> lt; n <！>＃8804; N。
S1。 [初期化。] t <！>＃8592を設定します。 0、m <！>＃8592; 0.（このアルゴリズムでは、mはこれまでに選択されたレコードの数を表し、tは処理した入力レコードの総数です。）
S2。 [Generate U.]ゼロから1の間で一様に分布する乱数Uを生成します。
S3。 [テスト] If（N <！>＃8211; t）U <！>＃8805; n <！>＃8211; m、ステップS5に進みます。
S4。 [選択]サンプルの次のレコードを選択し、mとtを1増やします。m<！> lt; n、ステップS2に進みます。そうでない場合、サンプルは完了し、アルゴリズムは終了します。
S5。 [スキップ]次のレコードをスキップし（サンプルに含めない）、tを1増やし、ステップS2に戻ります。
実装は説明よりも従う方が簡単かもしれません。リストからn個のランダムメンバーを選択するCommon Lispの実装を次に示します。
(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))
実際には、選択しているセットの割合に関係なく、選択しているセットのサイズではなく、選択した要素の数に比例したスペースでこれを行うことができます。これを行うには、ランダムな順列を生成し、それから次のように選択します。
TEA やXTEAなどのブロック暗号を選択します。 XORフォールディングを使用して、ブロックサイズを最小の2のべき乗に減らします。選択するセットよりも大きい。ランダムシードを暗号のキーとして使用します。順列で要素nを生成するには、暗号でnを暗号化します。出力番号がセットにない場合は、暗号化します。番号がセット内に収まるまで繰り返します。平均して、生成された数ごとに2つ未満の暗号化を行う必要があります。これには、シードが暗号で保護されている場合、順列全体も安全であるという追加の利点があります。
これについてもっと詳しく書いたこちら。
次のコード（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]-
Jは1と等しくなる可能性があるため、要素はそれ自体と交換できます
-
- <=>を<=>から減算して繰り返します。
最後に、<=>最後の要素を取得します。
これは、基本的にリストからランダムな要素を選択し、それを移動してから、残りのリストからランダムな要素を選択するなどです。
O（K）および O（N）時間で動作し、 O（N）ストレージが必要です。
シャッフル部分の名前は Fisher-Yates shuffle または Knuthのシャッフル。 The Art of Computer Programmingの第2巻で説明されています。
K番号をハッシュストアに保存することにより、簡単なアルゴリズムを高速化します。開始する前にKを知ることで、ハッシュマップへの挿入の非効率性がすべてなくなり、高速な検索のメリットが得られます。
私のソリューションはC ++指向ですが、非常に単純なので、他の言語に翻訳できると確信しています。
- 最初に、0からKまで、K個の要素を持つリンクリストを生成します
- リストが空でない限り、0からベクターのサイズまでの乱数を生成します
- その要素を取得して別のベクトルにプッシュし、元のリストから削除します
このソリューションには、2回のループ反復のみが含まれ、ハッシュテーブルのルックアップやその他の種類は含まれません。実際のコードでは：
// 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シャッフルアルゴリズムではn個のシャッフルのみを適用できるため、リスト全体をシャッフルする必要はありません。nは返される要素の数です。リストの生成にはリストのサイズに比例した時間がかかりますが、シャッフルアルゴリズムを再起動する前に部分的にシャッフルされたリストを事前にシャッフルする必要なく、将来のシャッフルニーズに既存のリストを再利用できます（サイズは同じままです）。
Knuth Shuffleの基本的なアルゴリズムは、整数のリストから始めることです。次に、最初の整数をリスト内の任意の数字と交換し、現在の（新しい）最初の整数を返します。次に、2番目の整数をリスト内の任意の番号（最初の整数を除く）と交換し、現在の（新しい）2番目の整数を返します。その後...など...
これはばかげて単純なアルゴリズムですが、スワップを実行するときにリストに現在のアイテムを含めるように注意してください。そうしないと、アルゴリズムが中断されます。
リザーバーサンプリングバージョンは非常にシンプルです：
my $N = 20;
my $k;
my @r;
while(<>) {
if(++$k <= $N) {
push @r, $_;
} elsif(rand(1) <= ($N/$k)) {
$r[rand(@r)] = $_;
}
}
print @r;
これは、STDINから$ N個のランダムに選択された行です。ファイルの行を使用していない場合は、<！> lt; <！> gt; / $ _を別のものに置き換えますが、これは非常に簡単なアルゴリズムです。
リストをソートする場合、たとえば、NからK個の要素を抽出したいが、それらの相対的な順序は気にしない場合、効率的なアルゴリズムが論文 シーケンシャルランダムサンプリングのための効率的なアルゴリズム （Jeffrey Scott Vitter、 ACM Transactions on Mathematical Software 、Vol.13、No。1、1987年3月、56-67ページ）。
編集：boostを使用してc ++でコードを追加します。入力したばかりで、多くのエラーが発生する可能性があります。乱数はブーストライブラリから取得され、バカな種を含んでいるので、これに対して深刻なことをしないでください。
/* 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の間のすべての整数は、ほぼ同じ確率で選択されました。
基本的には、任意のシーケンスに適用される Knuthのアルゴリズムです（実際、その答えにはこのLISPバージョンがあります）。アルゴリズムは時間的には O（N）であり、@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 コードです。コンパイルするには調整が必要な場合があります。
