2 ms·
It seems like nobody else mentioned this, so for completeness: the algorithm is called reservoir sampling. It allows you to sample n elements from a potentiall
by kqr 6y ago
It seems like nobody else mentioned this, so for completeness: the algorithm is called reservoir sampling.
It allows you to sample n elements from a potentially very big stream with exactly n elements of storage. Incredibly neat technique.
Lots written about it a web search away once you know its name!
(If the sequence is in primary memory with fast random access, it's more efficient to run n iterations of a Fisher-Yates shuffle and pick the first n elements.)
Edit: I forgot to refresh the comments page. Someone had mentioned it now. Good!