I am working on a new kind of sorting "algorithm" for when the cost of comparisons is high and heterogeneous. The ideal use case is as a methodology for minimizing the number of pairwise human evaluations: in AI, marketing, search evaluation, clinical trials, etc... It works by keeping track of what pairs are solidly established, which parts of the ranking are still ambiguous, what alternatives are still possible/impactful and from this deduce the fraction of the sorting that can be reused during updates.
Think of it as reversible incremental ranking with information-theoretic guarantees and updates that scale linearly with the number of items to rank. From this I realized there was a direct application in machine learning: differential sorting and ranking. I've been exploring this space for the past couple days and it seems I could be flirting with state of the art performances. To sort 8000 items, softsort takes 1.9 secs to complete one forward and one backward pass. My implementation takes 27ms. 488Mo for softsort. 0.18Mo for me. Sorting 10^6 items costs about 100ms and 15Mo. Softsort can't run at this scale. Alas softsort isn't SOTA, fastsoftsort is. We both run in O(n log n) in time and O(n) in space, and have very similar raw performance profiles except that my thing takes 3x as much memory ... which allows me to update the ranking in linear time on the next runs. Mmmh!
Think of it as reversible incremental ranking with information-theoretic guarantees and updates that scale linearly with the number of items to rank. From this I realized there was a direct application in machine learning: differential sorting and ranking. I've been exploring this space for the past couple days and it seems I could be flirting with state of the art performances. To sort 8000 items, softsort takes 1.9 secs to complete one forward and one backward pass. My implementation takes 27ms. 488Mo for softsort. 0.18Mo for me. Sorting 10^6 items costs about 100ms and 15Mo. Softsort can't run at this scale. Alas softsort isn't SOTA, fastsoftsort is. We both run in O(n log n) in time and O(n) in space, and have very similar raw performance profiles except that my thing takes 3x as much memory ... which allows me to update the ranking in linear time on the next runs. Mmmh!