3 ms·

> Fluxsort starts out with an analyzer that detects fully sorted arrays and sorts reverse order arrays using n comparisons. It also obtains a measure of presort

> Fluxsort starts out with an analyzer that detects fully sorted arrays and sorts reverse order arrays using n comparisons. It also obtains a measure of presortedness and switches to quadsort if the array is less than 25% random. This makes me wonder? is it worth it to do a neural a.i. sort by simply training it? I assume it would be hard to prove that the resulting a.i. is actually infallible and always produces a sorted output, but perhaps it could for practical measures sort faster than most current algorithms.

stingraycharles 5y ago
You mean using a neural network for sorting? I think it will be very expensive, as sorting algorithms usually take low level performance optimizations such as cache locality into consideration, and neural networks are a poor fit for this type of thing.
- HelloNurse 5y ago
  The currently en vogue deep and large neural networks are not only designed to have an affordable but significant evaluation cost (probably not competitive with really cheap techniques, like the partitioning and medians of this Fluxsort) but also to justify this cost with the recognition of fairly subtle patterns: wasted on rough and general worst-case guarantees, positively dangerous with arbitrarily crafted inputs.
  - stingraycharles 5y ago
    Do you have an example of a sorting algorithm that uses a neural network that’s on par with other sorting algorithms in terms of performance? It just seems so counter-intuitive to me that neural networks are an efficient way to handle this, but I would be happy if proven wrong.
somethingAlex 5y ago
There's no neural network you could train using supervised learning to solve sorting in the general case. To train a neural network, the training set and test set need to come from a common probability distribution but the inputs of sorting algorithms can be random. There's no relation between what you could possibly train your network on and what you'd ask it to do. Put another way - the input and output of your model would have zero correlation. There's nothing to train the model to pick up on. Interesting related work: Graves[0] trained a "neural Turing machine" to encode instructions for a basic sorting algorithm. [0] https://arxiv.org/abs/1410.5401 https://arxiv.org/abs/1410.5401

stingraycharles 5y ago

You mean using a neural network for sorting? I think it will be very expensive, as sorting algorithms usually take low level performance optimizations such as cache locality into consideration, and neural networks are a poor fit for this type of thing.

HelloNurse 5y ago
The currently en vogue deep and large neural networks are not only designed to have an affordable but significant evaluation cost (probably not competitive with really cheap techniques, like the partitioning and medians of this Fluxsort) but also to justify this cost with the recognition of fairly subtle patterns: wasted on rough and general worst-case guarantees, positively dangerous with arbitrarily crafted inputs.
- stingraycharles 5y ago
  Do you have an example of a sorting algorithm that uses a neural network that’s on par with other sorting algorithms in terms of performance? It just seems so counter-intuitive to me that neural networks are an efficient way to handle this, but I would be happy if proven wrong.

somethingAlex 5y ago

There's no neural network you could train using supervised learning to solve sorting in the general case. To train a neural network, the training set and test set need to come from a common probability distribution but the inputs of sorting algorithms can be random. There's no relation between what you could possibly train your network on and what you'd ask it to do. Put another way - the input and output of your model would have zero correlation. There's nothing to train the model to pick up on. Interesting related work: Graves[0] trained a "neural Turing machine" to encode instructions for a basic sorting algorithm. [0] https://arxiv.org/abs/1410.5401 https://arxiv.org/abs/1410.5401