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

51–60 of 200 posts

Re: Algorithm No One Knows About (2016)

#51

Post by fergie »

LolWolf wrote: post #29
fergie wrote: post #16

"(Stated more formally: given non-negative integers k and n with k "...it’s also possible to use the language of cards: deal k cards from a deck of size n, without replacement. So a poker hand like A2345 of clubs is valid for k=5 and n=52, but a hand containing AAAAA of clubs is not." These seem to be fairly straight forward problems to solve- can anybody ELI5 why the Vitter algorithm is necessary?

Probably the hardest things are the space and time requirements. If you relax e.g. the O(k) time requirement to O(k log k), the problem essentially becomes trivial.[1] More generally, though, what solution are you thinking of? (The problem, as stated, is actually fairly difficult! As far as I can tell...) --- [1] See: https://en.wikipedia.org/wiki/Coupon_collector's_problem . The solution is then to draw repeatedly a…

I see- in that case I need to read up on O(k) vs O(k log k)

Re: Algorithm No One Knows About (2016)

#52

Post by klingonopera »

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

A typo is only a (sticky) shift away, and not even obvious!

EDIT: ...and compiles, too!

Re: Algorithm No One Knows About (2016)

#53

Post by petters »

andreareina wrote: post #14
AllegedAlec wrote: post #3

Earlier quoted context omitted.

> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 card you're going to be rejecting only half of your draws, so the average slowdown is going a factor of 2. It it though? I'm a but shoddy on my mathematics, but I'd wager from the birthday problem that you'd probably have to rejec…

Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.

You're right, but it's not 2^8. It is √2^64 = 2^32.

Re: Algorithm No One Knows About (2016)

#54

Post by mihaifm »

kadoban wrote: post #6
AllegedAlec wrote: post #3

Earlier quoted context omitted.

> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 card you're going to be rejecting only half of your draws, so the average slowdown is going a factor of 2. It it though? I'm a but shoddy on my mathematics, but I'd wager from the birthday problem that you'd probably have to rejec…

If you think about it one draw at a time it's pretty clear and there's no room to be missing anything really. 2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.

That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).

Re: Algorithm No One Knows About (2016)

#55

Post by ses1984 »

klingonopera wrote: post #12
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…

A use case may be shuffling the entire list, if I'm not mistaken?

How long do you think it will take you to shuffle a list of size 2^64?

Re: Algorithm No One Knows About (2016)

#56

Post by IIAOPSW »

Ok I'll take a shot at it.

Pick a number between 0 and N. Let's call it p for pivot. Each draw after this initial draw is either less than p with probability p/(N-1) or greater than p with probability 1-p/(N-1). You need to make k-1 additional draws. The probability of m of those draws being less than p is given by the binomial distribution. Choose m from the binomial distribution. Then run the algorithm recursively on the space 0 to p-1 and p+1 to N. Some pseudo-code.

    def deckpicker(N,k,offset=0):
        if k == 0:
            return
        p = uniform_dist(0,N)
        m = binomial_dist(k-1, p/(N-1))
        deckpicker(p-1,m,offset)
        print(p+offset)
        deckpicker(N-(p+1),(k-1)-m,offset+p+1)

Re: Algorithm No One Knows About (2016)

#57

Post by LolWolf »

OscarCunningham wrote: post #48
LolWolf wrote: post #41

Earlier quoted context omitted.

EDIT: This is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 The problem is that all of these little errors add up to give you a logarithmic slowdown. In particular, the solution proposed in this comment is still Ω(k log k) (where k is the number of elements drawn), which is slower than the algorithm's proposed solution of O(k).

I see. In particular the log(k) doesn't come from repeat attempts, it comes from the time needed to search through your list of drawn elements to see if you've seen the chosen element before.

See my edit! Oops.

Anyways, if you were to keep it in some hash-based structure, you could check membership! (But I'm sure you already knew that :)

Re: Algorithm No One Knows About (2016)

#58

Post by OscarCunningham »

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…

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.

Re: Algorithm No One Knows About (2016)

#59

Post by yorwba »

kadoban wrote: post #4
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…

Yeah, the motivating text from the article isn't very convincing. Seemed really odd that they didn't even describe the algorithm either. Sure, there's code and a link to the paper, but you spent so much time in prose trying to talk it up, needs to have the full story in prose too if you're going to do that. At least give the main idea. I skimmed the paper, and the sort of algorithm used does have some advantages I ca…

The algorithm in the paper does have a threshold of n/13, beyond which it switches to "Method A".

Re: Algorithm No One Knows About (2016)

#60

Post by OscarCunningham »

LolWolf wrote: post #57
OscarCunningham wrote: post #48

Earlier quoted context omitted.

I see. In particular the log(k) doesn't come from repeat attempts, it comes from the time needed to search through your list of drawn elements to see if you've seen the chosen element before.

See my edit! Oops. Anyways, if you were to keep it in some hash-based structure, you could check membership! (But I'm sure you already knew that :)

No structure can check membership in O(1) time if n is big enough.
Post reply on HN