pyradixtree 0.0.1

pyradixtree, a python radix tree implementation

简介

pyradixtree库是完全使用Python编写的一种基数树实现，其参考了Redis中的基数树实现RAX, an ANSI C radix tree implementation并扩展了部分内容。 由于纯Python实现与C实现性能存在数量级差距，且为了实现方便，节点所占内存保有优化空间，此库仅可用于练习使用。

环境要求

库运行：
Python解释器版本 >= 3.8

测试代码运行：
需安装库 Pytest,StringGenerator

基本用法

模块仅提供类RadixTree，它继承自MutableMapping并实现了全部接口，是自定义的映射类型，使用类似于只支持str类型键的Dict。 安装：

pip install pyradixtree

使用：

from pyradixtree import RadixTree

rax = RadixTree()
keys = ['a', 'b', 'c']
for i, key in enumerate(keys):
    rax[key] = i

# a 0
# b 1
# c 2
for key in rax:
    print(key, rax[key])

del rax['a']
print('a' not in rax)  # True

功能

RadixTree支持了Dict支持的所有操作，详情可参考内置类型: Dict。

下面列举了RadixTree支持的全部操作：

• rax[key] 返回基数树中key对应节点存放的值，若key不存在则引发KeyError。

• rax[key] = value 将key对应节点的值设为value。

• del rax[key] 将key对应节点从基数树中删除，若key不存则引发KeyError。

• key in rax | key not in rax 判断key是否存在于基数树中。

• list(rax) 返回基数树中全部键组成的列表(有序)。

• len(rax) 返回基数树的元素数量(键个数)。

• iter(rax) 返回以基数树的键为元素的迭代器(保证字典升序)，效果同iter(rax.keys())。

• reversed(rax) 返回一个以基数树的键为元素的逆序迭代器(字典序倒序)。

• rax.clear() 删除基数树中全部元素。

• rax.copy() 返回基数树的浅拷贝。

• classmethod fromkeys(iterable[,value]) 使用可迭代的iterable作为键创建一个新基数树，并将键值都设为value(默认为None)。

• get(key[,default]) 如果key存在则返回对应节点存放的值，否则返回default(默认为None)。

• rax.keys() 返回由基数树全部的键组成的视图对象。

• rax.values() 返回由基数树全部的元素值组成的视图对象。

• rax.items() 返回由基数树全部的键值对组成的视图对象。

• rax.pop() 如果key存在则删除对应节点并返回值，否则返回default。若default未给出且key不存在则引发KeyError。

• rax.popitem() 从基数树中删除一个键节点并返回键值对，返回顺序由键字典序决定。

• rax.setdefault(key[,default]) 如果key存在则返回对应节点的值，否则插入值为default的键key并返回default(默认为None)。

• rax.update([other]) 使用来自other的键值对更新基数树，若键原本存在则更新值。它接收一个字典对象或包含键值对的可迭代对象，如果给出关键字参数则会以此更新字典：rax.update(a=1, b=2)。

另外，两个RadixTree之间支持==比较，当二者键值对完全相同时等式成立。

测试运行

测试使用pytest框架运行，使用StringGenrator库来随机生成字符串

运行全部测试：
pip install pytest, StringGenrator
pytest -vs

根据测试标记过滤用例：fuzz/unit/benchmark
pytest -vs -m fuzz
pytest -vs -m unit
pytest -vs -m benchmark
其中benchmark测试未使用pytest-benchmark插件

生成覆盖率报告
pip install pytest-cov
pytest -vs --cov --cov-report=html

存在的问题

1. 使用纯Python实现，性能较C库相差数量级的差距，仅可作为“玩具”使用。
2. 仅就Python来说，对于节点中出边、入边和父节点的存储存在较大优化空间，目前是为了方便实现，实际内存开销可能还不如其它映射数据结构，也就失去了使用基数树的意义。
3. 节点间存在循环引用的问题，GC回收性能可能受影响。