# Reservoir Sampling

DevFeed: [Reservoir Sampling](<https://devfeed.tech/articles/reservoir-sampling-40325.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/07/05/reservoir-sampling/>)

Published: 2013-07-05T10:00:49Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Python](<https://devfeed.tech/topics/python.md>), [data](<https://devfeed.tech/topics/data.md>), [datasets](<https://devfeed.tech/topics/datasets.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [big-data](<https://devfeed.tech/tags/big-data.md>), [generator](<https://devfeed.tech/tags/generator.md>), [induction](<https://devfeed.tech/tags/induction.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [random](<https://devfeed.tech/tags/random.md>), [randomized-algorithm](<https://devfeed.tech/tags/randomized-algorithm.md>), [reservoir-sampling](<https://devfeed.tech/tags/reservoir-sampling.md>), [sample](<https://devfeed.tech/tags/sample.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [streaming-data](<https://devfeed.tech/tags/streaming-data.md>), [streams](<https://devfeed.tech/tags/streams.md>)

## AI overview

This tutorial explains reservoir sampling for selecting an item uniformly at random from a data stream whose size is unknown or too large to store in memory. Its Python algorithm keeps one item and replaces it at step k with probability 1/k, with an induction-based proof of uniform selection.

## Source excerpt

Problem: Given a data stream of unknown size $ n$, pick an entry uniformly at random. That is, each entry has a $ 1/n$ chance of being chosen. Solution: (in Python) import random def reservoirSample(stream): for k,x in enumerate(stream, start=1): if random.random() < 1.0 / k: chosen = x return chosen Discussion: This is one of many techniques used to solve a problem called reservoir sampling. We often encounter data sets that we'd like to sample elements from at random.