Reservoir Sampling

import random

def printArray(stream,n):

for i in range(n):

print(stream[i],end=" ");

print();

def selectKItems(stream, n, k):

i=0;

reservoir = [0]*k;

for i in range(k):

reservoir[i] = stream[i];

while(i < n):

j = random.randrange(i+1);

if(j < k):

reservoir[j] = stream[i];

i+=1;

print("Following are k randomly selected items");

printArray(reservoir, k);

if __name__ == "__main__":

stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];

n = len(stream);

k = 5;

selectKItems(stream, n, k);


No comments: