Uzorkovanje iz rezervoara

Uzorkovanje iz rezervoara pripada porodici algoritama verovatnoće i služi da nasumično odabere k uzoraka iz liste S koja u sebi sadrži n članova, n je ili izuzetno veliki broj ili je nepoznat broj. Uglavnom je n dovoljno veliki da ne može da stane u glavnu memoriju računara. Složenost ovog algoritma je O(n) (Pod pretpostavkom da su nizovi jednodimenzioni i da je broj uzoraka k manji od ukupnog broja elemenata rezervoara).

Pseudo kod

array R[k];    // rezultat
integer i, j;

// punjenje rezervoara
for each i in 1 to k do
    R[i] := S[i]
done;

// menjanje elemenata sa postepenim smanjivanjem verovatnoće
for each i in k+1 to length(S) do
    j := random(1, i);   
    if j <= k then
        R[j] := S[i]
    fi
done

Sličnosti sa Fisher Yates metodom mešanja

Recimo da neko želi da izvuče k nasumičnih karata iz špila od 52 karte za igre. Očigledan pristup bi bio da se ceo špil promeša i da se potom iz špila izvuče k karata. U opštem slučaju izvlačenje k karata mora da funkcioniše i onda kada nam ukupan broj karata nije poznat. Ovaj uslov zadovoljava obrnuta verzija Fisher-Yates metode mešanja

//Inicijalizacija niza a sa k nasumičnih elemenata S(dužine n), oba niza počinju od nule
  a[0] ← S[0]
   for i from 1 to k - 1 do
       r ← random (0 .. i)
       a[i] ← a[r]
       a[r] ← S[i]
   for i from k to n - 1 do
       r ← random (0 .. i)
       if (r < k) then a[r] ← S[i]

Obzirom na to da su prvih k karata nevažni, prva petlja se može ukloniti i a se može inicijalizovati tako da to budu prvih k elemenata S.

C implementacija

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
void printArray(int stream[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", stream[i]);
    printf("\n");
}
 
// funkcija za nasumičan odabir k elemenata iz niza stream [0..n-1].
void selectKItems(int stream[], int n, int k)
{
    int i;  // indeks za elemente stream-a[]
 
    // reservoir[] je niz za rezultat inicijalizuje se sa prvih k elemenata iz niza stream
    int reservoir[k];
    for (i = 0; i < k; i++)
        reservoir[i] = stream[i];
 
    srand(time(NULL));

    for (; i < n; i++)
    {
        int j = rand() % (i+1);
 
        // ako je nasumično odabran indeks manji od k
        //zameniti trenutni element sa novim elementom iz niza stream
        if (j < k)
          reservoir[j] = stream[i];
    }
 
    printArray(reservoir, k);
}
 
int main()
{
    int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int n = sizeof(stream)/sizeof(stream[0]);
    int k = 5;
    selectKItems(stream, n, k);
    return 0;
}