import random
import statistics
import time


def reservoir_sample(stream, k, rng):
    if k < 0:
        raise ValueError('k must be non-negative')
    sample = []
    if k == 0:
        return sample
    for i, item in enumerate(stream, 1):
        if i <= k:
            sample.append(item)
        else:
            position = rng.randrange(i)
            if position < k:
                sample[position] = item
    return sample


def vertex_cover_2approx(edges):
    if any(a == b for a, b in edges):
        raise ValueError('this example requires no self-loops')
    cover = set()
    for a, b in edges:
        if a not in cover and b not in cover:
            cover.update((a, b))
    return cover


def membership_benchmark(n, repeats=5):
    if n <= 0 or repeats <= 0:
        raise ValueError('n and repeats must be positive')
    rng = random.Random(20)
    values = [rng.randrange(2 * n) for _ in range(n)]
    queries = [rng.randrange(2 * n) for _ in range(min(n, 300))]
    members = set(values)
    expected = sum(query in values for query in queries)
    result = {}
    for label, container in [('list', values), ('set', members)]:
        samples = []
        for _ in range(repeats):
            start = time.perf_counter()
            actual = sum(query in container for query in queries)
            samples.append(time.perf_counter() - start)
            if actual != expected:
                raise AssertionError('implementations disagree')
        result[label] = {'hits': expected, 'median_seconds': statistics.median(samples)}
    return result


if __name__ == '__main__':
    print(reservoir_sample(iter(range(100)), 5, random.Random(20)))
    print(sorted(vertex_cover_2approx([(0, 1), (1, 2), (2, 3)])))
    for size in (128, 512, 2048):
        print(size, membership_benchmark(size))