Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: Dan Doel <dan.doel <at> gmail.com>
Subject: ANNOUNCE: uvector-algorithms 0.1
Newsgroups: gmane.comp.lang.haskell.cafe
Date: Sunday 14th December 2008 17:13:44 UTC (over 8 years ago)
Hello,

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-
algorithms.

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

datasets.

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:
 http://hackage.haskell.org/cgi-bin/hackage-scripts/package/uvector-algorithms

Enjoy, and please let me know of any issues.
-- Dan
 
CD: 3ms