IIRC this is how fortune[1] selects a message fairly given the crappy database format it uses (possible fortunes are separated by lines containing just '%'
Algorithms Every Programmer Should Know: Reservoir Sampling
81–90 of 114 posts
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#82This algorithm was introduced with the premise > "I have a database table with #{17.kajillion} records, and I want to take a random sample of #{X} of them. How can I do this efficently?" And goes on to say that something like `YourBigTable.all.sample(X)` is bad in time and space. And the link that explains why doing `ORDER BY RANDOM()` is bad lists one reason being that generation of random numbers is relatively expe…
> But these problems aren't solved by reservoir sampling. Reservoir sampling is still O(N), and it requires generating a random number for every element. I had the same thought reading this. This solution is only really suitable if the number of elements to select is within some constant of the total number of elements. > More generally, reservoir sampling is appropriate when you don't know the size of the set before…
Could you please expand on your linked code, not really a C++ programmer and line 22/25 confuse me a bit?
Unfortunately I don't understand how each element has the same probability of being chosen. I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this?
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#831. Count N
2. compute p = n/N
3. select * from table where random()1) order by random() limit n
4. Repeat 3 until you got n rows
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#84FWIW, the pseudo-code in the Wikipedia article is easier to grok: http://en.wikipedia.org/wiki/Reservoir_sampling
I don't know... Can you really trust a wikipedia page that has needed attention from an expert for five years?
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#85Earlier quoted context omitted.
> But these problems aren't solved by reservoir sampling. Reservoir sampling is still O(N), and it requires generating a random number for every element. I had the same thought reading this. This solution is only really suitable if the number of elements to select is within some constant of the total number of elements. > More generally, reservoir sampling is appropriate when you don't know the size of the set before…
Could you please expand on your linked code, not really a C++ programmer and line 22/25 confuse me a bit? Unfortunately I don't understand how each element has the same probability of being chosen. I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this?
Regarding the C++ code:
/* This is standard modern C++ random number generation.
It means, using the random generator "engine", return
a number according to distribution "dist". In this
"dist" is a uniform distribution from "i" to "max-min".
"auto" is the new way to type variables in C++: it
infers the type of the variable from the type of the
expression */
22: auto index = dist(engine);
/* The following lines are a bit more complex, as they
contain a nested expression. Let us focus on the inner
expression:
(index second
This is in the form:
test-expr ? when-true-expr
: when-false-expr
This expression is a ternary condition. What it means
is that the expression before the question mark is
computed (index second);
/* Then, the std::swap operation simply swaps the two indicated
values in the array. */Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#86Earlier quoted context omitted.
Thanks for the clarification, thats exactly what I was wondering about. I have two questions: - is it a common problem to have, not knowing the set size? - is it O(N), or rather O(n)? My intuition tells me it depends on whether or not I have to retrieve every record in the set or not, because I/O should still be much more expensive than random number generation.
Imagine you are writing software to sit on a router to: 1) collect data for some length of time, and 2) thereafter have available for querying the (maybe approximate) 25th, 50th, 95th, and 99th percentile TCP connection bandwidth thresholds, and 3) signal when a connection grows beyond the 95th percentile. You only have a fairly limited amount of memory.
While it's great for medians, reservoir sampling for calculating high or low percentiles, particularly with high dynamic range data, will probably have very high error.
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#87Earlier quoted context omitted.
> But these problems aren't solved by reservoir sampling. Reservoir sampling is still O(N), and it requires generating a random number for every element. I had the same thought reading this. This solution is only really suitable if the number of elements to select is within some constant of the total number of elements. > More generally, reservoir sampling is appropriate when you don't know the size of the set before…
Could you please expand on your linked code, not really a C++ programmer and line 22/25 confuse me a bit? Unfortunately I don't understand how each element has the same probability of being chosen. I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this?
> Could you please expand on your linked code, not really a C++ programmer and line 22/25 confuse me a bit?
I've annotated the program here: http://ideone.com/gmaBri
> Unfortunately I don't understand how each element has the same probability of being chosen. I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this?
This is just a partial Fisher-Yates shuffle[1] using a sparse sequence instead of an array. Keep in mind that if an element is not chosen it is swapped with the chosen element and will be considered again. I think the best way to think about it is that you are choosing a random element from the set and then "removing" it from the set with the swap and then repeating.
[1] http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Th...
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#88Is there a pointer to the other algorithms?
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#89This algorithm was introduced with the premise > "I have a database table with #{17.kajillion} records, and I want to take a random sample of #{X} of them. How can I do this efficently?" And goes on to say that something like `YourBigTable.all.sample(X)` is bad in time and space. And the link that explains why doing `ORDER BY RANDOM()` is bad lists one reason being that generation of random numbers is relatively expe…
one reason being that generation of random numbers is relatively expensive
Say again? My laptop can read from /dev/urandom at over 1 Gbps. If you're running in userland on modern hardware you can easily hit 10 Gbps.
Seeding is hard, but once you've done that, generating random numbers is insanely cheap.
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#90Just looking at the comments, I think their is a tacit assumption on the part of some commenters that a stream of unordered records from a database has a random distribution relative to the value you care about. That is almost never true. In fact, I have seen clever performance optimizations in database applications that exploit I/O scheduler and layout induced bias in index-less record order. In practice, sampling 2…
Does this matter for this example? It scans every single record, and adds it to the output with a certain probability. The ordering of the original stream doesn't matter I think.