بكفاءة اختيار مجموعة من العناصر العشوائية من قائمة مرتبطة

Question

أقول لقد ربط قائمة من أرقام طول N. N كبيرة جدا و لا أعرف مقدما القيمة الدقيقة N.

كيف يمكنني الأكثر كفاءة كتابة الوظيفة التي سيعود k تماما أرقام عشوائية من القائمة ؟

Answer 1

هناك لطيفة جدا و كفاءة خوارزمية هذا باستخدام طريقة تسمى خزان أخذ العينات.

اسمحوا لي أن أبدأ بإعطاء لك التاريخ:

كانوث تدعو هذه الخوارزمية R على الصفحة.144 من عام 1997 Seminumerical الخوارزميات (المجلد 2 من فن برمجة الكمبيوتر) ، ويقدم بعض التعليمات البرمجية على ذلك هناك.كانوث سمات الخوارزمية إلى Alan G.الملاح.على الرغم من بحث طويل, لم أكن قادرة على العثور على الملاح هو الوثيقة الأصلية ، إن وجدت ، والتي قد تكون السبب في أنك سوف غالبا ما نرى كانوث نقلا عن مصدر هذه الخوارزمية.

ماكلويد و Bellhouse, 1983 (1) تقدم مناقشة أكثر استفاضة من كانوث وكذلك نشرت لأول مرة دليل (على حد علمي) أن الخوارزمية تعمل.

Vitter 1985 (2) استعراض خوارزمية R ثم يعرض ثلاث خوارزميات التي توفر نفس الناتج ، ولكن مع تطور.بدلا من اتخاذ خيار لتضمين أو تخطي كل واردة عنصر له خوارزمية حدد عدد الوافدين العناصر التي ينبغي تخطيها.في الاختبارات (لا ينكر خارج التاريخ الآن) انخفض هذا وقت التنفيذ بشكل كبير خلال تجنب توليد رقم عشوائي و مقارنات على كل قادم العدد.

في شبة الكود الخوارزمية هي:

Let R be the result array of size s
Let I be an input queue

> Fill the reservoir array
for j in the range [1,s]:
  R[j]=I.pop()

elements_seen=s
while I is not empty:
  elements_seen+=1
  j=random(1,elements_seen)       > This is inclusive
  if j<=s:
    R[j]=I.pop()
  else:
    I.pop()

علما بأنني قد مكتوبة خصيصا رمز لتجنب تحديد حجم المدخلات.هذا هو واحد بارد خصائص هذه الخوارزمية:يمكنك تشغيله دون الحاجة إلى معرفة حجم المدخلات مسبقا و لا يزال يؤكد لك أن كل عنصر واجهت مساو له في احتمال تنتهي في R (وهذا هو ، لا يوجد أي تحيز).وعلاوة على ذلك ، R يحتوي المعرض عينة من عناصر الخوارزمية وقد نظرت في جميع الأوقات.هذا يعني أنه يمكنك استخدام هذا على الانترنت الخوارزمية.

لماذا هذا العمل ؟

ماكلويد و Bellhouse (1983) توفر دليل على استخدام الرياضيات من تركيبات.انها جميلة ولكن سيكون من الصعب بعض الشيء لإعادة ذلك هنا.لذلك, لقد ولدت بديل دليل وهو أسهل شرح.

نمضي في طريق الإثبات من خلال الاستقراء.

نقول أننا نريد أن تولد مجموعة من s العناصر التي شهدناها بالفعل n>s عناصر.

دعونا نفترض أن لدينا الحالية s العناصر بالفعل كل من تم اختياره مع احتمال s/n.

تعريف الخوارزمية ، نختار العنصر n+1 مع احتمال s/(n+1).

كل عنصر بالفعل جزء من مجموعة النتائج احتمال 1/s يتم استبداله.

احتمال أن عنصرا من n-رأيت مجموعة النتائج يتم استبدال في n+1-ينظر النتائج لذلك (1/s)*s/(n+1)=1/(n+1).على العكس من ذلك ، فإن احتمال أن عنصر لم يتم استبدال هو 1-1/(n+1)=n/(n+1).

وهكذا ، n+1-ينظر يحتوي على عنصر إما إذا كان جزء من n-رأيت مجموعة النتائج و ليس استبدال---هذا الاحتمال هو (s/n)*n/(n+1)=s/(n+1)---أو إذا كان العنصر المختار-مع احتمال s/(n+1).

تعريف الخوارزمية يخبرنا أن أول s عناصر يتم تلقائيا تضمين الأولى n=s أعضاء مجموعة النتائج.لذلك ، n-seen نتيجة مجموعة تضم كل عنصر مع s/n (=1) احتمال أتاح لنا قاعدة قضية تحريض.

المراجع

1. ماكلويد, A.ايان و ديفيد R.Bellhouse."مريحة خوارزمية الرسم على عينة عشوائية بسيطة." مجلة الجمعية الملكيه الاحصاءيه المجتمع.سلسلة C (الإحصاء التطبيقي) 32.2 (1983):182-184.(الرابط)

2. Vitter جيفري S."أخذ عينات عشوائية مع خزان." ACM المعاملات الرياضية على برنامج (تومز) 11.1 (1985):37-57.(الرابط)

Answer 2

وهذا ما يسمى خزان أخذ العينات المشكلة.الحل بسيط هو تعيين رقم عشوائي إلى كل عنصر من عناصر القائمة كما تراها ، ثم الحفاظ على أعلى (أو أسفل) k العناصر كما أمرت رقم عشوائي.

Answer 3

أود أن أقترح:العثور على أول k أرقام عشوائية.نوع لهم.ثم اجتياز كل قائمة مرتبطة و أرقام عشوائية مرة واحدة.

إذا كنت بطريقة أو بأخرى لا أعرف طول قائمة مرتبطة (كيف؟), ثم هل يمكن انتزاع أول k في مجموعة ، ثم عقدة r ، توليد رقم عشوائي في [0, r), و إذا كان هذا هو أقل من ك, محل rth عنصر من الصفيف.(غير مقتنع تماما بأنه لا تحيز...)

بخلاف ذلك:"إذا كنت لن تكون البداية من هنا." هل أنت متأكد من قائمة مرتبطة هو حق مشكلتك ؟ ليس هناك أفضل بنية البيانات ، مثل حسن البالغ من العمر مسطحة مجموعة قائمة.

Answer 4

إذا كنت لا تعرف طول القائمة ، ثم سيكون لديك لاجتياز أنه كاملة لضمان عشوائي يختار.طريقة استخدمتها في هذه الحالة هو وصف توم هوتن (54070).في حين عبور قائمة تبقي k عناصر النموذج الخاص بك اختيار عشوائي إلى تلك النقطة.(في البداية كنت مجرد إضافة أولى k عناصر واجهتك.) ثم مع احتمال k/i, ، يمكنك استبدال عنصر عشوائي من اختيارك مع iعشر عنصر من القائمة (أيعنصر أنت في تلك اللحظة).

فإنه من السهل أن تظهر أن هذا يعطي اختيار عشوائي.بعد رؤية m عناصر (m > k) لدينا أن كل من الأول m عناصر القائمة هي جزء منك اختيار عشوائي مع احتمال k/m.هذا في البداية يحمل تافهة.ثم لكل عنصر m+1, ضعه في التحديد الخاص بك (استبدال عنصر عشوائي) مع احتمال k/(m+1).أنت الآن بحاجة إلى أن جميع العناصر الأخرى أيضا احتمال k/(m+1) من اختياره.علينا أن احتمال هو k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (أياحتمال أن العنصر في قائمة مرات احتمال أنه لا يزال هناك).مع حساب التفاضل والتكامل يمكنك مباشر تظهر أن هذا يساوي k/(m+1).

Answer 5

حسنا, كنت بحاجة إلى معرفة ما ن في وقت التشغيل على الأقل, حتى لو كان هذا ينطوي على القيام إضافية تمر على قائمة الاعتماد عليها.أبسط خوارزمية للقيام بذلك هو فقط اختيار رقم عشوائي في ن و إزالة هذا البند المتكررة k مرات.أو إذا جاز عودة تكرار الأرقام لا إزالة هذا البند.

إلا إذا كان لديك كبيرة جدا ن ، و صارمة جدا متطلبات الأداء, هذه الخوارزمية يعمل مع O(N*k) التعقيد الذي ينبغي أن يكون مقبولا.

تحرير:فما باللك, توم هوتن طريقة أفضل.حدد أرقام عشوائية أولا ، ثم اجتياز قائمة مرة واحدة.نفس نظرية التعقيد, أعتقد, ولكن أفضل بكثير من المتوقع في وقت التشغيل.

Answer 6

لماذا لا يمكنك فقط أن تفعل شيئا مثل

List GetKRandomFromList(List input, int k)
  List ret = new List();
  for(i=0;i<k;i++)
    ret.Add(input[Math.Rand(0,input.Length)]);
  return ret;

أنا متأكد من أنك لا يعني شيء بسيط جدا يمكنك تحديد أكثر ؟