rangemin: Linear range-min algorithms.
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.
Flags
Automatic Flags
Name | Description | Default |
---|---|---|
llvm | Compiles with delicious, delicious LLVM goodness. | Disabled |
wall | Enables 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
- rangemin-2.2.2.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 1.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 |
---|---|
Dependencies | base (>=4 && <5), containers (>=0.3.0.0), primitive (>=0.3), vector (>=0.6) [details] |
Tested with | ghc >=0 |
License | BSD-3-Clause |
Author | Louis Wasserman |
Maintainer | wasserman.louis@gmail.com |
Category | Algorithms |
Uploaded | by LouisWasserman at 2010-05-31T18:17:54Z |
Distributions | |
Reverse Dependencies | 1 direct, 0 indirect [details] |
Downloads | 14071 total (3 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs uploaded by user Build status unknown [no reports yet] |