0과 상한 N 사이에서 K개의 반복되지 않는 정수 목록을 효율적으로 생성하는 방법
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이 질문에는 이미 답변이 있습니다.
질문은 필요한 모든 데이터를 제공합니다.시퀀스를 생성하는 효율적인 알고리즘은 무엇입니까? 케이 주어진 간격 내에서 반복되지 않는 정수 [0,N-1].간단한 알고리즘(난수를 생성하고 이를 시퀀스에 추가하기 전에 해당 숫자가 이미 있는지 확인하는 것)은 다음과 같은 경우 매우 비쌉니다. 케이 충분히 크고 가깝습니다 N.
에서 제공되는 알고리즘 연결된 목록에서 임의의 요소 집합을 효율적으로 선택 필요 이상으로 복잡해 보이고 일부 구현이 필요합니다.방금 모든 관련 매개변수를 알고 있는 한 단일 패스로 작업을 잘 수행하는 것처럼 보이는 또 다른 알고리즘을 찾았습니다.
해결책
그만큼 랜덤 모듈 Python Library에서 매우 쉽고 효과적입니다.
from random import sample
print sample(xrange(N), K)
sample 함수는 주어진 시퀀스에서 선택한 K 고유 요소 목록을 반환합니다.
xrange "목록 에뮬레이터"입니다. 즉, 메모리에서 생성하지 않고 연속 숫자 목록처럼 작동하므로 이와 같은 작업에 매우 빠릅니다.
다른 팁
~ 안에 컴퓨터 프로그래밍의 예술, 2 권 : Seminumerical Algorithms, Third Edition, Knuth는 다음과 같은 선택 샘플링 알고리즘을 설명합니다.
알고리즘 S (선택 샘플링 기술). 0 <n ≤ N. 여기서 n 세트에서 무작위로 n 레코드를 선택하려면.
S1. [초기화.] set t ← 0, m ← 0을 설정하십시오 (이 알고리즘 동안 m은 지금까지 선택한 레코드 수를 나타내고 t는 우리가 처리 한 총 입력 레코드의 총 수입니다.)
S2. [u. 생성] 0과 1 사이에 균일하게 분포 된 임의의 숫자 u를 생성합니다.
S3. [테스트] (n - t) u ≥ n - m이면 S5 단계로 이동하십시오.
S4. [선택.] 샘플의 다음 레코드를 선택하고 M과 T를 1 씩 증가시킵니다. M <N 인 경우 S2 단계로 이동하십시오. 그렇지 않으면 샘플이 완료되고 알고리즘이 종료됩니다.
S5. [건너 뛰기] 다음 레코드를 건너 뛰고 (샘플에 포함시키지 마십시오) T를 1 씩 증가시키고 S2 단계로 돌아갑니다.
구현은 설명보다 따르는 것이 더 쉬울 수 있습니다. 다음은 목록에서 n 랜덤 멤버를 선택하는 일반적인 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))
실제로 선택한 총 세트의 비율에 관계없이 선택한 세트의 크기보다는 선택한 요소 수에 비례하여 공간 으로이 작업을 수행 할 수 있습니다. 임의의 순열을 생성 한 다음 다음과 같이 선택하여 다음을 수행합니다.
다음과 같은 블록 암호를 선택하십시오 차 또는 xtea. 사용 xor 접이식 블록 크기를 선택하는 세트보다 큰 2 개의 가장 작은 전력으로 줄입니다. 임의의 시드를 암호의 열쇠로 사용하십시오. 순열에서 요소 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 마지막 요소.
이것은 본질적으로 목록에서 임의의 요소를 선택하고 이동 한 다음 나머지 목록에서 임의의 요소를 선택합니다.
작동합니다 확인) 그리고 켜짐) 시간이 필요합니다 켜짐) 저장.
셔플 링 부분이 호출됩니다 Fisher-Yates Shuffle 또는 Knuth의 셔플, 두 번째 볼륨에 설명되어 있습니다 컴퓨터 프로그래밍의 기술.
k 숫자를 해싱 스토어에 저장하여 사소한 알고리즘 속도를 높이십시오. 시작하기 전에 K를 아는 것은 해시 맵에 삽입하는 모든 비 효율성을 제거하면 여전히 빠른 조회의 이점을 얻습니다.
내 솔루션은 C ++ 지향적이지만 매우 간단하기 때문에 다른 언어로 번역 될 수 있다고 확신합니다.
- 먼저 0에서 K로 이동하는 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.
Knuth 셔플 알고리즘을 사용하면 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;
그것은 Stdin에서 무작위로 선택된 행입니다. 파일에서 행을 사용하지 않는 경우 <>/$ _ 물건을 다른 것으로 바꾸지 만 매우 간단한 알고리즘입니다.
예를 들어, 목록이 정렬 된 경우, n에서 k 요소를 추출하려는 경우, 상대 순서에 신경 쓰지 않으면 논문에서 효율적인 알고리즘이 제안됩니다. 순차 랜덤 샘플링을위한 효율적인 알고리즘 (Jeffrey Scott Vitter, 수학 소프트웨어에 대한 ACM 트랜잭션, vol. 1987 년 3 월 13 일, No. 1, 56-67 페이지).
편집 부스트를 사용하여 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
내 노트북에 다음 ouptut을 제공합니다
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 사이의 모든 정수가 거의 동일한 확률로 선택되었습니다.
그것은 본질적으로 크누스의 알고리즘 임의의 시퀀스에 적용됩니다(실제로 해당 답변에는 이에 대한 LISP 버전이 있습니다).알고리즘은 에) 시간이 지나면 될 수 있습니다 오(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 코드입니다. 컴파일하기 위해 조정해야 할 수도 있습니다.
