[Haskell-cafe] Release: rangemin-2.0

[Louis Wasserman]

The original rangemin project was my first Haskell package, and definitely
my first attempt at super-advanced algorithms work in Haskell.  (I here
define "super-advanced" as "not in MIT OpenCourseWare undergraduate
algorithms lecture notes from any year.")

Here's the problem: Suppose we have an array of length n.  Preprocess the
array in O(n) time such that we can look up the minimum element of any slice
in the array in O(1) time.

Coming back to this project after two years, and especially rewriting the
approach with the vector package, was *spectacularly* fun.
rangemin-2.0<http://hackage.haskell.org/package/rangemin>is now on
Hackage, with a new API as well.  The constant factor on the O(n)
preprocessing is, based on criterion benchmarks, 88 milliseconds per million
elements, on my 2.5GHz Ubuntu laptop, with GHC HEAD and -O2 -fvia-c
-optc-O3.

I've spent the past three days unsuccessfully trying to get the LLVM backend
to work, because this algorithm has a *lot* of the sort of tight loops that
LLVM excels at.  Unfortunately, I haven't been able to install the LLVM
backend, which is very disappointing.  That said, GHC with the C backend is
about 10x slower than an optimized C++ implementation, which is all right
considering that the algorithm plays so much to C++'s strengths.

(If anybody has LLVM working and would be willing to help, I'd massively
appreciate it if you could benchmark both the C++ implementation -- not
mine, but included in a tarball inside the rangemin distribution package --
and my implementation, with LLVM -O2.  Benchmarking code is
here<http://hpaste.org/fastcgi/hpaste.fcgi/view?id=25309#a25309>
.)

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100503/67c00987/attachment-0001.html