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 throwaway_yy2Di on Monday April 04, 2016 @04:02AM (#11420149)
This works, and is so much simpler.

It's not quite the same problem though; the algorithm described returns samples in sequential order. They mention performance reasons for this (C-f "tape sampling"). It also has the limitation that you need to know the sample size in advance.

[ Parent | on HN ]
Re:Vitter's reservoir sampling algorithm D: randomly selecti... by vrfcodf on Monday April 04, 2016 @04:07AM (#11420164)
MLCG is sequential. No value will be repeated within the period.
[ Parent | on HN ]
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 ]
Re:Vitter's reservoir sampling algorithm D: randomly selecti... by tomsmeding on Monday April 04, 2016 @04:15AM (#11420188)
He means: outputs are sorted.
[ Parent | on HN ]