Algorithms Every Programmer Should Know: Reservoir Sampling

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by eru on Saturday March 07, 2015 @08:01AM (#9161730)

> Reservoir sampling is still O(N), and it requires generating a random number for every element.

I agree with your comment in general. Only: you can do better than generate a random number for each element. (Generate a random number to tell you how many elements in the steam to skip.)

[ Parent | on HN ]

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by alok-g on Saturday March 07, 2015 @11:25AM (#9162158)

Can you show that this will still maintain a uniform probability distribution?

[ Parent | on HN ]

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by shoegumfoot on Sunday March 08, 2015 @02:52PM (#9166654)

> Can you show that [generating a number of records to skip instead of a yes/no for each record] will still maintain a uniform probability distribution?

That should work if you pull the skip count from the appropriate distribution (negative binomial, I think).

[ Parent | on HN ]

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by eru on Monday March 09, 2015 @08:28PM (#9175110)

Yes, you have to work out the right distribution, and how to sample from it (at all, and perhaps how to sample from it efficiently).

[ Parent | on HN ]

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by eru on Sunday March 08, 2015 @12:25AM (#9164677)

Yes.

[ Parent | on HN ]