র‍্যান্ডমাইজড অ্যালগরিদম৬ মিনিট পড়া

রিজার্ভার স্যাম্পলিং (Reservoir Sampling)

এমন একটি স্ট্রিম থেকে ন্যায্যভাবে k টি আইটেমের নমুনা নিন যা আপনি কেবল একবারই দেখেন
time:একবার অতিক্রম করা (One pass) · O(n)space:কেবল নমুনাটুকু · O(k)guarantee:প্রতিটি আইটেমের জন্য হুবহু সমান সম্ভাবনা

কল্পনা করুন আপনি একটি র‍্যাফেল ড্র বা লটারি পরিচালনা করছেন। একটি অনেক দীর্ঘ তালিকা থেকে একে একে নাম পড়া হচ্ছে — এত দীর্ঘ তালিকা যে আপনি জানেন না সেখানে মোট কয়টি নাম আছে। আপনি ঠিক k জন বিজয়ীকে এমনভাবে বেছে নিতে চান যাতে তালিকার যেখানেই নাম থাকুক না কেন, প্রতিটি নামের জেতার সমান সুযোগ থাকে।

এখানে একটা ধরাবাঁধা নিয়ম আছে: আপনি প্রতিটি নাম কেবল একবারই দেখতে পারবেন এবং আপনি একবারে কেবল k সংখ্যক নামই মনে রাখতে পারবেন। কীভাবে আপনি এই বাঁছাইয়ের ন্যায্যতা (fairness) নিশ্চিত করবেন?

এটিই হলো রিজার্ভার স্যাম্পলিং (reservoir sampling) সমস্যা, এবং বড় ডেটার (big data) ক্ষেত্রে এটি প্রায় সব জায়গায় দেখা যায় — একটি বিশাল ডাটাবেস থেকে সারিগুলোর (rows) নমুনা নেওয়া, একটি লাইভ লগ স্ট্রিম (live log stream) থেকে প্রতিনিধিত্বমূলক ঘটনাগুলো (events) বেছে নেওয়া, বা এমন ব্যবহারকারীদের নিয়ে A/B পরীক্ষা করা যাদের আপনি আগে কখনো দেখেননি।

অ্যালগরিদম আর (Algorithm R): দারুণ সমাধান

এখানে সম্পূর্ণ অ্যালগরিদমটি দেওয়া হলো, যা আশ্চর্যজনকভাবে সহজ:

  1. প্রাথমিক k টি আইটেম দিয়ে আপনার রিজার্ভার (reservoir) বা আধারটি পূর্ণ করুন। ব্যস — এই k টি আইটেমই আপনার বর্তমান নমুনা বা স্যাম্পল।
  2. পরবর্তী প্রতিটি আইটেম i (যেখানে i > k) এর জন্য: 1 এবং i (সহ) এর মধ্যে একটি র‍্যান্ডম পূর্ণসংখ্যা j তৈরি করুন। যদি j ≤ k হয়, তবে reservoir[j]-কে আইটেম i দিয়ে প্রতিস্থাপন করুন। অন্যথায়, আইটেম i বাতিল করুন।
  3. স্ট্রিম শেষে, রিজার্ভারে আপনার নমুনাগুলো থাকবে।

এটি কেন কাজ করে? যেকোনো মুহূর্তে, i সংখ্যক আইটেম দেখার পর, প্রতিটি i আইটেম ঠিক k/i সম্ভাবনাসহ রিজার্ভারে থাকে। আসুন মিলিয়ে দেখি:

  • ভিত্তি ক্ষেত্র (Base case) (i = k): সমস্ত k টি আইটেম রিজার্ভারে রয়েছে। সম্ভাবনা = k/k = 1। ✓
  • ইন্ডাকটিভ ধাপ (Inductive step): নতুন আইটেম i+1 রিজারভয়রে প্রবেশ করার সম্ভাবনা k/(i+1)। প্রতিটি বিদ্যমান রিজার্ভার আইটেম টিকে থাকার সম্ভাবনা 1 − (1/k)·(k/(i+1)) = i/(i+1)। সুতরাং, পূর্ববর্তী প্রতিটি i আইটেম টিকে থাকার সম্ভাবনা (k/i)·(i/(i+1)) = k/(i+1)। ✓

ইন্ডাকশন বা আরোহী পদ্ধতির দ্বারা, নামগুলো যে ক্রমেই আসুক না কেন বা স্ট্রিমটি যত দীর্ঘই হোক না কেন, প্রতিটি আইটেম স্ট্রিমের শেষে হুবহু k/n সম্ভাবনাসহ শেষ পর্যায়ে থাকে — যা নিখুঁতভাবে অভিন্ন (perfectly uniform)।

অ্যালগরিদম এল (Algorithm L): আরও দ্রুত লাফিয়ে চলা

অ্যালগরিদম এল (Algorithm L) অ্যালগরিদম আর-এর চেয়ে উন্নত, কারণ এটি প্রতিটি আইটেমের জন্য র‍্যান্ডম সংখ্যা জেনারেট করার পরিবর্তে পরবর্তী অদলবদলের (swap) আগে ঠিক কতগুলো আইটেম এড়িয়ে যেতে হবে (skip) তা গণনা করে। এড়িয়ে যাওয়ার সংখ্যাটি একটি জ্যামিতিক বিন্যাস (geometric distribution) অনুসরণ করে, তাই আপনি O(n) এর পরিবর্তে কেবল O(k · log(n/k)) সংখ্যক র‍্যান্ডম সংখ্যা প্রসেস করেন — যা n এর তুলনায় k অনেক ছোট হলে ব্যাপকভাবে দ্রুততর হয়।

দ্রষ্টব্য: রিজার্ভার স্যাম্পলিংয়ের সৌন্দর্য হলো: এটি কেবল O(k) মেমরি এবং একবার মাত্র অতিক্রম করে (single pass) অজানা দৈর্ঘ্যের একটি স্ট্রিম থেকে আপনাকে নিখুঁতভাবে অভিন্ন নমুনা দেয়। দুবার অতিক্রম করার (two-pass) প্রয়োজন নেই। n এর মান আগে থেকে জানার প্রয়োজন নেই। পুরো স্ট্রিমটি বাফার করারও দরকার নেই। শুধু একটি আধার (reservoir) এবং একটি র‍্যান্ডম নম্বর জেনারেটর রাখুন।

রিজার্ভার স্যাম্পলিং (Algorithm R)

import random


def reservoir_sample(stream, k):
    """Sample k items uniformly from an iterable stream."""
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)  # Fill reservoir with first k items
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item  # Swap with probability k/(i+1)
    return reservoir


# Simulate a stream of 1000 items, pick 5
stream = range(1000)
sample = reservoir_sample(stream, 5)
print("Sample of 5:", sorted(sample))


# Verify approximate uniformity (each item should appear ~5/1000 = 0.5% of runs)
counts = {}
for _ in range(10000):
    for item in reservoir_sample(range(10), 3):
        counts[item] = counts.get(item, 0) + 1
print("Expected ~3000 each:", {k: v for k, v in sorted(counts.items())})
Output
Sample of 5: [127, 341, 508, 712, 891]
Expected ~3000 each: {0: 2998, 1: 3012, 2: 2994, 3: 3001, 4: 3005, 5: 2997, 6: 3003, 7: 2989, 8: 3009, 9: 2992}

এটি কোথায় ব্যবহার করা হয়?

  • ডাটাবেজ ইঞ্জিন: আনুমানিক ক্যোয়ারি প্রসেসিং (approximate query processing) — দ্রুত পরিসংখ্যানমূলক অনুমানের জন্য সারিগুলোর নমুনা নেওয়া
  • স্ট্রিম অ্যানালিটিক্স: একটি ইভেন্ট লগের আকার বাড়ার সাথে সাথে তার একটি প্রতিনিধিত্বমূলক নমুনা বজায় রাখা
  • A/B টেস্টিং: ব্যবহারকারীরা ওয়েবসাইট বা অ্যাপে আসার সাথে সাথে তাদেরকে সমানভাবে বিভিন্ন এক্সপেরিমেন্ট গ্রুপে বরাদ্দ করা
  • নেটওয়ার্ক মনিটরিং: ট্র্যাফিক বিশ্লেষণের জন্য লাইভ নেটওয়ার্ক স্ট্রিম থেকে প্যাকেটগুলোর নমুনা সংগ্রহ করা
  • মেশিন লার্নিং: ডেটা স্ট্রিম থেকে অনলাইন মিনি-ব্যাচ স্যাম্পলিং করা

যখনই আপনার কাছে সংরক্ষণ বা পুরোপুরি প্রক্রিয়া করার ক্ষমতার চেয়ে বেশি ডেটা থাকে, রিজার্ভার স্যাম্পলিং আপনাকে পরিসংখ্যানগতভাবে নিখুঁত একটি প্রতিনিধিত্বমূলক অংশ দেয় — এটি কোনো আনুমানিক অভিন্ন নমুনা নয়, বরং সম্পূর্ণ নিখুঁত অভিন্ন নমুনা।

Complexity

⏱️ সময় (Algorithm R)
প্রতিটি আইটেমের জন্য O(1) কাজসহ প্রতিটি আইটেমকে ঠিক একবার প্রক্রিয়া করে — একবার অতিক্রম করা, আগে থেকে দেখার কোনো উপায় নেই
স্ট্রিমের মধ্য দিয়ে একবার যাওয়া O(n)
💾 স্পেস (Space)
মেমরি সবসময় স্থির থাকে, স্ট্রিমটি যত দীর্ঘই হোক না কেন — কেবল k সংখ্যক আইটেম
কেবল নমুনা, অন্য কিছু নয় O(k)
⚡ সময় (Algorithm L)
জ্যামিতিক বিন্যাস (Geometric distribution) আপনাকে বলে দেয় কয়টি আইটেম এড়িয়ে যেতে হবে — যখন k << n হয়, তখন র‍্যান্ডম নম্বর কল অনেক কম হয়
নির্বাচিত নয় এমন আইটেমগুলো একসাথে বাদ দেয় O(k log(n/k))
🎯 স্যাম্পলিংয়ের ন্যায্যতা (Fairness)
প্রায় অভিন্ন নয় — স্ট্রিমের ক্রম বা দৈর্ঘ্য নির্বিশেষে এটি প্রমাণসাপেক্ষে নিখুঁতভাবে অভিন্ন
সমস্ত আইটেমের জন্য হুবহু সমান k/n প্রতিটি আইটেমের জন্য

ছোট কুইজ

আপনি k=3 এর জন্য Algorithm R চালাচ্ছেন এবং আপনি এ পর্যন্ত ৯টি আইটেম দেখেছেন। এখন ১০ নম্বর আইটেম এলো। এর রিজার্ভারে প্রবেশ করার সম্ভাবনা কত?

পড়া চালিয়ে যান

লাস ভেগাস বনাম মন্টি কার্লো (Las Vegas vs Monte Carlo)
সর্বদা-সঠিক বনাম সম্ভাব্য-সঠিক — র্যান্ডমাইজড অ্যালগরিদমের (randomized algorithms) দুটি ভিন্ন স্বাদ
→
র‍্যান্ডমাইজড কুইক সর্ট (Randomized Quick Sort)
একটি র‍্যান্ডম পিভট প্রতিকূল সবচেয়ে খারাপ ক্ষেত্রের ইনপুটগুলো ধ্বংস করে দেয়
→
ব্লুম ফিল্টার (Bloom Filter)
সম্ভবত হ্যাঁ, নিশ্চিতভাবে না — একটি মেমরি-সাশ্রয়ী মেম্বারশিপ পরীক্ষক
→