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

Algorithm No One Knows About (2016)

getkerf.wordpress.com

Post reply on HN
Print view View original

161–170 of 200 posts

Re: Algorithm No One Knows About (2016)

#161

Post by nemetroid »

lonelappde wrote: post #138
dzdt wrote: post #125

Earlier quoted context omitted.

The reason for naming the variables as they are seems to be to keep consistency with Vitter's paper [ http://www.ittc.ku.edu/~jsv/Papers/Vit87.RandomSampling.pdf ] Since the paper is really the primary documentation of the algorithm this makes perfect sense. Renaming the variables to be more meaningful to you would make it harder to compare to the paper, reducing the effectiveness of the paper as documentation and ma…

There's no reason to preserve bad notation from a 30year old paper.

Are you saying that single-letter variable names in maths is "bad notation"?

Re: Algorithm No One Knows About (2016)

#162

Post by svat »

supergarfield wrote: post #110
web007 wrote: post #79

Earlier quoted context omitted.

You select N from M, in order, where M is "too big" and N fits in memory / swap / disk. You then shuffle your N selections to get random ordering.

I understand "you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them" as "N cards don't fit in memory". Or is the relevant distinction memory vs disk, as it's feasible to randomize on-disk data?

The problem asks to find k cards (integers) out of n, in time O(k) and O(1) additional space — this means additional to the k required to store the output. So while holding n items wouldn't fit in memory, it is implicit that k would. But we still want to avoid Ω(k log k) time, or more than a constant amount of additional space.

Re: Algorithm No One Knows About (2016)

#164

Post by B1FF_PSUVM »

Mathnerd314 wrote: post #128
natch wrote: post #97

Some of the variable names used: i, j, t, qu1, S, n, N, U, X, y1, y2, V I know others have already commented on this but I think it's worth laying out all of the cryptic variables and asking: are some of these shorthand for well known math concepts that make it unnecessary to have a more descriptive name? I understand the use of temporary value holders like `i`, but have no clue what some of the others might be used…

The variable names are mostly from the paper, since the blog post mostly just transliterated the Pascal code in the appendix. Some of them are explained. n: sample size. N: file size / total record count. U,V: independent uniform variates. X: random variate approximating skip distance. S: skip distance. qu1: N-n+1. y1 and y2 aren't explained, they're just intermediate formulas. t seems to be a local loop variable. i…

> working code beats comprehensibility.

If you give long names to every variable, by the time you finish reading a line you forgot what they were doing.

Tolstoy novel problem.

Re: Algorithm No One Knows About (2016)

#165

Post by aasasd »

web007 wrote: post #79
OscarCunningham wrote: post #58

Earlier quoted context omitted.

Is there an easy way to adapt the algorithm to get the cards drawn in a random order? The article says "it’s easy to randomize the order after the fact" but if we can't store them in memory then that's a no-go.

You select N from M, in order, where M is "too big" and N fits in memory / swap / disk. You then shuffle your N selections to get random ordering.

Not sure that this qualifies as uniform distribution, even if you spread the N across the M. Because the selection must be predictable, so that any next N don't include the previous ones. That's presuming that the ‘user’ might iterate over M items in total, even if you pick chunks of N internally.

Re: Algorithm No One Knows About (2016)

#166

Post by thaumaturgy »

ghusbands wrote: post #61

The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.

Another good tool for this is the linear feedback shift register, and most programmers outside of crypto seem to be unaware of it too. A "complete" N-bit LFSR gives you 2^N non-repeating pseudorandom values. You start with some value (the seed), and feed it into your LFSR operation along with your chosen bitmask (the "taps"), and you get a difficult-to-predict value back out.

"Complete" LFSRs are created by carefully selecting your taps, and there's plenty of literature available for a broad range of taps for many different numbers of output bits.

Your cipher may have an LFSR buried somewhere in it, I guess they're a common component in crypto. (I know dick-all about crypto, mostly.)

Usual caveats for PRNGs apply: LFSRs are cool and magical and super fast, but the next number in the sequence can be computed by anyone else that can figure out your LFSR and seed, and since a complete LFSR will hit each value in 2^N exactly once per cycle, it doesn't even count as pseudorandom.

But, if you need a random-looking non-sequential non-repeating selection widget, an LFSR just might do the trick.

Re: Algorithm No One Knows About (2016)

#167

Post by dmurray »

debatem1 wrote: post #153
SAI_Peregrinus wrote: post #86

Earlier quoted context omitted.

Because we're restricted to O(1) extra space by the problem statement, regardless of the number of cards we're picking. We could be picking all 2^64, but definitely don't want the constant in O(1) to be 2^64!

O(1) /extra/ space, but we must have working space at least the size of the output.

The paper describes an online one-pass algorithm for which this is not true: as you get each input value you accept or reject it. So you only need O(1) space to store the number of values you've seen, the number remaining, and the number you still need to accept.

Re: Algorithm No One Knows About (2016)

#168

Post by Gene_Parmesan »

airstrike wrote: post #42
klingonopera wrote: post #9

Oh dear, I find those single-letter variable names are quite counter-productive in making the code easy for someone unfamiliar to the project to understand...

Yeah, I'm way out of my comfort zone here but I found the choice of n and N pretty off-putting

They are like that because they essentially transliterated the original Pascal code from the paper. Leaving the variable names as they were in the paper allows for the paper to act as documentation for the code, so to speak.

Re: Algorithm No One Knows About (2016)

#169

Post by dahart »

It’s called Reservoir Sampling https://en.wikipedia.org/wiki/Reservoir_sampling

I was just re-reading this yesterday! I think a lot of the Monte Carlo rendering people know about this family of algorithms, and the idea is pretty simple. I’m not sure why it’s described from the start as picking k samples though, I find it a lot easier to understand and see how it works when you start with k=1.

Btw, it’s fun to work out the probabilities of picking a sample to prove how this algorithm works, and that it’s uniform. Big piles of factorials that all cancel out.

Pps the other super rad algorithms that aren’t well knows are the alias method for simulating a discrete distribution https://en.wikipedia.org/wiki/Alias_method

...and the suffix array, which is crazy surprisingly useful https://en.wikipedia.org/wiki/Suffix_array

Re: Algorithm No One Knows About (2016)

#170

Post by dahart »

TheMerovingian wrote: post #106

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

It’s related to Fisher-Yates shuffle, https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to...

But it’s not the same thing. The difference is whether you can keep all samples in memory at the same time. With Vitter / reservoir sampling, you only need to have your reservoir in memory plus enough space for 1 new sample at a time, so you can stream through a large number of samples with a tiny amount of memory.

Post reply on HN