The rangemin package

[Tags: bsd3, library]

Rapidly (in linear time) preprocesses a vector so that the minimum element of any given subrange can be looked up in constant time.

This implementation is based on an algorithm of Fischer and Heun, which can be found at http://dx.doi.org/10.1007/11780441_5. Despite being written entirely in Haskell (and maintaining referential transparency internally), it is competitive against the C++ implementation written by Fischer and Heun themselves (included in the tarball), especially when compiled with LLVM.

Depending on the target system, this library compiled with -fasm approximately ties with the original authors' C++ implementation compiled with -O3 -funroll-loops. With -fllvm -optlc-O3, this library has been observed to beat the same C++ implementation by 20-30%.

Internally, this library rolls its own stream fusion system, avoiding the vector package's issues with duplicated index variables and providing a few other special features. This package's API does, however, fuse (to the extent possible) with input vectors using the vector package fusion system. In particular, it automagically recognizes input vectors whose element types have a natural order-preserving injection into Int, converts them, and uses the specialized range-min implementation for Int vectors. See Data.RangeMin for more details.


Properties

Versions1.0, 1.0.1, 1.0.2, 1.0.3, 1.0.4, 1.0.5, 1.0.6, 1.1.0, 1.1.1, 1.1.2, 2.0, 2.1.0, 2.1.1, 2.1.2, 2.1.3, 2.1.4, 2.1.5, 2.2.0, 2.2.1, 2.2.2
Dependenciesbase (==4.*), containers (>=0.3.0.0), primitive (>=0.3), vector (>=0.6)
LicenseBSD3
AuthorLouis Wasserman
Maintainerwasserman.louis@gmail.com
CategoryAlgorithms
Upload dateSat May 22 04:27:20 UTC 2010
Uploaded byLouisWasserman
Downloads1003 total (88 in last 30 days)

Modules

Flags

NameDescriptionDefault
llvmCompiles with delicious, delicious LLVM goodness.Disabled
wallEnables warnings, with the exception of name shadowing.Enabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainers' corner

For package maintainers and hackage trustees