41–50 of 114 posts
Earlier quoted context omitted.
Nicely put, sir/ma'am!
Downvoted for a compliment. Way to go HN, way to go.
This 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…
There are lots of cases where this assumption doesn't hold: if you're sampling from a join, or from a table with non-contiguous ID values, for example.
Earlier quoted context omitted.
Yes - the code is wrong. A correct implementation would adjust the probability of sampling based on how many items have been trialed. EDIT: I misread it as rand(n), rand(idx) is correct.
But that's happening here as well, right? The random number is an indexed picked between 0 and the current index. Though, I think there is an off-by one in this implementation (assuming that Ruby indexing starts at 0): j = rand(idx) out[j] = i if j Say that the index is n, it will call rand(n), which gives a random number [0..n). However, the index should be picked from [0..n].
That sounded right to me. I could be convinced otherwise.
Earlier 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…
As I said on another comment in this thread: if you have the addresses (i.e. database ID values) for all of your records in memory, then sure, sampling directly from that set is faster than iterating over every record in a table. There are lots of cases where this assumption doesn't hold: if you're sampling from a join, or from a table with non-contiguous ID values, for example.
Earlier quoted context omitted.
[deleted]
If you have N locations with known addresses and you can select a sample of k from those addresses randomly with uniform probability, then sure, do that. But there are lots of situations where you don't have that: say, you're sampling from a database join, or you're just using a table that has non-contiguous id values (e.g. a table with deletions). Or, in the case of truly "Big Data", you have the data spread over mu…
>Having a large input set of known size (and your result set is not large) is not a time when you would want to use reservoir sampling. Such a problem can be solved in O(k) where k is the size of the result set, while reservoir sampling is O(n) where n is the size of the input set.
and I have responded here: https://news.ycombinator.com/item?id=9158903
Earlier quoted context omitted.
But that's happening here as well, right? The random number is an indexed picked between 0 and the current index. Though, I think there is an off-by one in this implementation (assuming that Ruby indexing starts at 0): j = rand(idx) out[j] = i if j Say that the index is n, it will call rand(n), which gives a random number [0..n). However, the index should be picked from [0..n].
You may be right...I spent a lot of time thinking about that, and I convinced myself that this was correct, but I could be wrong. My thinking is that rand(N) in ruby returns a value from [0, N-1] inclusive, which is the complete index range of the sampled stream so far. That sounded right to me. I could be convinced otherwise.
Suppose that the sample size is 1 and you are getting the second item (index 1). You will call rand(1), which has 0 as the only possible outcome. So, you will always replace the first item (index 0). Whereas if you would call rand(2) (possible outcomes: 0 and 1), you replace the item in the sample with probability .5 (assuming that the random number generator is uniform).
I really like this algorithm, and I think it's instructive to think about a naive solution, and how it differs. Looping n times, calling rand(n) and putting the random element in the output. This mostly works, and is actually far better, in space and time, especially in the case where "putting the element in the output" is expensive (as is implied by the "kajillions of records" premise). The problem with this solutio…
Looping n times, calling rand(n) and putting the random element in the output. This mostly works, and is actually far better, in space and time, Reservoir sampling is normally used on large streams where you do not want to or cannot keep the data you are sampling from in memory.
Earlier quoted context omitted.
doesn't your implementation require you to fetch all data into the client process for ruby to iterate over? isn't the movement of such data -- when you have billions of rows simply impossible in reasonable time?
This implementation is useful at some scales, but not all: it uses find_each to iterate over the ActiveRecord scope, which is going to be slower than doing it all in the database (if that's possible), but still way better than instantiating every record in a large table. (find_each instantiates a few records at a time, then throws them away)
This 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…
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.
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.