rangetree 1.0

功能

• 支持开区间和闭区间

• 支持整数键

• 优化查找（非插入）

安装

要安装 rangetree，只需

$ pip install rangetree

使用方法

插入使用Python的切片表示法或使用范围对象完成。

>>> r = RangeTree()
>>> r[0:10] = 'single digits'
>>> r[range(10, 100)] = 'double digits'

支持负整数。

>>> r[-10:0] = 'negative singles'

缺少范围将导致 KeyError。请使用 Rangetree.get() 或 in 运算符。

>>> 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'

支持开区间（指向或从无穷大开始）。设置开区间只能使用切片表示法。

>>> r[1000:] = 'quadruple digits or more'
>>> r[999999999]
'quadruple digits or more'

重叠范围将导致 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 很快。使用 perf，给定2000个区间

$ 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 us

查找的大致数字在单个微秒以下。

变更日志

1.0 (2016-10-20)

首次公开发布。

贡献

欢迎贡献。可以使用 tox 运行测试，请在提交拉取请求之前确保覆盖率至少保持不变。

致谢

rangetree 的开发由 Nanobit 赞助。

rangetree 已由 David R. MacIver 使用 Hypothesis 进行测试。

rangetree 使用 perf 进行基准测试，由 Victor Stinner 完成。