Comment by Syzygies | Hacker News Reader

Comment by Syzygies | Hacker News Reader

In college in the 1970's, I took a combinatorial algorithms class with Herb Wilf. He explained that choosing a subset of k distinct elements from 1..n uniformly at random was likely k log k, because you needed to detect collisions, and "sorting" k elements was k log k.

(Always check your assumptions. Sorting has an k log k lower bound if all you can do is compare elements. With integers 1..n, one can do much more.)

I showed up at 5pm at his office, as he was bracing himself for the drive from Swarthmore back to Philly, wondering why he ever took this gig. I proposed a linear algorithm: Break 1..n into k bins, and only sort to detect collisions within each bin. Bins would have an average occupancy of 1, so it didn't matter what sort you used.

(I found this idea later in Knuth, and was briefly disillusioned that adults didn't read everything.)

I looked like George Harrison post-Beatles, I probably smelled of pot smoke, and he dismissed my idea. Then my dorm hall phone rang at 10pm, a professor of mine relaying an apology. For that and other ideas, the second edition of his book opened with thanks to me.

I'm surprised now that I realized then that bubble sort actually had the least overhead, in such an application. People don't use Strassen to multiple matrices unless the matrices are really big. For sorting, "really big" is 2 or 3 elements.

> choosing k elements from 1..n uniformly at random

Can you clarify the problem?

k elements uniformly at random, independently, with replacement, sounds like it’s trivially O(k), or perhaps O(k log n) if n is so big that you need O(k log n) bits to merely represent the answer. (Those logs are pesky and can appear and disappear in different models of computation!)

Maybe you mean k distinct elements? Off the top of my head, if n is not huge (n = O(k), or more concretely, n < ck for your choice or c > 1, and I would probably start with 2 if I were implementing this), I would make an array of all the elements and draw k of them using any of a number of straightforward algorithms. (Fischer-Yates, for example, but I admit I had to look up the name.)

For larger n, make a hash table to store the elements selected so far. Now repeat k times: choose an element at random and retry if it’s a duplicate. Then add it to the hash table and continue. Each iteration takes at most 1/c tries on average, so the overall expected time is O(k). (For n < ck, the last few draws may retry quite a lot.)

Thinking of this as sorting seems odd, but I admit I’m thinking about this in 2023, not the 1970s :)

Yes, distinct elements. Fixed. That's the only way what I said makes sense, like how one error-corrects listening to a talk.

They were concerned with the case where n could be absurdly large, and wanted no time or space dependence on n. They improved my idea to cut the multiple of k needed for space.

> Bins would have an average occupancy of 1, so it didn't matter what sort you used.

That's not quite right, though - you only care about the average occupancy if your sorting algorithm is O(b) for b elements. If you're using a O(b^2) sort, you actually care about the root-mean-square occupancy (or in general just the average runtime, or just the total runtime since you'll multiply the average by the number of bins anyway).

The k-bin approach is definitely much faster than O(k log k), but I'm fairly sure it's slightly slower than truely linear, asymptotically, since the runtime will be something like 1+0+4+1 in typical cases, where linear would have to be 1+0+2+1.

Edit: on some cursory Monte Carlo testing, the sum of squares of occupancies actually seems to still converge on a constant factor (of two) times the sum of plain/linear occupancies, which I was not expecting but does make the above point rather moot. (Also, the sum of cubed occupancies seems to converge on a factor of five, which seems downright bizzare.)

(Tangential edit: The factors seem to be 1 2 5 15 52±2 200±20, which might be https://oeis.org/A000110, though none of the interpretations there seem obviously related.)

There's a fixed, rapidly vanishing probability distribution on bin occupancies, which evaluates to a constant per bin when one applies a sorting algorithm. One gets linear algorithms with different constants, depending on the sorting algorithm. You're thinking "deep end of the pool" worrying about b log b versus b^2. I was in the "shallow end of the pool" where the constants in front of fancy sorts took them out of the running.

Like I said about Strassen and matrix multiplication. Great algorithm, but it takes a while to kick in for the lead.

> There's a fixed, rapidly vanishing probability distribution on bin occupancies,

Pretty much; my mistake was underestimating just how rapidly it vanishes. In actuality any sorting algorithm that isn't pathologically horrible garbage like bogosort will work fine, because it runs on meaningful numbers of elements so rarely that it doesn't matter (and I'm not totally sure bogosort is garbage enough).

> where the constants in front of fancy sorts took them out of the running.

For beating O(k log k), the constants don't actually matter, since they just increase the constant factor inside your O(k) runtime. It's just that apparently, the asymptotics don't matter much either for that.

Do people really use Strassen in practice? I don’t seem to see them in the wild.

I guess you mean k log k, not n log n.

yep, thanks. "n log n" is how one always says it, it becomes a local variable in its phrase. Oops.

Reply on news.ycombinator.com