Reservoir sampling

by

I actually did not realize there was a name for this, so I proved and implemented this from scratch:

import random
def random_subset( iterator, K ):
    result = []
    N = 0

    for item in iterator:
        N += 1
        if len( result ) < K:
            result.append( item )
        else:
            s = int(random.random() * N)
            if s < K:
                result[ s ] = item

    return result

From: http://web.archive.org/web/20141026071430/http://propersubset.com:80/2010/04/choosing-random-elements.html

With a proof near the end.

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. Expand a random range from 1–5 to 1–7
  3. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  4. What distribution do you get from this broken random shuffle?
  5. Select k random elements from a list whose elements have weights
  6. Data structures for loaded dice?
  7. Pseudorandom Number Generator – Exponential Distribution
  8. Choosing n numbers with fixed sum
  9. Shuffle list, ensuring that no item remains in same position
  10. True random number generator [closed]
  11. Create a random permutation of 1..N in constant space
  12. Creating a random number generator from a coin toss
  13. Given a number, produce another random number that is the same every time and distinct from all other results
  14. Random points inside a parallelogram
  15. Generating shuffled range using a PRNG rather than shuffling
  16. Randomly choosing from a list with weighted probabilities
  17. A Good and SIMPLE Measure of Randomness
  18. Unbiased random number generator using a biased one
  19. Efficient way to add element to sorted datastructure [closed]
  20. How to count the number of set bits in a 32-bit integer?
  21. Algorithm to return all combinations of k elements from n
  22. Algorithm to randomly generate an aesthetically-pleasing color palette [closed]
  23. Binary Search in Array
  24. The Sieve of Atkin
  25. Finding the best trade-off point on a curve
  26. How to hash a string into 8 digits?
  27. what is the fastest way to find the gcd of n numbers?
  28. Why is bubble sort O(n^2)?
  29. Location of highest density on a sphere
  30. Why is the “start small” algorithm for branch displacement not optimal?

Leave a Comment