3 ms·
It’s related to Fisher-Yates shuffle, https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to_Fisher-Yates_shuffle https://en.wikipedia.org/wiki/Reservoir_
by dahart 7y ago
It’s related to Fisher-Yates shuffle, https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to_Fisher-Yates_shuffle https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to...
But it’s not the same thing. The difference is whether you can keep all samples in memory at the same time. With Vitter / reservoir sampling, you only need to have your reservoir in memory plus enough space for 1 new sample at a time, so you can stream through a large number of samples with a tiny amount of memory.