News for hackers. Stuff that matters.

A comment on Algorithms Every Programmer Should Know: Reservoir Sampling. Parent comment

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by danieldk on Friday March 06, 2015 @01:59PM (#9158784)
Looping n times, calling rand(n) and putting the random element in the output. This mostly works, and is actually far better, in space and time,

Reservoir sampling is normally used on large streams where you do not want to or cannot keep the data you are sampling from in memory.

[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by javajosh on Friday March 06, 2015 @02:18PM (#9158931)
Then I'm a little bit worried about this algorithm, because if the probability of picking is n/idx then the odds of picking a long tail item get asymptotically close to 0. I'm not sure if it really qualifies as a sample of the entire thing.
[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by loqi on Friday March 06, 2015 @05:50PM (#9160096)
Intuitively, the reason why it balances out is that while earlier items are more likely to be picked, they're also more likely to get kicked out after being picked.
[ Parent | on HN ]
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by c0ldfusion on Friday March 06, 2015 @02:31PM (#9159019)
proof is in the article http://en.wikipedia.org/wiki/Reservoir_sampling
[ Parent | on HN ]