Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The case for a learned sorting algorithm

blog.acolyer.org

Post reply on HN
Print view View original

11–20 of 23 posts

Re: The case for a learned sorting algorithm

#11

Post by vbarrielle »

edejong wrote: post #2

Is the paper "NN-sort: Neural Network based Data Distribution-aware Sorting" [1] not a year prior to the cited paper? It seems to discuss the same approach. [1] NN-sort: Neural Network based Data Distribution-aware Sorting: https://arxiv.org/pdf/1907.08817.pdf

This paper does not look like a strong paper, in particular it's very terse when describing the way the neural network is trained, which fails to convince that they did not train the neural network model on the sorted input. They are also not clear on their timings, it's not sure they include the training time in their benchmarks. For these reasons, it does not look very reproducible, and there's no obligation to cite non-reproducible work.

Re: The case for a learned sorting algorithm

#12

Post by Upvoter33 »

smusamashah wrote: post #6

>The results show that our approach yields an average 3.38x performance improvement over C++ STL sort, which is an optimized Quick- sort hybrid, 1.49x improvement over sequential Radix Sort, and 5.54x improvement over a C++ implementation of Tim- sort, which is the default sorting function for Java and Python. This is a lot

Would be curious: this performance result includes training time? I guess I should read the paper...

Re: The case for a learned sorting algorithm

#13

Post by gumby »

Upvoter33 wrote: post #12
smusamashah wrote: post #6

>The results show that our approach yields an average 3.38x performance improvement over C++ STL sort, which is an optimized Quick- sort hybrid, 1.49x improvement over sequential Radix Sort, and 5.54x improvement over a C++ implementation of Tim- sort, which is the default sorting function for Java and Python. This is a lot

Would be curious: this performance result includes training time? I guess I should read the paper...

The article says it does.

Re: The case for a learned sorting algorithm

#14

Post by 0-_-0 »

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"

Re: The case for a learned sorting algorithm

#16

Post by qsort »

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.

Re: The case for a learned sorting algorithm

#18

Post by 0-_-0 »

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.

That's almost never the case in practice. What distribution the data is drawn from on the other hand can often be known or approximated.

Re: The case for a learned sorting algorithm

#19

Post by qsort »

0-_-0 wrote: post #18
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.

That's almost never the case in practice. What distribution the data is drawn from on the other hand can often be known or approximated.

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

Re: The case for a learned sorting algorithm

#20

Post by 0-_-0 »

qsort wrote: post #19
0-_-0 wrote: post #18

Earlier quoted context omitted.

That's almost never the case in practice. What distribution the data is drawn from on the other hand can often be known or approximated.

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