rangetree 1.0

功能

• 支持打开和关闭范围
• 支持整数键
• 为查找优化（不是插入）

安装

要安装rangetree，只需：

$ pip install rangetree

用法

插入是使用python的切片表示法或range对象完成的。

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

支持负整数。

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

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

>>>1000inrFalse>>>r[1000]Traceback(mostrecentcalllast):File"<stdin>",line1,in<module>File"rangetree.py",line93,in__getitem__raiseKeyError(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(mostrecentcalllast):File"<stdin>",line1,in<module>File"rangetree.py",line58,in__setitem__raiseKeyError('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由Victor Stinner使用perf进行基准测试。