Reservoir Sampling (online)
Last updated
Last updated
Given a array A
read in as a data stream (one by one) and a sample size k
, return a sample of size k
in the data stream.
Idea:
Assume we already choose k samples from n data, now we read in the n+1 data. The new data has probability to be sampled. And the existing samples have the same probability to be removed.
Time complexity:
Space complexity: