3 ms·
IMO the Wikipedia article on this is better than this article: https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
by pmiller2 11y ago
IMO the Wikipedia article on this is better than this article: https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
- sika_grr 11y agoI only see an O(n) algorithm there, there is no O(k). Am I missing something?
- pps43 11y agoWiki shows Algorithm R, this article talks about Algorithm D, both by the same author. The former is well known, while the latter is more obscure. This is probably because the extra complexity of Algorithm D is rarely necessary. If k and n are on the same order of magnitude, there is not much difference, and if k << n then simple random sampling would work nearly as well.