reservoir.py

from random import *

# Classical reservoir sampling
def sample1(xs):
    n = 0
    y = None
    for x in xs:
        n += 1
        if randrange(n) == 0: y = x
    return y

# Reservoir sampling with bounded buffer
def sample2(xs, max_buf):
    buf = []
    n = 0
    y = None
    for x in xs:
        buf.append(x)
        n += 1
        if len(buf) == max_buf:
            i = randrange(n)
            if i < len(buf): y = buf[i]
            buf.clear()
    if buf:
        i = randrange(n)
        if i < len(buf): y = buf[i]
    return y

print(sample2(range(10), 1))