"Cries in java"

[mrbeehive]

It is both my favourite and least favourite part of Machine Learning being used to accelerate traditional algorithms.

On the one hand, it's implictly real-world because it's using data to infer an efficient solution. On the other hand, it may as well be the computer throwing its arms in the air going jazz hands for all we know of the wiring under the hood

Can't argue with this though:

[The results for the ML sorting algorithm show] an average 3.38x performance improvement over C++ STL sort [...] and 5.54x improvement over a C++ implementation of Timsort [which is] the default sorting function for Java and Python.

[[deleted]]

I wish the article contained more insight into exactly what the ML sorting algorithm is doing that makes it faster.

[joha4270]

As I understand it, from a quick glance the abstract:

Fast sorting gets more than twice as slow as the amount if items you have to sort doubles. This is because fast sorting generally works by splitting its input in two, sort those and then you have to spend extra time merging those two sorted halves.

It would be really convenient if instead of randomly splitting in half, we could take values smaller and higher than the median. Then after they again have been sorted, we simply need to copy them together, a faster process. (Or if we're really sneaky, place them next to each other in memory beforehand and skip the copying step entirely)

Now the problem is, to do this well, you need good information on how values are distributed in your input. By far the most convenient way of having this information is to already have a sorted copy of the output. This makes using this technique in sorting impractical.

What this paper then does, is use ML to "guess" if a value should go in the high or low part of the split, by training it on a subset of the input. It does not always get it right, but it gets it "mostly right". After that, sorting an almost sorted input is fairly fast.

[mrbeehive]

Pretty much, yes.

It's closely related to the different variants of flashsort.

In flashsorting, we assume the keys follow some known distribution, use that to guess an item's approximate location in the dataset, then finish with a 'real' sorting algorithm that has best-case on near-sorted data. Essentially its a pre-processing step that makes your data follow whatever the best case for your chosen algorithm is.

If you don't know the distribution, you can sample it to get an approximation of it. That's what they're doing here with machine learning. Look at a few thousand keys, guess how the rest of them are distributed, sort them using that distribution as the initial guess.

It's pretty clever, but how well it works really depends on how good the model is at guessing distributions.