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

31–40 of 200 posts

Re: Algorithm No One Knows About (2016)

#31

Post by LolWolf »

avip wrote: post #25
rini17 wrote: post #21

Earlier quoted context omitted.

Trivial algorithms (like one implemented in Python) slow down when k is close to n. Or when n is large, then it is not possible to use bitmap to mark dealt cards.

The python algo does not get slow when n is large. The k~n case obviously calls for inverse selection. https://github.com/python/cpython/blob/master/Lib/random.py#...

NOTE: This comment I wrote is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 Yeah, but the k ~ n/2 case (in which inverse selection and normal selection have the same runtime) is still Ω(n log n) (equiv Ω(k log k)), which is still "slower" than the presented algorithm.

Re: Algorithm No One Knows About (2016)

#32

Post by GistNoesis »

Here is how I would do it. Pick a prime p bigger than N. Pick a random permutation of Z/pZ. Pick an initial state. Advance to the next state, to cycle through all the values exactly once.

You use rejection sampling if the state is greater than N, so as long as you pick p close to N this should happen very rarely and be amortized O(1).

If N is big this advance to the next state can be encoded easily as a multiplication by an element of Z/pZ (multiplication followed by modulo p), and you will cycle through all the values because Maths. If N is not so big you pick a few (m) elements of Z/pZ to represent your permutation, and you use the first number as a multiplier mod p the first time, then the second number as a multiplier mod p the second time, and so on..., and you will also cycle through all the value, because Maths as long as you don't get a 1 while multiplying sequentially your m elements.

Don't forget to stamp it good enough(TM), if not use Dual-ECC.

Re: Algorithm No One Knows About (2016)

#33

Post by OscarCunningham »

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?

They specifically say that a nice thing about Vitter's algorithm is that it produces its results in sorted order, and that it's easy to shuffle them after they've been drawn.

> The reason it’s nice for an algorithm to produce results in sorted order is because it’s easy to randomize the order after the fact.

Re: Algorithm No One Knows About (2016)

#34

Post by ikeboy »

Tldr of the algorithm from the paper:

Instead of choosing random numbers to include in the list, they're choosing the gap between numbers. They derive the distribution of this gap then approximate it so it can be calculated quickly.

Re: Algorithm No One Knows About (2016)

#35

Post by tiborsaas »

klingonopera wrote: post #27
coleifer wrote: post #22

Earlier quoted context omitted.

The algorithm described in the article has other desirable properties: * IDs are returned in sorted order * IDs are generated one after another, ie could be implemented as a generator or coroutine * No additional space required during the computation Resulting in a single pass.

Nicely said. I was thinking of ways to solve the problem by eliminating the overhead of checking whether a random number was already drawn, when Vitter's solution was to make the random number generator produce random numbers in a sorted manner, thus eliminating that overhead entirely. EDIT: Then again... if the algorithm is to be used to shuffle a list, wouldn't returning the selection in a sorted manner defeat the…

It would. The original problem is to draw a subset of tweets.

If there's a chance to randomize the entire tweet archive, then it's a shuffling algorithm now.

Re: Algorithm No One Knows About (2016)

#36

Post by IIAOPSW »

AllegedAlec wrote: post #3
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…

> 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…

But on each draw you need to check if its a card you've already drawn. You can hold your cards in a set data structure but then you pick up the complexity of the insertion operation into sets. IIRC sets are basically hash tables that map keys to themselves. Insertion is O(1)...until you need to resize your table due to hash collision.

Re: Algorithm No One Knows About (2016)

#37

Post by LolWolf »

mehrdadn wrote: post #11

I haven't read the algorithm code, but I think you can do the following? For n items, pick a random k https://code.activestate.com/recipes/126037-getting-nth-perm...

Ooh, this feels like it gets close to the solution!

It's not quite there as stated, though, since this algorithm requires O(k^2) time (where k is the number of elements to be randomly drawn) as you have to insert items into specific indices in the array.

Re: Algorithm No One Knows About (2016)

#38

Post by afiori »

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…

The problem the author tries to avoid here is in this way the memory requirement is proportional to 2^63.

Re: Algorithm No One Knows About (2016)

#39

Post by klingonopera »

OscarCunningham wrote: post #33
klingonopera wrote: post #12

Earlier quoted context omitted.

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

They specifically say that a nice thing about Vitter's algorithm is that it produces its results in sorted order, and that it's easy to shuffle them after they've been drawn. > The reason it’s nice for an algorithm to produce results in sorted order is because it’s easy to randomize the order after the fact.

...but is it actually so? The more I think about it, the entire topic seems to be, how do you say, a dog biting its own tail?

You have a sorted list. Now randomize it. Either you pick random from source, or you place randomly into destination. And then, as k approaches n...

Re: Algorithm No One Knows About (2016)

#40

Post by airstrike »

rini17 wrote: post #21
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?

Trivial algorithms (like one implemented in Python) slow down when k is close to n. Or when n is large, then it is not possible to use bitmap to mark dealt cards.

What's preventing someone from implementing a non-trivial algorithm in Python?
Post reply on HN