Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithms Every Programmer Should Know: Reservoir Sampling

omniref.com

Post reply on HN
Print view View original

111–114 of 114 posts

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#111

Post by shoegumfoot »

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?

> Can you show that [generating a number of records to skip instead of a yes/no for each record] will still maintain a uniform probability distribution?

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

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#112

Post by eru »

shoegumfoot wrote: post #111
alok-g wrote: post #103

Earlier quoted context omitted.

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

> Can you show that [generating a number of records to skip instead of a yes/no for each record] will still maintain a uniform probability distribution? That should work if you pull the skip count from the appropriate distribution (negative binomial, I think).

Yes, you have to work out the right distribution, and how to sample from it (at all, and perhaps how to sample from it efficiently).

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#113

Post by jamiesonbecker »

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?

btw, your sly remark wasn't lost .. ;)

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

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#114

Post by cperciva »

jamiesonbecker wrote: post #113
cperciva wrote: post #106

Earlier quoted context omitted.

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

btw, your sly remark wasn't lost .. ;) (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!) P…

I wasn't talking about RDRAND. I can't remember what throughput it gives, and it's a pain to use "live" in that it's allowed to fail and return all zeroes.

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.

Post reply on HN