Algorithms Every Programmer Should Know: Reservoir Sampling

Post by eridius » Sat, Mar 07, 2015, 6:04 AM 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.

Post by dbenhur » Sat, Mar 07, 2015, 7:36 AM UTC

eridius wrote: post #70

dlubarov wrote: post #65

Earlier quoted context omitted.

Yeah - unfortunately there isn't a great way to select n random rows in standard SQL. 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).

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.

Post by damian2000 » Sat, Mar 07, 2015, 9:07 AM UTC

Post by namuol » Sat, Mar 07, 2015, 10:57 AM UTC

Post by eru » Sat, Mar 07, 2015, 1:05 PM UTC

jsprogrammer wrote: post #64

willvarfar wrote: post #59

I used to work on a hospital database, back before the internet. It happened a few times that we were asked for a random sample of records. It was quite common to want to recalculate the rehabilitation rates and other stats. This was a problem, as patient records filled several tapes and, being the youngster, I had to sit loading tapes for hours. Because our data set was bigger than memory, we had trouble deciding wh…

So the hospital was expecting random samples each time, but kept getting the same sample (with some appended records)?