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).Random -{Sampling with a Reservoir}--{Dictionary of Algorithms and Data Structures}-

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 ← S 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); int k = 5; selectKItems(stream, n, k); return 0; }

Reference

Категорија:Алгоритми Категорија:Пробабилистичка теорија комплексности