[Haskell-cafe] ANNOUNCE: uvector-algorithms 0.1
dan.doel at gmail.com
Sun Dec 14 12:13:44 EST 2008
I've been sitting on this for a while, waiting for some changes to uvector to
go in, but finally decided I should just release it, and fix it up if and when
said changes go in. So, I'm announcing the first release of uvector-
What it is is a library of algorithms (mostly sorting) for the mutable arrays
defined in uvector. It has several varieties of sorting, including introsort
(quicksort which falls back on heapsort in bad cases), heapsort, a simple top-
down merge sort and a radix sort (as well as insertion sort, and optimal
sorting for length<=4 arrays, which probably won't get much use outside of the
implementation of the other sorts). All modules attempt to export as uniform
an interface as possible, so that one can substitute between them freely, say
when trying to determine which algorithm is best suited for your particular
Also exposed are the operations that allow you to use the arrays as heaps
(which is the basis for implementing heapsort), and partial sorts and selects
in heap and intro variety. Lastly, there is a combinator for safely using
these mutable array algorithms to sort immutable arrays.
All of these algorithms have been painstakingly profiled, and their generated
core examined to do as little heap allocation and as much unboxing as
possible, and to inline and specialize for maximum performance (unless, of
course, I've managed to miss anything). I've been running a relatively simple
benchmarking suite that tests various kinds of inputs, and in my experience,
the sorts herein tend to beat glibc's sort, and do relatively well compared to
GNU's STL sorts over vector<>s (taking 50% or so more time at present,
although this library may well be better at heapsorting random arrays, if you
want something to brag about :)).
For future work, I've been working on an implementation of Python's timsort
(which is a very fancy bottom-up merge sort), but it's not ready yet. I'd also
like to introduce some combinators for easy Schwartzian transforms, but that
again requires modifications to uvector. I may also look at moving some of my
benchmark program into the package.
Suggestions for other algorithms people would like to see are of course
welcome (especially if accompanied by papers/references on how to implement
them if they're not well known).
The hackage page is here:
Enjoy, and please let me know of any issues.
More information about the Haskell-Cafe