Created
July 2, 2013 17:08
-
-
Save tantalor/5911137 to your computer and use it in GitHub Desktop.
Testing whether reservoir sampling works when you sample the RNG only once. reservoir1: Samples RNG once per stream element.
reservoir2: Samples the RNG once per stream.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from random import random as rand | |
def reservoir1(stream): | |
i = 1 | |
choice = None | |
for value in stream: | |
if rand() * i < 1: | |
choice = value | |
i = i + 1 | |
return choice | |
def reservoir2(stream): | |
r = rand() | |
i = 1 | |
choice = None | |
for value in stream: | |
if r * i < 1: | |
choice = value | |
i = i + 1 | |
return choice | |
def test(stream, reservoir, n=1000): | |
histo = {} | |
for k in xrange(0, n): | |
choice = reservoir(stream) | |
histo[choice] = histo.get(choice, 0) + 1 | |
return histo | |
get_stream = lambda: xrange(0, 8) | |
print "reservoir1: ", test(get_stream(), reservoir1) | |
print "reservoir2: ", test(get_stream(), reservoir2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I'm sure it must be weird getting a comment on this repo 5 years after putting it up, but the reason
reservoir2
is not uniform is because of a bug on line 14.r
is being assigned as some fixed floating point number at the start withr = rand()
and then it never changes in the for-loop. Calling r at this point only returns the same number over and over. Deleting line 14 and changing line 18 toif rand() * i < 1:
fixes the issue