pthariensflame/discrimination.rs

Generic worst-case-linear-time sorting and partitioning algorithms based on discriminators

discrimination.rs

WIP

Generic worst-case-linear-time sorting and partitioning algorithms based on discriminators. Partially a port of the Haskell library of the same name.

discrimination.rs's Issues

On adapting discrimination to Rust

Having previously drafted a library for generic discrimination in Rust, I can probably offer some comments.

(I will edit this later. Meanwhile, you may want to skim my comment on r/rust – although it is not very detailed when it comes to actual implementation choices.

To begin with, a note: the performance of order discriminators is primarily determined by the speed of the sorting routine used for the base order (NatO in the paper), and by how much overhead you incur when applying that sorting routine with a given ordering relation; analogously, equivalence discriminators are more or less dependent on the data structure that backs the grouping operation.

In more concrete terms, the half-bucket, half-radix sorting routine presented in the paper works well for illustrative purposes, but I failed to achieve reasonable perfomance when sorting types with relatively complex ordering relations. I would recommend starting directly with a real radix sort on Natural, and defer sorting of all fixed-size types to it. With regard to overhead caused by orderings, my ideas are still fairly nebulous and remain unimplemented (as I planned to work on them during the upcoming holidays), so it is perhaps too early to offer sound advice.