4 ms·

The core problem with Reservoir sampling is the huge number of calls to the random number generator. That quickly drains the entropy from PRNGs. Also, for som

The core problem with Reservoir sampling is the huge number of calls to the random number generator. That quickly drains the entropy from PRNGs. Also, for some sampling applications, the calls to the PRNG are the slowest part of the algorithm. So, you should prefer an algorithm that makes the fewest possible number of calls. Lastly, you should take care in how the algorithm is implemented. For example, if the PRNG yields consecutive 32-bit values, computing randbits modulo n leads to small selection biases whenever n doesn't evenly divide 2^32. There are a lot of ways around this problem, but naive implementations won't give equi-distributed results. For the most part, you should choose some other sampling algorithm unless you have exotic needs: not knowing the population size until you loop over it, AND not caring about the huge number of calls to the PRNG, AND having a limitless supply of entropy for your PRNG, AND having an easy means of getting equidistributed values in range of 0 to n-1, OR the quality of your results isn't important.

deleted 13y ago
[deleted]
tomp 13y ago
Another way would be to simply calculate hash(prefix + obj) and then choose the object with lowest hash value. You can use a GPU-fast hash like sha2, and you can even paralelize it. It's not guaranteed to be evenly distributed, but I think it would be close enough for most purposes.
- noelwelsh 13y ago
  Ingenious! This should work -- the uniform distribution property of hash functions is relied upon very heavily by other streaming algorithms such as HyperLogLog, and there has been sound empirical evaluation by the guys at Aggregate Knowledge of the properties of various hash functions: http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/ http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo... (Dunno why you include a prefix in the calculation above. hash(obj) should be sufficient.)
  - joosters 13y ago
    You need the prefix because without it, you will end up picking the same object every time you run the algorithm (e.g. On the next day's stream of data) Depends, of course, upon the size of the stream and the range in variety of the objects in the stream.A stream of bytes would not be a good use case, for example.
jrabone 13y ago
Sounds like the sort of problem the Mersenne Twister PRNG is good for.
yxhuvud 13y ago
I don't understand why you would need many calls to random. Are there any obvious reasons it wouldn't suffice to get one random number and then reuse it throughout the stream?
- tantalor 13y ago
  Looks like that doesn't work, https://gist.github.com/tantalor/5911137 https://gist.github.com/tantalor/5911137 The distribution ends up weighted towards the front with a spike at the end. Looks like this: https://docs.google.com/spreadsheet/oimg?key=0AhzL62E3zw7-dGhpemVRcE1zVlhoVnBpbDNjS2NKclE&oid=1&zx=tj3bijabnb4f https://docs.google.com/spreadsheet/oimg?key=0AhzL62E3zw7-dG...
joe_the_user 13y ago
Another thing about the algorithm and article is, this is supposed to be a "real world problem" that the interviewer asks because they're struggling with it themselves. But what would a single randomly chosen item from a huge set mean to "real world" operations? That you would very occasionally get a very usual value? - You'd have to run the scan many times for that and whatever other thing you were thinking of. Basically, the algorithm is "cool exercise in probability" that any deeper look will discover has just about zero use or practicality in the actual "real world". Which kind of throws into the zone of obnoxious interview brain teasers despite claims to the contrary.
- stouset 13y ago
  Not at all. The exercise is trivially extended to allow for selecting 1,000 or 1,000,000 items from the set. This can be useful if you want a reprsentative sample from the stream, but require a well-defined and limited number of samples.
- gizmo686 13y ago
  The problem was supposed to be based off of a real world problem. Almost always, when you simplify a problem you have to its core, you end up with a very simple question that appears to have no practical applications. Normally, this simple question is also easy, in which case simplifing it is the only skill you need. In other cases this question is hard, in which case you need to be able to solve it. Both of these skills are valuable, but should not be tested in the same question. Also, if you are trying to pick a candidate's brains, their is no reason to make them redo your work of simplification, when you are stuck on the actual problem.
wtbob 13y ago
> That quickly drains the entropy from PRNGs. If you're worrying about the entropy in your PRNG, you are (probably) doing it wrong—just use Fortuna and be done with it. > Also, for some sampling applications, the calls to the PRNG are the slowest part of the algorithm. That's a valid concern. Of course, how often do you need cryptographic security and performance in a sampling application?
gizmo686 13y ago
Is there any reseason you couldn't use a fast psuedo random number generator? Even so, you are processing a stream of data, sounds like an easy place to get entropy.

deleted 13y ago

[deleted]

tomp 13y ago

Another way would be to simply calculate hash(prefix + obj) and then choose the object with lowest hash value. You can use a GPU-fast hash like sha2, and you can even paralelize it. It's not guaranteed to be evenly distributed, but I think it would be close enough for most purposes.

noelwelsh 13y ago
Ingenious! This should work -- the uniform distribution property of hash functions is relied upon very heavily by other streaming algorithms such as HyperLogLog, and there has been sound empirical evaluation by the guys at Aggregate Knowledge of the properties of various hash functions: http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/ http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo... (Dunno why you include a prefix in the calculation above. hash(obj) should be sufficient.)
- joosters 13y ago
  You need the prefix because without it, you will end up picking the same object every time you run the algorithm (e.g. On the next day's stream of data) Depends, of course, upon the size of the stream and the range in variety of the objects in the stream.A stream of bytes would not be a good use case, for example.

jrabone 13y ago

Sounds like the sort of problem the Mersenne Twister PRNG is good for.

yxhuvud 13y ago

I don't understand why you would need many calls to random. Are there any obvious reasons it wouldn't suffice to get one random number and then reuse it throughout the stream?

tantalor 13y ago
Looks like that doesn't work, https://gist.github.com/tantalor/5911137 https://gist.github.com/tantalor/5911137 The distribution ends up weighted towards the front with a spike at the end. Looks like this: https://docs.google.com/spreadsheet/oimg?key=0AhzL62E3zw7-dGhpemVRcE1zVlhoVnBpbDNjS2NKclE&oid=1&zx=tj3bijabnb4f https://docs.google.com/spreadsheet/oimg?key=0AhzL62E3zw7-dG...

joe_the_user 13y ago

Another thing about the algorithm and article is, this is supposed to be a "real world problem" that the interviewer asks because they're struggling with it themselves. But what would a single randomly chosen item from a huge set mean to "real world" operations? That you would very occasionally get a very usual value? - You'd have to run the scan many times for that and whatever other thing you were thinking of. Basically, the algorithm is "cool exercise in probability" that any deeper look will discover has just about zero use or practicality in the actual "real world". Which kind of throws into the zone of obnoxious interview brain teasers despite claims to the contrary.

stouset 13y ago
Not at all. The exercise is trivially extended to allow for selecting 1,000 or 1,000,000 items from the set. This can be useful if you want a reprsentative sample from the stream, but require a well-defined and limited number of samples.
gizmo686 13y ago
The problem was supposed to be based off of a real world problem. Almost always, when you simplify a problem you have to its core, you end up with a very simple question that appears to have no practical applications. Normally, this simple question is also easy, in which case simplifing it is the only skill you need. In other cases this question is hard, in which case you need to be able to solve it. Both of these skills are valuable, but should not be tested in the same question. Also, if you are trying to pick a candidate's brains, their is no reason to make them redo your work of simplification, when you are stuck on the actual problem.

wtbob 13y ago

> That quickly drains the entropy from PRNGs. If you're worrying about the entropy in your PRNG, you are (probably) doing it wrong—just use Fortuna and be done with it. > Also, for some sampling applications, the calls to the PRNG are the slowest part of the algorithm. That's a valid concern. Of course, how often do you need cryptographic security and performance in a sampling application?

gizmo686 13y ago

Is there any reseason you couldn't use a fast psuedo random number generator? Even so, you are processing a stream of data, sounds like an easy place to get entropy.