Algorithms Every Data Scientist Should Know: Reservoir Sampling
blog.cloudera.com
blog.cloudera.com
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.
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.)
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.
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-dG...
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.
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.
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?
Even so, you are processing a stream of data, sounds like an easy place to get entropy.
I've since learned there are many other interesting sampling algorithms that apply in a streaming setting. A few are give here: http://people.cs.umass.edu/~mcgregor/slides/10-jhu1.pdf
rand($.) < 1 && ($line = $_) while <>;
<> is a common way to read stdin, and the value is assigned to the $_ special variable.
The one I didn't know was $., the current input line number. In other words, its your loop index that automatically increments.
Given the article's windup, I'd be a bit skeptical of the naive solution - at input n, with probability 1/n replace the current choice.
Once you've reached input number 10^8 or whatever, you've got all sorts of chances to have arithmetic overflow and/or the weirdness of that many pseudo-random operations screw you.
I'd rather keep a list of x's; let x1 be randomly chosen from the last 10, x2 randomly chosen from the last 100, x3 random chosen from the last 1000, etc and when termination time come do a little fixup. That'd take O(log(n)) memory instead of O(1) but if this matters, shouldn't you want some sample of what's happening?
There's some complications if the sample is not a power of two (or whatever number of elements you picked for each level). Essentially though, you know the number of elements at that point though, and you can weight the probability of selection so that the winner has exactly 1/N probability of having been selected.
[1] You always need at least one bit. After the first, each additional bit divides the space in which 1/n can lie in half, so it's just 1 + (1/2 + 1/2(1/2 + 1/2(...))) = 1+1/2+1/4+... = 2. It's a lot like arithmetic coding[3]
[2] http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b...
Not that I have any knowledge any given pseudo-random number generator would trouble with long series's of zeros. Still, scheme I had in my parent post was aiming to avoid potential problems with that kind of thing.
Why? Double floats don't overflow until 10^-300 or so, and RNG's give uniform numbers from 0 to 1 just fine...
Maybe that's why I'm not so enthusiastic about it as an interview question? ;)
More seriously - I do think that questions with specific optimal answers (or at least known answers that are considerably better than simple greedy solutions) can be good interview questions, as long as they contain a big middle, with plenty of opportunity to think about the problem and show some good problem solving skills.
Questions where you know the answer or don't are probably the worst. Questions where you get the right answer or you get nowhere aren't great either. Questions where you can get a good answer by thinking about it, even if you don't get the most optimal answer, are probably best.
Another good way to approach this would be this: how much would an interviewee/candidate's performance change if he or she were allowed to type "how to randomly sample from a list of unknown length" into google. If that would make a huge difference, then it probably isn't a great question unless you're really testing to see if someone is already aware of an algorithm.
Some other similar logic - Selecting n distinct items out of N, all C(N,n) selections being equally likely, passing through the data only once :)
And the next step - if the data can be accessed randomly, the above can be done in O(n) time instead of O(N) through a modification of the algo, still giving a statistically equivalent sampling scheme.
For example, many CS grads don't have strong stats/maths backgrounds. However there are still many "data science" jobs open to them. For example, you can work on the tooling that goes into storing and processing data (e.g. Hadoop), or you can build visualisations. If you want to work on, say, data analysis you need to have a stronger background in stats.
Where I did my PhD (the top ranked CS department in the UK by a recent survey) the undergrad students did one maths courses in their entire degree, with most of it being discrete maths (IIRC). This really limited the ability of students to undertake research in machine learning or theoretical CS.
Nice to see brummies on hacker news. Since your start up guy, I guess you hang around faraday wharf?
The systems are archaic. By that I mean both the implementation platform, and the people who you will sell your solution to. To most of the senior stuff this is new and mysterious - they would rather "play safe", and may ask you instead to use traditional methods, put "intuitive" variables, and keep the solution "simple" (simple being anything that they already know of, from their past 10-20 years of experience).
But things are changing. In my farm too. And if you interview now as a data scientist, you will probably be given the right respect - and put into a team where the leaders may want people like you.
And you will be one of very few in the company who knows what this stuff is, rather than myriads who know how to model using the company's already setup platform - which you will prove to be inferior. You may have to push the boundaries of the company for it, and you will pave the way. But you will also be welcome - as the realization now dawns upon corporates that there may be better ways of doing what they have been doing.
Also you will not be alone. You will find some smart people in the company you join soon. They will challenge you, be your friends. You will learn and think about things that you have not before... as will you intrigue others to think of things that they haven't before.
So go for it. Try it out. It's easy money.