Узорковање из резервоара

С Википедије, слободне енциклопедије

Узорковање из резервоара припада породици алгоритама вероватноће и служи да насумично одабере к узорака из листе С која у себи садржи н чланова, н је или изузетно велики број или је непознат број. Углавном је н довољно велики да не може да стане у главну меморију рачунара. Сложеност овог алгоритма је О(н) (Под претпоставком да су низови једнодимензиони и да је број узорака к мањи од укупног броја елемената резервоара).[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;
}

Референце[уреди | уреди извор]