Hacker News Reader

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 can see. Mostly, you can start giving output right away and don't need extra storage, and you don't have to be careful that n << N or have separate algorithms with a threshold or anything.

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

Ah, thank you, I did not see that part.

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

EDIT: This is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 < c ≤ 1). :)

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

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

In general, assuming that we have constant-time operations on arbitrarily large numbers (which we almost universally assume when doing these analyses, except in very specific fields), then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly).

Additionally, the only problem with this approach is the extra O(k) space taken up by the structure, which doesn't meet the condition if the result is to be reported in a streaming fashion (but this is not the case in most practical applications)! For comparison, Vitter's is able to do this streaming output in O(1) space.

> then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly).

Hashtables can never guarantee constant time operations. It is expected O(1) time, but it is completely possible that everything hashes to the same bucket and you get O(n) operations, no matter how much you rehash.

The algorithm is a randomized algorithm and we're assuming we're picking a good hash. The probability of that event is exponentially vanishing, so, in expectation (which is the runtime we're looking for, as we are analyzing a randomized algorithm based on rejection sampling) it is O(1).

In the worst case analysis of this rejection-sampling algorithm, the time for table look up and insertion doesn't even factor in since you'll have infinite run-time.

> Hashtables can never guarantee constant time operations.

A bit mask is a form of hash table and is guaranteed O(1) lookup for O(lg(Universe)) space.

When you have fixed universes, all kinds of options open up. I personally love vEB Trees, which can do set operations in O(lg(lg(U)))

Yes, in cases where direct addressing is possible you get guaranteed constant time. That's really more of an array than a hashtable IMO.

> 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 reject much more than half of the 'cards', and as you get to the end, you'd have to redraw several times for each card.

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

The "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done.

One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k.

If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results immediately. (You'd want to use something like Fisher-Yates to shuffle for these properties)

This also wouldn't use much extra space, and doesn't require special handling for small or large k.

Biggest downside is it will change the order of the original set. And it's only worth doing if you already have an array full of the items to choose, most likely.

I think the article discusses the fact that shuffling the entire initial set takes up way too much memory.

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.

Ah, right. I wasn't thinking properly. Thanks for the explanation.

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

Yes, thanks. Took the root of the wrong number.

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.

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

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.

Wouldn't this have a bias to how the initial input sequence is?

EDIT: On the other hand, due to randomness, it could cancel itself out, I don't know, beats me. My brain hurts, at this point, I'd try to figure it out statistically first, to see if it's even a valid assumption before continuing the theoretical thought, but I'm presently too lazy to code that out... it's Friday, cheers.

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

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.

I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above...

...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...

OscarCunningham's implementation https://news.ycombinator.com/item?id=20961548 remembers what has already been swapped using the counter i.

Fisher-Yates [1] algorithm is proven to "produce an unbiased permutation: every permutation is equally likely".

Additionally, "The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place."

[1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

According to examples in the English Wikipedia, the method I described above is actually the Fisher-Yates method (and its naive implementation, and thus the O(n²) complexity), and the swapping method on everyone's minds was actually Durstenfeld's (optimization?), with O(n).

The initial code snippet intended to be Durstenfeld was erroneously an off-by-one Sattolo implementation, which then further solidifyed my suspicion that it had a bias, which Sattolo's implementation actually indeed has. The Durstenfeld method is however proven to be unbiased.

To add further confusion to the names in the issue, though some readers might not be able to verify due to the language barrier, the German Wiki states (claims?) Fisher-Yates is Durstenfeld's method with O(n), and the "naive" Fisher-Yates is labelled as the "direct" approach, with O(n²). The name Durstenfeld is not mentioned anywhere on the German Wiki. Though the names are different, the maths are the same in both English and German. I speak German and often read both versions of an article, in case anyone's wondering why I even brought up the topic.

Thank you for posting the link.

EDIT: I try not to post usernames in text, in case anyone ever changes their name.

EDIT2: I recommend to always positively increment an iterator from 0 to n-1, and use in-loop arithmetics to get the actual desired iterator/index you require. It's less performant, but I'd argue mistakes are less common.

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

This solution requires storing the 2^63 cards you have picked. That's impossible to do today.

It would take a lot of storage, but it's not impossible. 2^64 bits equals 2097152 terabytes. A lot, but doable with modern technology. I guess for $100-200M.