Quick lookups of values in numeric ranges.
Project description
rangetree is an Apache2 licensed library, written in Python 3, for easy and fast lookups of numeric ranges.
Given three integer ranges, 0 - 9, 10 - 99, and 100 - 999, rangetree makes it trivial to look up exactly which range any integer falls in. (Note Python slices and ranges include the first index, and exclude the second.)
>>> from rangetree import RangeTree
>>>
>>> r = RangeTree()
>>> r[0:10] = 'single digits'
>>> r[10:100] = 'double digits'
>>> r[100:1000] = 'triple digits'
>>>
>>> r[4]
'single digits'RangeTree s are optimized for lookups, and make use of the excellent bintrees library.
Features
supports open and closed ranges
supports integer keys
optimized for lookups (not insertions)
Installation
To install rangetree, simply:
$ pip install rangetreeUsage
Insertion is done using Python’s slice notation, or using range objects.
>>> r = RangeTree()
>>> r[0:10] = 'single digits'
>>> r[range(10, 100)] = 'double digits'Negative integers are supported.
>>> r[-10:0] = 'negative singles'Missing a range will result in a KeyError. Use Rangetree.get() or the in operator.
>>> 1000 in r
False
>>> r[1000]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "rangetree.py", line 93, in __getitem__
raise KeyError(key)
KeyError: 1000
>>> r.get(1000, 'no value')
'no value'Open ranges (that go to or from infinity) are supported. Setting open ranges is only possible using the slice notation.
>>> r[1000:] = 'quadruple digits or more'
>>> r[999999999]
'quadruple digits or more'Overlapping ranges will result in a KeyError.
>>> r = RangeTree()
>>> r[1000:] = 'quadruple digits or more'
>>> r[10000:] = 'ten thousand'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "rangetree.py", line 58, in __setitem__
raise KeyError('Overlapping intervals.')
KeyError: 'Overlapping intervals.'rangetree is fast. Using perf, given 2000 intervals:
$ pyperf timeit --rigorous -g --duplicate 5 -s "from rangetree import RangeTree; r = RangeTree()" -s "for i in range(2000):" -s " r[i*10:i*10+10] = i" "r[500]"
.........................................
3.75 us: 1 #######
3.77 us: 2 #############
3.80 us: 9 ###########################################################
3.82 us: 5 #################################
3.84 us: 8 #####################################################
3.86 us: 9 ###########################################################
3.89 us: 7 ##############################################
3.91 us: 8 #####################################################
3.93 us: 8 #####################################################
3.95 us: 6 ########################################
3.98 us: 10 ##################################################################
4.00 us: 12 ###############################################################################
4.02 us: 5 #################################
4.05 us: 9 ###########################################################
4.07 us: 5 #################################
4.09 us: 6 ########################################
4.11 us: 3 ####################
4.14 us: 4 ##########################
4.16 us: 2 #############
4.18 us: 0 |
4.20 us: 1 #######
Median +- std dev: 3.97 us +- 0.11 usThe ballpark figure for lookups is in the single digit microseconds.
Changelog
1.0 (2016-10-20)
Initial public release.
Contributing
Contributions are very welcome. Tests can be run with tox, please ensure the coverage at least stays the same before you submit a pull request.
Credits
The development of rangetree is sponsored by Nanobit.
rangetree is tested with Hypothesis, by David R. MacIver.
rangetree is benchmarked using perf, by Victor Stinner.
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
