5 ms·
The case for a learned sorting algorithm
- edejong 6y agoIs 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 https://arxiv.org/pdf/1907.08817.pdf
- tokai 6y agoThat paper has not been published. You can't claim a paper is prior, just because a draft was available earlier. Incidently it was send to the same conference as the OP paper. But it seems like it wasn't accepted, while the OP paper was.
- currymj 6y agothis is not really the norm in computer science. it’s generally expected to cite things on arXiv although it is more of a grey area.
- Chirono 6y agoThe paper in this post doesn't use neural networks at all. It also includes the time to train the model in the sorting time, which the paper you linked doesn't. NN-sort trains on historic data to sort future data, which requires the distribution to be roughly the same, whearas this algorithm learns online.
- jl2718 6y agoThis one doesn’t use neural nets.
- vbarrielle 6y agoThis 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.
- smusamashah 6y ago>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
- jl2718 6y agotl,dr: linear spline fitting to approximate a CDF and then recursive bucket sort similar to radix.
- 0-_-0 6y agoI 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"
- qsort 6y agoIf 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.
- 0-_-0 6y agoThat's almost never the case in practice. What distribution the data is drawn from on the other hand can often be known or approximated.
- qsort 6y agoWhat do you mean "is drawn from"? Isn't the previous condition a reasonable characterization of "you know what distribution it's drawn from"?
- 0-_-0 6y agoLet'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)?
- qsort 6y agoAssuming "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.
- glebshevchuk 6y agoCan this approach be made more robust so it could be used in critical programs? Is there a way to formally verify performance of an approach like this?
- deleted 6y ago[deleted]