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

81–90 of 200 posts

Re: Algorithm No One Knows About (2016)

#81

Post by norswap »

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…

I'm feeling like I'm missing something, but why not? 2^64 is the number of cards in the deck, but that's not the number of cards we're picking. That might be just 10.

Re: Algorithm No One Knows About (2016)

#82

Post by stillworks »

norswap wrote: post #81
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…

I'm feeling like I'm missing something, but why not? 2^64 is the number of cards in the deck, but that's not the number of cards we're picking . That might be just 10.

From the article: "Stated more formally: given non-negative integers k and n with k Focus on k Also, in the comments section in the article, the author counters a comment in favor of Python's random generator along the same lines.

Re: Algorithm No One Knows About (2016)

#83

Post by lucb1e »

epeus wrote: post #28

Getting this wrong can tank your product - see what happened to Draw Something http://epeus.blogspot.com/2012/04/draw-something-ceo-grace-a...

Summary without the drama: by not using a "discard pile" but picking randomly from the same set of words every time, you get repeat words paradoxically often (birthday paradox), which is what pictionary did and people complained about.

Re: Algorithm No One Knows About (2016)

#84

Post by amcsi »

So let me get this straight...

This algorithm creates an initially empty array of size K with the DB internal ids of what would randomly be selected. Then it goes in order from 0 to the number of rows - 1, and for each one it goes e.g. "What are the chances that number 0 would get randomly picked out of N items if K items need to be picked?" Then, if the #0 passes the "random check", it gets added. Then it would go to 1 and go "What are the chances #1 would be picked out of N-1 items if K-1 items need to be picked?" ...and repeated so on until all K random items have been picked?

Re: Algorithm No One Knows About (2016)

#85

Post by drfuchs »

norswap wrote: post #81
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…

I'm feeling like I'm missing something, but why not? 2^64 is the number of cards in the deck, but that's not the number of cards we're picking . That might be just 10.

The algorithm has to deal with picking, say, 2^63 of them. No room in RAM or even on disk to keep track of the chosen cards.

Re: Algorithm No One Knows About (2016)

#86

Post by SAI_Peregrinus »

norswap wrote: post #81
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…

I'm feeling like I'm missing something, but why not? 2^64 is the number of cards in the deck, but that's not the number of cards we're picking . That might be just 10.

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!

Re: Algorithm No One Knows About (2016)

#87

Post by sweeneyrod »

OscarCunningham wrote: post #46
klingonopera wrote: post #39

Earlier quoted context omitted.

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

An easy way to randomise a list is the following: import random list = [0,1,2,3,4,5,6,7,8,9] length = len(list) for i in range(1,length): j = length - i k = random.randrange(j+1) list[j], list[k] = list[k], list[j] print(list) [3, 9, 6, 4, 7, 8, 5, 1, 0, 2] The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.

That code doesn't work as written (there is an off-by-one error in the first iteration of the loop). But the intended algorithm (starting at the end of the list, swap each element with a random predecessor) doesn't produce a uniform distribution anyway; for instance it will never produce an output where the last element is unchanged.

Re: Algorithm No One Knows About (2016)

#88

Post by justicz »

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.

I’ve used this trick with a 64-bit block cipher (base-32 encoding the result) to generate short, unique public identifiers (to put in URLs) for entries in a database based on an integer primary key.

Re: Algorithm No One Knows About (2016)

#89

Post by OscarCunningham »

sweeneyrod wrote: post #87
OscarCunningham wrote: post #46

Earlier quoted context omitted.

An easy way to randomise a list is the following: import random list = [0,1,2,3,4,5,6,7,8,9] length = len(list) for i in range(1,length): j = length - i k = random.randrange(j+1) list[j], list[k] = list[k], list[j] print(list) [3, 9, 6, 4, 7, 8, 5, 1, 0, 2] The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.

That code doesn't work as written (there is an off-by-one error in the first iteration of the loop). But the intended algorithm (starting at the end of the list, swap each element with a random predecessor) doesn't produce a uniform distribution anyway; for instance it will never produce an output where the last element is unchanged.

I had an error which I believe I have now fixed. The intended algorithm is "starting at the end of the list, swap each element with a random predecessor or possibly with itself".

Re: Algorithm No One Knows About (2016)

#90

Post by dahfizz »

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.
Post reply on HN