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

121–130 of 200 posts

Re: Algorithm No One Knows About (2016)

#121

Post by pbnjay »

SilasX wrote: post #118
jasonshaev wrote: post #117

Earlier quoted context omitted.

This is a bad take and odd place to criticize Go programmers. Go convention is often short variable names, but the only place I know where single-letter variable names is encourage is for receiver methods. https://golang.org/doc/effective_go.html#methods In that case the definition of the single-letter variable is literally a line or two of code away.

So is HN a good place to ask, and if so, are you able to find a perspicuous example highlighting the superior code quality?

The receiver name is likely to be used within the method, and always defined at the top of the block (and recommended to be consistent across all of the receiver's method definitions). So locality and consistency are great, improving the readability of the code.

Names like "self" and "this" proscribed by other languages begin to have issues when you start dealing with nested definitions and closures. Allowing them to be explicitly named in Go avoids these ambiguities.

Re: Algorithm No One Knows About (2016)

#122

Post by ChrisLomont »

Dylan16807 wrote: post #30

Okay, so this is a way to generate a sampling in order, so you don't have to keep a sorted list and your run time can be k instead of klogk. Mostly. The body of the post, with its talk of strict timing and sample bias, had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n. If this algorithm hi…

>had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n

I can sample 1-6 in finite time by rolling a die. I suppose you mean given a RNG in range 1-2^n, you cannot get a sample range non-power-of-two in fixed time.

However, you can sample in finite time with probability as high as you like, since the likelihood of another roll falls off exponentially. So if the odds of your machine quantum tunneling into a star is p, then you can make an algorithm that does your sampling with fixed time T with probability more than 1-p, making it perfectly usable.

in practice, resampling rand takes very, very little time. I use it all the time for uniform [0,n) queries. The avg number of rolls is for the most part like 1.1 or less.

For example, to sample 0-9 given a 32 bit full period generator, since 2^32 mod 10 is 6, only in 6 cases out of 2^32 cases do you need a second roll. This is common.

Re: Algorithm No One Knows About (2016)

#123

Post by klingonopera »

reggieband wrote: post #98
klingonopera wrote: post #67

Earlier quoted context omitted.

I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above... ...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...

Fisher-Yates [1] algorithm is proven to "produce an unbiased permutation: every permutation is equally likely". Additionally, "The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place." [1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

According to examples in the English Wikipedia, the method I described above is actually the Fisher-Yates method (and its naive implementation, and thus the O(n²) complexity), and the swapping method on everyone's minds was actually Durstenfeld's (optimization?), with O(n).

The initial code snippet intended to be Durstenfeld was erroneously an off-by-one Sattolo implementation, which then further solidifyed my suspicion that it had a bias, which Sattolo's implementation actually indeed has. The Durstenfeld method is however proven to be unbiased.

To add further confusion to the names in the issue, though some readers might not be able to verify due to the language barrier, the German Wiki states (claims?) Fisher-Yates is Durstenfeld's method with O(n), and the "naive" Fisher-Yates is labelled as the "direct" approach, with O(n²). The name Durstenfeld is not mentioned anywhere on the German Wiki. Though the names are different, the maths are the same in both English and German. I speak German and often read both versions of an article, in case anyone's wondering why I even brought up the topic.

Thank you for posting the link.

EDIT: I try not to post usernames in text, in case anyone ever changes their name.

EDIT2: I recommend to always positively increment an iterator from 0 to n-1, and use in-loop arithmetics to get the actual desired iterator/index you require. It's less performant, but I'd argue mistakes are less common.

Re: Algorithm No One Knows About (2016)

#125

Post by dzdt »

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 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 making it hard to compare the code to its specification.

Re: Algorithm No One Knows About (2016)

#126

Post by Someone »

”Here’s a program roughly 0% of programmers know how to write: generate a list of random tweets, without duplication.

[…]

Stated more formally: given non-negative integers k and n with k , generate a list of k distinct random numbers, each less than n.“

I think that knowing k beforehand makes it a different, easier problem. I don’t see how, if you don’t know k beforehand, you can do without enough memory to store a number of magnitude n!, and even that would be extremely slow, the more items you have to produce (uniformly pick a permutation of n items, and produce as many of them as requested)

Re: Algorithm No One Knows About (2016)

#127

Post by aidenn0 »

drfuchs wrote: post #47

A bunch of comments here are missing the main point: Unless you have an Exabyte of memory, you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them. The goal here is an algorithm that generates the selected cards, one by one, in order, as if from a coroutine that only uses a tiny, constant amount of memory. So, no arrays, lists, sets, hash tables, bitmaps, etc., even i…

If you can store 2^64 data points, why cant you store 2^63 indexes? That's a very small increase in memory requirements.

Re: Algorithm No One Knows About (2016)

#128

Post by Mathnerd314 »

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 and j are index variables for the array used to return the sample, introduced by the blogpost.

I'm not saying it's good code, but BLAS is similar: https://github.com/Reference-LAPACK/lapack/blob/master/BLAS/.... At some point working code beats comprehensibility.

Re: Algorithm No One Knows About (2016)

#129

Post by SilasX »

pbnjay wrote: post #121
SilasX wrote: post #118

Earlier quoted context omitted.

So is HN a good place to ask, and if so, are you able to find a perspicuous example highlighting the superior code quality?

The receiver name is likely to be used within the method, and always defined at the top of the block (and recommended to be consistent across all of the receiver's method definitions). So locality and consistency are great, improving the readability of the code. Names like "self" and "this" proscribed by other languages begin to have issues when you start dealing with nested definitions and closures. Allowing them to…

The distinction isn't against protected words, but against more descriptive names (like "buffer" or "receiver"), and the issue is more complex functions, not one-liners.

Anyway, didn't mean to put you on the spot, since you don't speak for Go programmers and weren't planning to justify the argument, I just wanted to clarify why these wouldn't satisfy the challenge.

Re: Algorithm No One Knows About (2016)

#130

Post by vardump »

dahfizz wrote: post #90
OscarCunningham wrote: post #2

>The misleading part in using the language of cards is that you don’t often consider a deck of size 2^64. What’s nice about the card formulation though is that it conveys how simple the problem statement really is. This is a fundamental problem that was open for a long time. Nobody knew how to deal cards. >The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. I…

This solution requires storing the 2^63 cards you have picked. That's impossible to do today.

It would take a lot of storage, but it's not impossible. 2^64 bits equals 2097152 terabytes. A lot, but doable with modern technology. I guess for $100-200M.
Post reply on HN