library/python/reservoir_sampling/__init__.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import random


def reservoir_sampling(data, nsamples, prng=None):
    if prng is None:
        prng = random

    result = []
    for i, entry in enumerate(data):
        if i < nsamples:
            result.append(entry)
        else:
            j = prng.randint(0, i)
            if j < nsamples:
                result[j] = entry
    return result