रिजर्वायर सैंपलिंग

परिचय

रिजर्वायर सैंपलिंग एक यादृच्छिक एल्गोरिदम है। इस एल्गोरिदम में, k आइटम n अलग-अलग आइटम की सूची से चुने जाते हैं।

हम इसे आकार k की एक सरणी को रिजर्वायर के रूप में बनाकर हल कर सकते हैं। फिर मुख्य सूची से बेतरतीब ढंग से एक तत्व चुनें और उस आइटम को रिजर्वायर सूची में रखें। जब एक आइटम एक बार चुना जाता है, तो इसे अगली बार के लिए नहीं चुना जाएगा। लेकिन यह दृष्टिकोण प्रभावी नहीं है, हम इस विधि द्वारा जटिलता बढ़ा सकते हैं।

रिजर्वायर सूची में, सूची से पहले k आइटम कॉपी करें, अब सूची में (k+1)वें नंबर से एक-एक करके, मान लें कि वर्तमान चयनित आइटम इंडेक्स i पर रखा गया है। 0 से i तक एक यादृच्छिक इंडेक्स ढूंढें और इसे j में संग्रहीत करें, यदि j 0 से k की रेंज में है, तो reservoir[j] को list[i] के साथ स्वैप करें।

इनपुट और आउटपुट

इनपुट: पूर्णांकों की सूची: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, k का मान = 6
आउटपुट: दी गई सरणी में K-चयनित आइटम: 8 2 7 9 12 6

एल्गोरिदम

chooseKItems(array, n, k)
इनपुट: सरणी, सरणी में तत्वों की संख्या, चुनने के लिए तत्वों की संख्या
आउटपुट: k तत्वों को बेतरतीब ढंग से चुनें

Begin
    आकार [k] का आउटपुट सरणी परिभाषित करें
    सरणी से पहले k आइटम आउटपुट में कॉपी करें
    जब तक i < n, करें
        j := 0 से i तक बेतरतीब ढंग से एक मान चुनें
        यदि j < k, तो
            output[j] := array[i]
        i को 1 से बढ़ाएं
    done
    आउटपुट सरणी प्रदर्शित करें
End

उदाहरण (C++ कोड)

#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); // 0 से 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