News for hackers. Stuff that matters.

A comment on Vitter's reservoir sampling algorithm D: randomly selecting unique items. Parent comment

Re:Vitter's reservoir sampling algorithm D: randomly selecti... by tomp on Monday April 04, 2016 @04:17AM (#11420197)
"sequential" in the sense that if returned values are i1, i2, ..., in, then 0 <= i1 < i2 < ... < in <= N.

A MLCG will return numbers all over the place; sorting them will take an additional O(n log n) time.

[ Parent | on HN ]
Re:Vitter's reservoir sampling algorithm D: randomly selecti... by vrfcodf on Monday April 04, 2016 @04:22AM (#11420220)
I see.
[ Parent | on HN ]