To retrieve k random numbers from an array of undetermined size we use a technique called reservoir sampling. Can anybody briefly highlight how it happens with a sample code?
-
This page contains a good explanation with pseudo-code. (The Wikipedia page I originally linked to is unclear, and the pseudo-code is incomplete.)– Stephen CApr 10, 2010 at 7:57
-
1I wrote a blog entry about the exact thing a couple of months back, which has a C# implementation: gregbeech.com/blog/sampling-very-large-sequences The best description of how it works that I've found is here: gregable.com/2007/10/reservoir-sampling.html– Greg BeechApr 10, 2010 at 8:13
-
Related question stackoverflow.com/questions/54059/…– Ian MercerApr 11, 2010 at 6:11
Add a comment
|
4 Answers
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
With a proof near the end.
-
@Larry: Where is the
accept it with probability s/k
part in your code? [ quote from algorithm mentioned at blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx ]– LazerApr 11, 2010 at 10:26 -
By coincidence, it seems like between that article and mine, we use the same variables, but for different things. My "K" appears to be their "S", and my "N" (in code) appears to be their "K". In other words, I accept things with
K/N
probability, where N is the current count of things.– LarryApr 11, 2010 at 16:14 -
what I meant to ask was how you were implementing probability in your code. Anyways, now I understand. Thanks!– LazerApr 12, 2010 at 3:11
-
Not quite understanding your question, but I can explain the code a little more if you are specific! =)– LarryApr 12, 2010 at 4:31
-
Thanks. This is super easy to understand and get started with basics.– GopinathMay 13, 2016 at 19:08
Following Knuth's (1981) description more closely, Reservoir Sampling (Algorithm R) could be implemented as follows:
import random
def sample(iterable, n):
"""
Returns @param n random items from @param iterable.
"""
reservoir = []
for t, item in enumerate(iterable):
if t < n:
reservoir.append(item)
else:
m = random.randint(0,t)
if m < n:
reservoir[m] = item
return reservoir
-
What's the difference between this and the accepted answer? I think this is exactly the same thing, even if this code is more elegant. May 10, 2017 at 13:09
-
1It can be directly related to published research (Knuth, 1981), in case someone is interested in more extended explanation or Knuth's proof.– samSep 25, 2017 at 9:33
-
-
-
1@user76284 Correct, and it should be. Let
iterable
contain 11 items from which we want to samplen
=10. For the 11th item,t
will be 10 (becauseenumerate
starts at 0), and we generate a random integer between 0 and 10 inclusive (i.e., 11 possibilities) such that the probability of adding the 11th item toreservoir
is n/t = 10/11.– samNov 7, 2020 at 9:46
Java
import java.util.Random;
public static void reservoir(String filename,String[] list)
{
File f = new File(filename);
BufferedReader b = new BufferedReader(new FileReader(f));
String l;
int c = 0, r;
Random g = new Random();
while((l = b.readLine()) != null)
{
if (c < list.length)
r = c++;
else
r = g.nextInt(++c);
if (r < list.length)
list[r] = l;
b.close();}
}
Python solution
import random
class RESERVOIR_SAMPLING():
def __init__(self, k=1000):
self.reservoir = []
self.k = k
self.nb_processed = 0
def add_to_reservoir(self, sample):
self.nb_processed +=1
if(self.k >= self.nb_processed):
self.reservoir.append(sample)
else:
#randint(a,b) gives a<=int<=b
j = random.randint(0,self.nb_processed-1)
if(j < k):
self.reservoir[j] = sample
k = 10
samples = [i for i in range(10)] * k
res = RESERVOIR_SAMPLING(k)
for sample in samples:
res.add_to_reservoir(sample)
print(res.reservoir)
out[1]: [9, 8, 4, 8, 3, 5, 1, 7, 0, 9]