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.

Depends on your use case. Generating random numbers is indeed relatively expensive:

    $ time dd if=/dev/zero of=/dev/null bs=1024 count=1M
    1073741824 bytes (1.1 GB) copied, 0.348118 s, 3.1 GB/s
    real    0m0.350s
    user    0m0.092s
    sys     0m0.260s

    $ time dd if=/dev/urandom of=/dev/null bs=1024 count=1M
    1073741824 bytes (1.1 GB) copied, 102.332 s, 10.5 MB/s
    real    1m42.334s
    user    0m0.152s
    sys     1m41.994s

(fyi, Dr. Colin Percival is an eminent security developer for FreeBSD, author and CEO of the trusted Tarsnap, and developer of the AWS AMI's for FreeBSD; when he takes a whack at Linux's PRNG, he's got some standing to do it from :).)

But, yep, this is normal for Linux.. although, frankly, I'm just glad that we, like FreeBSD, are not taking rdrand at face value (thx Ted T'so!) Perhaps post-seed performance will improve down the road.

The inner loop of a PRNG microbenchmark should be identical to the inner loop of an AES-CTR microbenchmark (or your favourite block cipher or MAC if you prefer a different one) and those are fast these days.

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 beforehand. But in the premise, we do know the size of the set. And if you know the size of the set (and have some way to address arbitrary elements), then randomly generating a set of X indices is going to be much simpler and faster. Yeah, you have to deal with duplicate indices, but that's an easy problem to solve.

Last time I had to solve this, I came up with the following solution[1] which doesn't generate any duplicates and runs in O(k) where k is the size of result set.

[1] http://ideone.com/CAwuxW

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.

It seems less, not more, likely that this kind of situation would exist in a huge table - what use would such a table be if you could only process it sequentially?

A sufficiently smart database might understand "order by rand() limit n" and do reservoir sampling on row id's behind the scenes. I wouldn't count on it, though.

If you set it up in advance, you could also use reservoir sampling to avoid even storing all the data in the first place, while still saving a random sample.

In fact, i think this is the underlying meme of 'big data' - that it's now plausible and useful to do analysis over all of a large dataset, so you might as well build everything around iterating over the entire table regardless.

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 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 < size ) ? array[index]
              : map.insert({index, min + index}).first->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 < size), and if it evaluates to true,
       the overall expression will resolve to the result of
       the expression between the question mark and the colon,
       otherwise it resolves to what is after the colon.

       Here, it means that if "index" is smaller than "size",
       use "array[index]", otherwise insert a new entry in the
       map, with key "index" and value "min+index", then reuse
       the result of the operation by accessing member "second"
       of the member "first". I am not familiar with STL maps;
       here is an explanation of the map::insert method from
       cplusplus.com:

           The single element versions (1) return a pair, with
           its member pair::first set to an iterator pointing 
           to either the newly inserted element or to the 
           element with an equivalent key in the map. The 
           pair::second element in the pair is set to true if 
           a new element was inserted or false if an equivalent
           key already existed.
    */

    23: std::swap(array[i], index < size
    24:                         ? array[index]
    25:                         : map.insert({index, min + index}).first->second);

    /* Then, the std::swap operation simply swaps the two indicated
       values in the array. */

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...

Yes, reservoir sampling is O(N), but my point there was that it doesn't require instantiating every record at once. Also, the cost of the random number generation isn't the big deal in an ORDER BY RANDOM() implementation -- it's that even the smart implementations end up doing multiple table scans. So even at O(n) this probably beats most implementations of that approach, in practice.

Reservoir sampling is appropriate with more than just a set of unknown size -- you very frequently know the size of a set, but it's still too big to sample directly. But yes, if your sets are small, you have a lot of options.

You can make a better approach using a much longer list, but then the math is far less elegant. EX: Add the first X * N elements to the list. Then remove 1/X of them. Then 1/X of the times add an element to the list until it’s full. Cull 1/X of them and then add new elements (1/X)^2 of the time. Repeat until you run out of elements at which point you cull the list back to X elements.

Downside is your generating ~N log N random numbers so scanning the list and then sorting a random set may be faster.

If you have an approximate number elements AND want a small percentage of them then randomly generate X * N element list which is then culled to an N element list.

Finally, if N happens to be close to the full number of elements you’re better off creating an exclusion list.

PS: Reservoir Sampling is only good if your memory constrained, need a constant time algorithm, and generating random numbers is expensive.

Offhand I'm not sure how to do that in SQL, since data isn't usually fetched by index (unless the row has an explicit index key). Worst-case you could iterate over the rows just as you do with reservoir sampling, and it would still be faster (since you aren't generating tons of random numbers and doing a lot of array manipulation). Or you could do one query fetching just the primary key, record the keys of the indices you're interested in, and then do a second query to fetch that set. Or maybe SQL does have some way to fetch by index after all.

If you have an integral primary key, you could select its max and generate random numbers up to that. Continuity isn't guaranteed so you would need to check for nonexistent primary keys in addition to checking for duplicates.

If there's no integral primary key, then there's no standard SQL solution faster than O(n).

  let count = query("SELECT COUNT() FROM table")
  let indices = computeIndices(count, k)
  for index in indices {
    results.append(query("SELECT * FROM table LIMIT 1 OFFSET ?", index))
  }

Also, do you have any citation for OFFSET j being O(j)? I can believe that's the case, but it also seems fairly obvious to optimize OFFSET for the case of a non-filtered unordered SELECT (or one ordered in a way that matches an index).

Can anyone comment on why this reservoir method would be a better choice than the old fashioned systematic sample? (which, BTW, only requires the generation of one random number to determine the starting record).

I'm not sure that I buy this...Do you have an example? Still, it is a neat algorithm. And it is a true stream query algorithm, that is, if you have an open-ended stream, it maintains a random sample at all times.

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 multiple machines. In these cases, you need an approach suitable for when you don't know the size of the stream, you can't load it all into memory and/or you can't select randomly from an address pool.

>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

isn't the movement of such data -- when you have billions of rows simply impossible in reasonable time?

(find_each instantiates a few records at a time, then throws them away)

There's also another, less-known variant of this algorithm that I'll go into in a future post that alleviates the concern.

- 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.

Yes. It could be as simple as receiving values from a Python generator (or equivalent mechanism in your favourite language), where you don't know the number of items beforehand (and querying for the length is either impossible or expensive).

In such a cases, using reservoir sampling is an elegant solution, because you're probably in a situation where you'll be iterating through all values anyway.

One motivating case is when the items arrive over time, like you have a website and you want to sample uniformly from your visitors over the course of the next hour. You don't need to know how many people will arrive.

I agree with your comment in general. Only: you can do better than generate a random number for each element. (Generate a random number to tell you how many elements in the steam to skip.)

That should work if you pull the skip count from the appropriate distribution (negative binomial, I think).

Let's keep this going.

Resist commenting about being downvoted. It never does any good, and it makes boring reading.

Please don't bait other users by inviting them to downvote you.