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

রেজারভোয়ার স্যাম্পলিং একটি র‍্যান্ডোমাইজড অ্যালগরিদম। এই অ্যালগরিদমে, nটি ভিন্ন আইটেমের একটি লিস্ট থেকে kটি আইটেম বেছে নেওয়া হয়।

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

রেজারভোয়ার লিস্টে, লিস্ট থেকে প্রথম kটি আইটেম কপি করুন, এখন এক এক করে (k+1)তম নম্বর থেকে লিস্টে, ধরা যাক বর্তমান নির্বাচিত আইটেম inde x i-তে থাকে। ০ থেকে i পর্যন্ত একটি র‍্যান্ডোম ইনডেক্স বের করুন এবং j-তে সংরক্ষণ করুন, যদি j ০ থেকে k-এর রেঞ্জে থাকে, তবে reservoir[j]-কে list[i]-এর সাথে সোয়াপ করুন।

ইনপুট এবং আউটপুট

ইনপুট: পূর্ণসংখ্যার তালিকা: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, k এর মান = ৬ আউটপুট: দিয়ে गये অ্যারেতে K-নির্বাচিত আইটেম: 8 2 7 9 12 6

অ্যালগরিদম

chooseKItems(array, n, k)

ইনপুট: অ্যারে, অ্যারেতে এলিমেন্টের সংখ্যা, বেছে নেওয়ার জন্য এলিমেন্টের সংখ্যা।

আউটপুট: kটি এলিমেন্ট র‍্যান্ডমলি বেছে নিন।

শুরু 
  output অ্যারে সংজ্ঞায়িত করুন আকার [k] 
  অ্যারে থেকে প্রথম k আইটেম আউটপুট-এ কপি করুন 
  যতক্ষণ i < n, করুন 
    j := ০ থেকে i পর্যন্ত র‍্যান্ডমলি একটি মান বেছে নিন 
    যদি j < k, তবে 
      output[j] := array[i] 
    i ১ বাড়ান 
  শেষ 
  আউটপুট অ্যারে প্রদর্শন করুন 
শেষ 

উদাহরণ

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; void display(int array[], int n) {   for (int i = 0; i < n; i++)     cout << array[i] << " "; } void chooseKItems(int array[], int n, int k) {       //এটি অ্যারে থেকে k আইটেম বেছে নেবে   int i;   int output[k];   for (i = 0; i < k; i++)     output[i] = array[i];   srand(time(NULL));       //ভিন্ন সিড ভ্যালু পেতে টাইম ফাংশন ব্যবহার   while(i < n) {     int j = rand() % (i+1);       //০ থেকে i পর্যন্ত র‍্যান্ডম ইনডেক্স     if (j < k)       //i-তম এলিমেন্ট আউটপুট অ্যারেতে j-তম এলিমেন্টে কপি করুন       output[j] = array[i];     i++;   }   cout << "K-Selected items in the given array: ";   display(output, k); } int main() {   int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};   int n = 12;   int k = 6;   chooseKItems(array, n, k); }

আউটপুট

K-Selected items in the given array: 8 2 7 9 12 6