Skip to main content
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output. See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ spaceChoosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$. See Wikipedia's description for details.

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output. See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$. See Wikipedia's description for details.

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output. See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$. See Wikipedia's description for details.

added 102 characters in body
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output. See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$. See Wikipedia's description for details.

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output.

This extends to arbitrary $k$. See Wikipedia's description for details.

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output. See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$. See Wikipedia's description for details.

Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output.

This extends to arbitrary $k$. See Wikipedia's description for details.