Reservoir sampling

Question

to retrieve k random numbers from an array of undetermined size we use a technique called reservoir sampling. Can anybody briefly highlight how it happens with a sample code??

Answer 1

This page contains a good explanation with pseudo-code. (The Wikipedia page I originally linked to is unclear, and the pseudo-code is incomplete.)

Answer 2

I wrote a blog entry about the exact thing a couple of months back, which has a C# implementation: http://gregbeech.com/blog/sampling-very-large-sequences

The best description of how it works that I've found is here: http://gregable.com/2007/10/reservoir-sampling.html

Answer 3

I actually did not realize there was a name for this, so I proved and implemented this from scratch:

import random
def random_subset( iterator, K ):
    result = []
    N = 0

    for item in iterator:
        N += 1
        if len( result ) < K:
            result.append( item )
        else:
            s = int(random.random() * N)
            if s < K:
                result[ s ] = item

    return result

From: http://propersubset.com/2010/04/choosing-random-elements.html

with a proof near the end.