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

21–30 of 200 posts

Re: Algorithm No One Knows About (2016)

#21

Post by rini17 »

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.

Re: Algorithm No One Knows About (2016)

#22

Post by coleifer »

tiborsaas wrote: post #5

Why is hashmap not good enough for unique ID generation? const tweetIDs = {}; while(TWEET_COUNT){ const rnd = Math.random() * MAX_TWEET_ID; if(!tweetIDs[rnd]){ tweetIDs[rnd] = true; TWEET_COUNT--; } }

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.

Re: Algorithm No One Knows About (2016)

#24

Post by panic »

vardump wrote: post #13

While reading, I was thinking about LFSR [0] with suitable properties and period. Not strictly random, although LFSRs are commonly used for generating "random" numbers. [0]: https://en.wikipedia.org/wiki/Linear-feedback_shift_register

Wolfenstein 3D's FizzleFade uses an LFSR to visit each screen pixel exactly once in a pseudorandom order: http://fabiensanglard.net/fizzlefade/index.php

There's an alternative FizzleFade implementation using Feistel networks: http://antirez.com/news/113 -- I think the same technique could be used here to randomly permute the index space.

Re: Algorithm No One Knows About (2016)

#25

Post by avip »

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.

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

Re: Algorithm No One Knows About (2016)

#27

Post by klingonopera »

coleifer wrote: post #22
tiborsaas wrote: post #5

Why is hashmap not good enough for unique ID generation? const tweetIDs = {}; while(TWEET_COUNT){ const rnd = Math.random() * MAX_TWEET_ID; if(!tweetIDs[rnd]){ tweetIDs[rnd] = true; TWEET_COUNT--; } }

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 entire purpose? If k = n, output would be input...

Re: Algorithm No One Knows About (2016)

#29

Post by LolWolf »

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 and then check if this card has been drawn.

Re: Algorithm No One Knows About (2016)

#30

Post by Dylan16807 »

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 hits certain rare values it will re-sample the RNG.

Post reply on HN