Bug#973753: ITP: nim-lapper -- simple, fast interval searches for nim
Package: wnpp
Severity: wishlist
Subject: ITP: nim-lapper -- simple, fast interval searches for nim
Package: wnpp
Owner: Steffen Moeller <moeller@debian.org>
Severity: wishlist
* Package name : nim-lapper
Version : 0.1.6+git20200609.d82bbc7
Upstream Author : Brent S. Pedersen
* URL : https://github.com/brentp/nim-lapper
* License : Expat
Programming Lang: (C, C++, C#, Perl, Python, etc.)
Description : simple, fast interval searches for nim
This package uses a binary search in a sorted list of intervals along
with knowledge of the longest interval. It works when the size of the
largest interval is smaller than the average distance between intervals.
As that ratio of largest-size::mean-distance increases, the performance
decreases. On realistic (for my use-case) data, this is 1000 times
faster to query results and >5000 times faster to check for presence
than a brute-force method.
.
Lapper also has a special case `seek` method when we know that the
queries will be in order. This method uses a cursor to indicate that
start of the last search and does a linear search from that cursor to
find matching intervals. This gives an additional 2-fold speedup over
the `find` method.
Remark: This package is maintained by Steffen Moeller at
https://salsa.debian.org/med-team/nim-lapper
Reply to: