boundary/folsom — pull request #6 by nygge (2011-10-31 16:45:56+00:00)
Title: Optimize folsom_sample_uniform

Use a dict instead of list for the reservoir.

This improves the performance of folsom_sample_uniform.
On my laptop inserting 5000 element in a sample with reservoir size=5000, is about 10x faster.
Inserting 50000 elements in a sample with reservoir size=5000 is about 50x faster.

Note that the order of the elements returned by get_values is different from the previous algorithm,
but I don't think that matters since the elements are inserted randomly anyway.

This patch only changes the data structure used for the reservoir, it does not change the basic algorithm
used. I think that there is a bug in how the sampling is done, I will open an issue describing that.

/Anders