كيف يمكنك أن كفاءة توليد قائمة من ك عدم تكرار الأعداد الصحيحة بين 0 و الحد الأعلى N [مكررة]
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هذا السؤال سبق الجواب هنا:
- فريد (غير مكرر) أرقام عشوائية في س(1)? 21 إجابات
السؤال يعطي جميع البيانات اللازمة:ما هو خوارزمية فعالة لتوليد سلسلة من K وعدم تكرار الأعداد الصحيحة خلال فترة معينة [0,N-1].تافهة خوارزمية (توليد أرقام عشوائية ، قبل إضافتها إلى تسلسل البحث عنها لمعرفة ما إذا كانت هناك بالفعل) هو مكلفة للغاية إذا K كبير بالقرب بما فيه الكفاية N.
الخوارزمية المقدمة في بكفاءة اختيار مجموعة من العناصر العشوائية من قائمة مرتبطة يبدو أكثر تعقيدا من اللازم ، يتطلب تنفيذ بعض.لقد وجدت فقط خوارزمية أخرى أن يبدو للقيام بهذه المهمة على ما يرام ، طالما أنك تعرف كل المعايير ذات الصلة في تمريرة واحدة.
المحلول
ال وحدة عشوائية من مكتبة Python يجعلها سهلة للغاية وفعالة:
from random import sample
print sample(xrange(N), K)
sample تقوم الوظيفة بإرجاع قائمة العناصر الفريدة K التي تم اختيارها من التسلسل المحدد.
xrange هو "محاكي قائمة" ، أي أنه يتصرف مثل قائمة الأرقام المتتالية دون إنشائها في الذاكرة ، مما يجعلها سريعة للغاية لمهام مثل هذه.
نصائح أخرى
في فن برمجة الكمبيوتر ، المجلد 2: خوارزميات ندوة ، الطبعة الثالثة, ، يصف Knuth خوارزمية أخذ عينات الاختيار التالية:
الخوارزمية S (تقنية أخذ العينات). لتحديد سجلات n بشكل عشوائي من مجموعة من n ، حيث 0 <n ≤ n.
S1. [initialize.] set t ← 0 ، m ← 0. (خلال هذه الخوارزمية ، يمثل M عدد السجلات المحددة حتى الآن ، و T هو إجمالي عدد سجلات الإدخال التي تعاملنا معها.)
S2. [توليد U.] قم بإنشاء رقم عشوائي U ، موزعة بشكل موحد بين الصفر والآخر.
S3. [اختبار.] إذا (n - t) u ≥ n - m ، انتقل إلى الخطوة S5.
4 س. [SELECT.] حدد السجل التالي للعينة ، وزيادة M و T بمقدار 1. إذا كان M <N ، انتقل إلى الخطوة S2 ؛ وإلا فإن العينة كاملة وتنتهي الخوارزمية.
S5. [تخطي.] تخطي السجل التالي (لا تقم بتضمينه في العينة) ، وزيادة T بمقدار 1 ، والعودة إلى الخطوة S2.
قد يكون التنفيذ أسهل في المتابعة من الوصف. فيما يلي تطبيق 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 للطي للحد من حجم الكتلة إلى أصغر قوة أكبر اثنين من مجموعة كنت اختيار من.استخدام البذور عشوائية مفتاح التشفير.لتوليد عنصر 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 العناصر الأخيرة.
هذا يختار بشكل أساسي عنصرًا عشوائيًا من القائمة ، ويقوم بنقله إلى الخارج ، ثم يختار عنصرًا عشوائيًا من القائمة المتبقية ، وما إلى ذلك.
يعمل في نعم) و على) الوقت ، يتطلب على) تخزين.
يسمى الجزء الخلط فيشر ييتس خلط أو خلط ورق اللعب Knuth, ، الموصوفة في المجلد الثاني من فن برمجة الكمبيوتر.
قم بتسريع الخوارزمية التافهة عن طريق تخزين أرقام 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.
لاحظ أنك لست بحاجة إلى خلط القائمة بأكملها ، نظرًا لأن خوارزمية Knuth Shuffle تتيح لك تطبيق N -Haffles فقط ، حيث 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 على البرامج الرياضية, ، المجلد. 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
يعطي 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
يعرض رمز الياقوت هذا أخذ عينات الخزان ، خوارزمية ص طريقة. في كل دورة ، اخترت 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 من هذا). الخوارزمية هي على) في الوقت المناسب ويمكن أن يكون س (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;
}
هذا هو رمز بيرل. GREP هو مرشح ، وكما هو الحال دائمًا لم أختبر هذا الرمز.
@list = grep ($_ % I) == 0, (0..N);
- أنا = الفاصل الزمني
- ن = الحد الأعلى
احصل فقط على الأرقام التي تتطابق مع الفاصل الزمني عبر مشغل المعامل.
@list = grep ($_ % 3) == 0, (0..30);
سيعود 0 ، 3 ، 6 ، ... 30
هذا هو رمز Pseudo Perl. قد تحتاج إلى تعديلها لجعلها تجمع.
