Узорковање из резервоара
Узорковање из резервоара припада породици алгоритама вероватноће и служи да насумично одабере к узорака из листе С која у себи садржи н чланова, н је или изузетно велики број или је непознат број. Углавном је н довољно велики да не може да стане у главну меморију рачунара. Сложеност овог алгоритма је О(н) (Под претпоставком да су низови једнодимензиони и да је број узорака к мањи од укупног броја елемената резервоара).[1][2]
Псеудо код[уреди | уреди извор]
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
Сличности са Фисхер Yатес методом мешања[уреди | уреди извор]
Рецимо да неко жели да извуче к насумичних карата из шпила од 52 карте за игре. Очигледан приступ би био да се цео шпил промеша и да се потом из шпила извуче к карата. У општем случају извлачење к карата мора да функционише и онда када нам укупан број карата није познат. Овај услов задовољава обрнута верзија Фисхер-Yатес методе мешања
//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]
Обзиром на то да су првих к карата неважни, прва петља се може уклонити и а се може иницијализовати тако да то буду првих к елемената С.
C имплементација[уреди | уреди извор]
#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; }