وقتی طولِ جریان از ابتدا معلوم نیست، Reservoir Sampling می‌تواند نمونه‌ای با حداکثرِ k عضو نگه دارد. در الگوریتمِ R، هر ردیفِ تازه بر اساسِ شمارهٔ ورود شانسِ جایگزینی می‌گیرد؛ نمونهٔ نهایی فقط چند ردیفِ اول نیست. این صفحه یک جریانِ پنج‌ردیفی، بافرِ دوعضوی و تمامِ ۶۰شاخهٔ تصادفیِ همان مثال را واقعاً محاسبه می‌کند.
ردیف‌هایِ اول را تا ابد نگه نداریم
جریانِ اصیلِ ما پنج ردیف با positionِ ۱تا۵ دارد. ابتدا دو ردیفِ اول در بافر قرار می‌گیرند. برای ردیفِ jامِ بعدی، یک عددِ صحیح از۰تاj−۱ می‌گیریم؛ اگر عدد ازk کمتر بود، همان خانهٔ بافر با ردیفِ تازه عوض می‌شود. قراردادِ صفرمبنا معادلِ صورتِ یک‌مبنایِ تعریفِ مرجع است، اما دو نمایش را در کد قاطی نمی‌کنیم.
تابع، طولِ کل را از ورودی دریافت نمی‌کند؛ در هر گام فقط شمارندهٔ دیده‌شده را دارد. برایِ محدودماندنِ این فایلِ آموزشی، جریانِ بیش از۳۲ردیف و kِ بیرونِ ۰تا۸ رد می‌شوند. این سقف‌ها بخشی از wrapperِ ما هستند و حدِ عمومیِ الگوریتم یا سرویس نیستند.
یک اجرایِ ثبت‌شده را دنبال کنیم
با Random(37)، بافر پس از دو ردیفِ اول[۱،۲] است. در ردیفِ ۳، انتخابِ صفرمبنای۲ تغییری نمی‌دهد. در ردیفِ ۴، انتخابِ ۰ خانهٔ اول را عوض می‌کند و بافر[۴،۲] می‌شود. در ردیفِ ۵، انتخابِ ۴ بیرونِ دو خانه است؛ نمونهٔ نهایی همان[۴،۲] می‌ماند. تمامِ trace در JSON آمده است.
| ردیفِ ورودی | انتخابِ صفرمبنا | positionهایِ بافر |
|---|---|---|
| ۱ | برداشتِ تصادفی ندارد | [۱] |
| ۲ | برداشتِ تصادفی ندارد | [۱،۲] |
| ۳ | ۲ | [۱،۲] |
| ۴ | ۰ | [۴،۲] |
| ۵ | ۴ | [۴،۲] |
حفظِ ترتیبِ بافر، مرتب‌سازیِ زمانِ ورود نیست. در خروجی، positionها هویتِ ردیف‌اند. دو ردیفِ ۲و۳ عمداً contentِ یکسانِ same دارند؛ آن‌ها دو مشاهدهٔ جدا هستند و صرفاً به‌دلیلِ برابریِ محتوا با هم ادغام نمی‌شوند. انتخابِ نمونه، روشِ حذفِ رکوردِ تکراری نیست.
به یک seed برایِ بحثِ احتمال اکتفا نکنیم
برای این مسئلهٔ کوچک، تعدادِ انتخاب‌هایِ ممکن در گام‌هایِ ۳،۴و۵ به‌ترتیب۳،۴و۵ است؛۶۰مسیر داریم. کد با Choicesِ کنترل‌شده همهٔ مسیرها را اجرا می‌کند. ده زیرمجموعهٔ دوعضویِ ممکن از پنج position با combinationsِ مستقل ساخته می‌شوند و با نتیجهٔ واقعی مقایسه می‌شوند.
هر زیرمجموعه دقیقاً در۶مسیر از۶۰مسیر ظاهر می‌شود؛ Fraction احتمال را۱÷۱۰ نگه می‌دارد. این شمارشِ کامل، شاهدِ دقیقِ همینN=5 وk=2 با انتخاب‌هایِ یکنواخت است. آن را اثباتِ ماشینیِ همهٔ طول‌ها، آزمونِ کیفیتِ مولد یا تضمینِ نمایندگیِ کسب‌وکار نمی‌نامیم.
جریانِ کوتاه، خالی و kِ صفر
اگر فقط یک ردیف برسد وk=2 باشد، همان یک ردیف برمی‌گردد؛ عضوِ جعلی برایِ پرکردنِ بافر نمی‌سازیم. جریانِ خالی خروجیِ خالی وk=0 نمونهٔ خالی می‌دهد. kِ منفی،bool و عددِ ۹ در قراردادِ محدودِ تمرین رد می‌شوند. پس از هر گام نیز اندازهٔ واقعیِ بافر ازk بیشتر نیست.
تابع برایِ گزارشِ آموزشی، traceِ هر گام را هم نگه می‌دارد؛ بنابراین حافظهٔ کلِ این نسخه را فقطO(k) اعلام نمی‌کنیم. بافرِ نمونه حداکثرk است، اما دفترِ trace با تعدادِ گام‌ها رشد می‌کند و به همین دلیل سقفِ ۳۲داریم. الگوریتمِ جریان و ابزارِ نمایشِ آموزشی را جدا توصیف کنیم.
نمونهٔ یکنواخت، الزاماً نمایندهٔ هر گروه نیست
یک نمونهٔ کوچک می‌تواند گروهی را نبیند. برایِ هدفِ کنترلِ کیفیت و پوششِ شیفت‌ها، نمونه‌گیریِ طبقه‌ایِ تماس سؤالِ دیگری دارد. Reservoirِ واحد در این صفحه سهمیهٔطبقه‌ها یا نسبتِ خطایِ مرکز را برآورد نمی‌کند؛ داده‌ها همگی ساختگی‌اند.
Bootstrapِ جنگلِ تصادفی انتخابِ با‌جایگذاری دارد؛ نمونهٔpositionهایِ این الگوریتم آن قرارداد نیست. برایِ ادامه در مبانی هوش مصنوعی، واحدِ نمونه،شانسِ انتخاب ودامنهٔتعمیم را ثبت کنید. اجرایِ Python۳٫۱۲٫۱۴ این صفحه هیچ تماسِ واقعی،مدل یا خدمتِ تحلیلِ محصول را آزمایش نکرده است.
فایل تمرین و منبع
کد مستقلِ تمرینِ محدود · تمام خروجیِ واقعیِ همین تمرین؛ JSON
- NIST DADS؛ تعریفِReservoir Sampling،انتخابِیکنواخت؛ اصلاحِمدخل۲۱ژانویه۲۰۲۰
- Python۳٫۱۲؛ Random وrandrange؛ محدودیتِبازتولید و ماهیتِغیررمزنگاری
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.