Algorithms Every Programmer Should Know: Reservoir Sampling • Hacker News Board

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#101

Post by twic » Sat, Mar 07, 2015, 2:47 PM UTC

joe_the_user wrote: post #52

timr wrote: post #42

Earlier quoted context omitted.

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.

Another way to put it is that reservoir sampling only makes sense if you have to iterate over the entire table regardless. That means, no keys, row numbers or unique values that can chosen at random and found more quickly. 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?

Once-through sequential processing is a pretty common paradigm for large datasets. That's basically what Hadoop and column stores are about.

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.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#102

Post by jamiesonbecker » Sat, Mar 07, 2015, 3:06 PM UTC

cperciva wrote: post #89

eridius wrote: post #5

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…

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.

> 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

(I7, 3.2.0-4-amd64)

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#103

Post by alok-g » Sat, Mar 07, 2015, 4:25 PM UTC

eru wrote: post #98

eridius wrote: post #5

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…

> Reservoir sampling is still O(N), and it requires generating a random number for every element. 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.)

Can you show that this will still maintain a uniform probability distribution?

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#104

Post by IgorPartola » Sat, Mar 07, 2015, 7:11 PM UTC

jamiesonbecker wrote: post #102

cperciva wrote: post #89

Earlier quoted context omitted.

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.

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

You are comparing doing nearly nothing vs an PRNG. Presumably, you would spend your computation cycles doing something more useful than generating zeros, at which point I am not certain the difference would be quite so drastic.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#105

Post by taltman1 » Sat, Mar 07, 2015, 7:58 PM UTC

Reservoir sampling in a few lines of awk:

https://github.com/taltman/scripts/blob/master/EDA/samp

It's shorter than this ruby implementation, and includes copious documentation, file handling, and corner-case support.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#106

Post by cperciva » Sat, Mar 07, 2015, 11:42 PM UTC

jamiesonbecker wrote: post #102

cperciva wrote: post #89

Earlier quoted context omitted.

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.

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

Your /dev/urandom is astonishingly slow. Is this normal for Linux?

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#107

Post by eridius » Sun, Mar 08, 2015, 1:02 AM UTC

dbenhur wrote: post #93

eridius wrote: post #70

Earlier quoted context omitted.

If N is sufficiently larger than k, it might actually be faster to do something like 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)) } Yeah, you're doing a bunch of queries, but you're removing all of copying all the data from all the rows.

OFFSET j is O(j) in most RDMSes. You made an o(N/2 * k) algorithm given j is a random number in [0,N).

Depending on the size of k compared to N, and how much data is in each row, it's still probably better than iterating over the entire contents of the table.

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

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#108

Post by detrino » Sun, Mar 08, 2015, 2:06 AM UTC

eridius wrote: post #107

dbenhur wrote: post #93

Earlier quoted context omitted.

OFFSET j is O(j) in most RDMSes. You made an o(N/2 * k) algorithm given j is a random number in [0,N).

Depending on the size of k compared to N, and how much data is in each row, it's still probably better than iterating over the entire contents of the table. 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).

Assuming that the DB is backed by some kind of tree, it would need to maintain extra metadata in the branches in order to achieve even O(log n) offsetting. For this reason I could understand it being a linear operation.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#109

Post by eru » Sun, Mar 08, 2015, 5:25 AM UTC

alok-g wrote: post #103

eru wrote: post #98

Earlier quoted context omitted.

> Reservoir sampling is still O(N), and it requires generating a random number for every element. 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.)

Can you show that this will still maintain a uniform probability distribution?

Yes.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#110

Post by SamReidHughes » Sun, Mar 08, 2015, 2:47 PM UTC

cperciva wrote: post #106

jamiesonbecker wrote: post #102

Earlier quoted context omitted.

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

Your /dev/urandom is astonishingly slow. Is this normal for Linux?

Yes. For example, if you choose the encrypted hard drive option when installing Debian, it'll take forever, like, hours and hours, two digit numbers of hours, because it's reading from some /dev/urandom (I presume) to initialize the drive with random data. You can skip that step though. It's way better to do it beforehand using some script that uses something other than /dev/urandom. And maybe, don't put a 1 TB hard drive in a netbook or an older machine.