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

41–50 of 200 posts

Re: Algorithm No One Knows About (2016)

#41

Post by LolWolf »

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…

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

Re: Algorithm No One Knows About (2016)

#42

Post by airstrike »

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

Re: Algorithm No One Knows About (2016)

#44

Post by tromp »

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?

We can compute a random k-size subset of {0..n-1} as rndsubset(0,k,n), where

rndsubset(i,0,n) = {}

rndsubset(i,k,n) = {i} union rndsubset(i+1,k-1,n) with probability k/(n-i), rndsubset(i+1,k,n) otherwise

This however takes on average n/k time per element, which is prohibitive when n >> k.

The probability of {h} being the next chosen element in rndsubset(i,k,n) is k/(n-h) * Prod_{i<=j<h} 1-k/(n-j), which is sampled directly in constant time by Vitter.

Re: Algorithm No One Knows About (2016)

#46

Post by OscarCunningham »

klingonopera wrote: post #39
OscarCunningham wrote: post #33

Earlier quoted context omitted.

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

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.

Re: Algorithm No One Knows About (2016)

#47

Post by drfuchs »

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 if they're hidden in some cute construct built into your favorite language.

Re: Algorithm No One Knows About (2016)

#48

Post by OscarCunningham »

LolWolf wrote: post #41
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…

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.

Re: Algorithm No One Knows About (2016)

#49

Post by yorwba »

klingonopera wrote: post #39
OscarCunningham wrote: post #33

Earlier quoted context omitted.

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

You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.

Re: Algorithm No One Knows About (2016)

#50

Post by mehrdadn »

LolWolf wrote: post #37
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.

Yeah, but I think you can be more clever than just doing naive array insertions, by trying to batch them up. At least, we know decreasing sequences of indices can be done in one pass with no changes, and increasing sequences can be done in one pass by accumulating shifts. That leaves alternations to worry about. Now I haven't fully thought this through, but I think something along these lines might work (there may be errors in some of the details here): treat the list of indices you're inserting into as the leaves of a binary tree, and create the intermediate nodes of that tree, initializing them to zero. The intermediate nodes represent offsets (initialized to 0) that will be logically added to all earlier nodes. Then sort the nodes, breaking ties so that the later ones are first. Now perform every insertion at {the given index plus its ancestors}, and then increment the counters for all ancestors of that index so that you account for shifts of later elements. This should get you to O(k log k) or so.

In fact, this makes me wonder why there isn't a multi-insert function in every language's vector implementation...

Post reply on HN