أخذ العينات بالخزان: احتفظ بسجلين من تدفق مجهول الطول

تخيّل أن برنامجك يستقبل رسائل، وتريد الاحتفاظ برسالتين لمراجعتهما عند نهاية التشغيل. في تجربتنا ستصل الرسائل A, B, C, D, E، لكن البرنامج لا يحصل مسبقًا على الرقم خمسة. إذا احتفظت بأول رسالتين دائمًا فستقرأ A وB كل مرة. سنبني بدل ذلك إجراءً يسمح بتغير محتوى الخانتين، ثم نفحص نتيجته بحصر الاحتمالات كاملة.

قاعدة الخزان، ثم تطبيقها خطوة خطوة

املأ أول k خانات. عند السجل رقم t اسحب عددًا صحيحًا متساوي الاحتمال من صفر إلى t−1. إذا كان أصغر من k، استبدل السجل الموجود في تلك الخانة؛ وإلا تجاوز الوافد. هذه صيغة بترقيم صفري لخوارزمية R. مرجع القاعدة.

اخترنا k=2. عند وصول C تكون الخيارات 0,1,2؛ اثنان منها يؤديان إلى إدخالها. وعند D يصبح المجال 0,1,2,3، لكن الاستبدال يظل مقتصرًا على الخانتين صفر وواحد. الجدول يتابع اختيارات قررناها مسبقًا لفهم التنفيذ:

لاحظ أن تجاهل D لم يُنقص العداد: الرسالة التالية خامسة، حتى إن لم تحفظ الرابعة. لو عددنا السجلات المحفوظة فقط، لبقي مجال السحب صغيرًا، ولغيرنا التجربة كلها. والأرقام في هذا الجدول ليست مخرجات بذرة عشوائية؛ إنها مسار محدد سنضمن وجوده ضمن الفحص الشامل.

كود يقبل مولّدًا لا قائمة كاملة

الدالة randrange(t) تختار من range(t)، أي إن الحد الأعلى مستبعد. نمررها هنا بوصفها دالة draw؛ ويمكن استبدالها بدالة اختبار تعيد اختيارات محددة. توثيق بايثون.

def reservoir(items, k, draw):
    if type(k) is not int or k < 0:
        raise ValueError("k must be a nonnegative integer")
    if k == 0:
        return []
    bag = []
    for t, item in enumerate(items, 1):
        if t <= k:
            bag.append(item)
        else:
            j = draw(t)
            if type(j) is not int or not 0 <= j < t:
                raise ValueError("draw returned an invalid index")
            if j < k:
                bag[j] = item
    return bag

عرّفنا سلوك الأطراف صراحة: k=0 يعيد قائمة فارغة دون استهلاك المدخل؛ والتدفق الأقصر من k يعيد جميع سجلاته. نرفض حجمًا سالبًا أو غير صحيح، ونرفض نتيجة سحب خارج المجال. إذا أردت اشتراط عينة مكتملة، فأضف بعد الاستدعاء فحصًا أن طول النتيجة يساوي الحجم المطلوب.

from random import Random
result = reservoir(iter("ABCDE"), 2, Random(17).randrange)
print(result)  # ['A', 'B']

هذا الاستدعاء أعاد A وB باستخدام Python 3.12.14 في بيئة المقال. تختلف نتيجته عن الجدول لأن اختيارات الجدول كانت محددة يدويًا. البذرة مفيدة لتكرار التشغيل، لكن معظم خوارزميات الوحدة قد تتغير بين إصدارات بايثون؛ سجّل الإصدار إذا احتجت إلى إعادة إنتاج تجربة.

اختبار أقوى من تشغيل البرنامج ألف مرة

لدينا بعد ملء الخانتين ثلاث لحظات سحب فقط. في الأولى ثلاثة خيارات، وفي الثانية أربعة، وفي الثالثة خمسة؛ إذن عدد المسارات 3×4×5=60. تحت افتراض أن كل سحب منتظم ومستقل، احتمال كل مسار 1/60. مررنا جميع هذه المسارات إلى الدالة نفسها، ورتبنا كل زوج نهائي قبل عده حتى لا نخلط بين ترتيب الخانات وهوية الزوج.

يظهر كل حرف في أربعة أزواج؛ لذلك ورد كل سجل في 4×6=24 مسارًا، واحتمال ظهوره 24/60=2/5. لكننا لم نكتف بهذا العدد الفردي: قارنا الأزواج العشرة نفسها. يشرح مقال العينة العشوائية البسيطة الفرق المفاهيمي؛ هنا اختبرنا إجراءً عمليًا لبنائها أثناء التدفق.

ولفهم النتيجة حسابيًا، افحص الزوج AB: يجب تجاوز الرسائل الثلاث التالية، باحتمال (1/3)×(2/4)×(3/5)=1/10. أما الزوج CE، فقبل الخامسة يجب أن يحتوي الخزان على C، واحتمال ذلك من حصر أول أربع رسائل هو 1/2؛ ثم يجب أن يحل E محل السجل الآخر، باحتمال 1/5. الناتج أيضًا 1/10.

الضمان العام يتعلق بكل مجموعة ذات حجم ثابت، تحت فرض السحوبات المستقلة المنتظمة، لا بجودة مولّد الأعداد المستخدم. تمر خوارزمية R على السجلات مرة واحدة، وتحتفظ بـk سجلات؛ زمنها خطي في عدد السجلات إذا عُدّت عملية السحب والاستبدال ثابتة الكلفة. وصف الخوارزمية.

خطأ صغير يفسد الأزواج

بدّلنا عمدًا draw(t) إلى draw(t-1). عند وصول C لا يبقى إلا الخياران صفر وواحد، فيجب إدخالها، ويستحيل الحفاظ على AB. أصبح عدد المسارات 2×3×4=24. ظهرت الأزواج AC,AD,AE,BC,BD,BE مرتين لكل منها؛ وظهرت CD,CE,DE أربع مرات لكل منها.

لهذا لا تكفي مقارنة عدد نتائج متفرقة، ولا أن ترى خانتين ممتلئتين دائمًا. الاختبار المفيد هنا يختار مثالًا يمكن حصره، ويكشف استبعاد نتيجة كانت يجب أن تبقى ممكنة. لم نختبر عشوائية جهاز أو سرعة معالجة ملف؛ اختبرنا منطق تحديث الخزان.

حدود التطبيق وما تحقق فعليًا

• وسعنا الحصر إلى كل 1≤k≤n≤7: نجحت 28 عائلة أحجام، بإجمالي 10,158 مسارًا. وقورنت النتائج بطريقة ثانية تجمع احتمالات الحالات بكسور دقيقة، دون استخدام منطق خانات الدالة.
• مررنا مولّدًا من 100 سجل؛ استُهلكت جميعها مرة واحدة، وطلبت الدالة 98 سحبًا عند حجم خزان اثنين. لا يحتاج الاستدعاء إلى تحويل المولّد إلى قائمة.
• اختبرنا التدفق الفارغ، والتدفق الأقصر من الحجم المطلوب، وعدم استهلاك المدخل عند الحجم صفر، وسبعة مدخلات غير صالحة.
• في مثال القيم a,a,b ميزنا السجلات بمعرفاتها. الأزواج الثلاثة للمعرفات متساوية، وقد يحتوي أحدها قيمتين متطابقتين. إن كنت تريد قيمًا فريدة فذلك مطلب مختلف؛ حذف التكرار يغير مجتمع الاختيار.

ابدأ بتحديد هوية السجل والحجم المطلوب وسلوك التدفق القصير. ثم افصل مصدر الأعداد عن تحديث الخانات، واختبر كل المسارات في مثال صغير. بهذه الخطوات تستطيع فحص منطق العينة قبل ربطه بتدفقك الحقيقي.

المصادر وملاحظة الإعداد

1. NIST — reservoir sampling
2. Vitter — Random Sampling with a Reservoir، القسم 2
3. Python — random.randrange