The case for a learned sorting algorithm • Hacker News Board

Re: The case for a learned sorting algorithm

#21

Post by qsort » Mon, Oct 19, 2020, 9:15 PM UTC

0-_-0 wrote: post #20

qsort wrote: post #19

Earlier quoted context omitted.

What do you mean "is drawn from"? Isn't the previous condition a reasonable characterization of "you know what distribution it's drawn from"?

Let's say you draw 1 million samples from a uniform distribution between 0 and 1. I'm saying that if you know the distribution you can sort in O(N log(log(N))). Are you claiming you can sort them in O(N)?

Assuming "1 million" is a proxy for taking the limit to infinity, i.e. the usual asymptotic setting, if you are willing to accept that the algorithm will "only" work with probability 1, then yes, I can.

Let N be the size of the array. Create N new empty lists, numbered from 0 to N-1. Divide [0, 1) in N equal brackets B0 = [0, 1/n); B1 = [1/n, 2/n]... BN-1 = [(n-1)/n, 1). For each element, determine the bracket it falls in and append it to the corresponding list. Sort each list. Because of the uniformity hypothesis, for n -> infinity, the probability that each bracket contains O(1) elements goes to 1, therefore the running time is O(N) with probability 1.

Re: The case for a learned sorting algorithm

#22

Post by nemoniac » Mon, Oct 19, 2020, 9:52 PM UTC

qsort wrote: post #16

0-_-0 wrote: post #14

I remember learning as part of my CS degree that knowing the distribution of your data allows you to sort it in N log(log(N)) instead of N log(N) (which assumes a comparison based sort), although back then it wasn't given such a fashionable name as "learned sort", and determining the distribution wasn't called "training"

If you know the distribution of your data (in the sense that you are guaranteed that each datapoint is iid with a distribution described by some known PDF f : R -> R), you can sort in O(N) with probability 1.

I'd really like to read up on this. Do you have a source?

Re: The case for a learned sorting algorithm

#23

Post by qsort » Mon, Oct 19, 2020, 11:22 PM UTC

nemoniac wrote: post #22

qsort wrote: post #16

Earlier quoted context omitted.

If you know the distribution of your data (in the sense that you are guaranteed that each datapoint is iid with a distribution described by some known PDF f : R -> R), you can sort in O(N) with probability 1.

I'd really like to read up on this. Do you have a source?

It's really dead simple, look at my other comment in the same thread. The only caveat is that all those fancy words before are actually necessary minimal hypotheses, not just fancy words.