跳过基于列表的排序集合
skiplistcollections的Python项目详细描述
skip list collections是一个python模块，包含基于跳过列表的排序集合。skiplistcollections是用python编写的，并且可以使用：
- cpython 2.6+，3.2+
- Pypy 1.9+
github上的项目页：https://github.com/jstasiak/skiplistcollections
pypi上的项目页面：https://pypi.python.org/pypi/skiplistcollections
skiplistdict
SkipListDict是提供类似dict的接口并使用skip list实现的容器。它是按键永久排序的。
- 迭代容器（以任意键开始，支持反向排序）是o（n）
- 获取、设置和删除任意键的平均值为o（log n），最坏情况下为o（n）（退化跳过列表）
>>>fromskiplistcollectionsimportSkipListDict>>>things=SkipListDict(capacity=16)>>>len(things)0>>>things['x']=1>>>things.setdefault('x','DEFAULT')1>>>'x'inthingsTrue>>>len(things)1>>>things['g']=2>>>things['z']=3>>>tuple(things.keys())('g','x','z')>>>tuple(things.values())(2,1,3)>>>tuple(things.items())(('g',2),('x',1),('z',3))>>>tuple(things.items(start_key='x'))(('x',1),('z',3))>>>tuple(things.items(start_key='x',reverse=True))(('x',1),('g',2))>>>delthings['z']>>>things.update({'a':'A','b':'B'})>>>len(things)4>>>thingsSkipListDict({'a':'A','b':'B','g':2,'x':1},capacity=16)
如您所见，SkipListDict非常接近python dict接口。实际上它继承了MutableMapping抽象基类。
当然有区别：
- 在创建时，需要设置最大的DICT大小
- 尚不支持使用其他映射初始化
- 不能将“无”用作键
- items、keys和values是视图，接受start_key和reverse参数
技能集
SkipListSet使用跳过列表设置实现。它是按键永久排序的。
- 迭代容器是o（n）
>>>fromskiplistcollectionsimportSkipListSet>>>things=SkipListSet(capacity=16)>>>len(things)0>>>things.add(3)>>>len(things)1>>>things.add(1)>>>things.add(4)>>>thingsSkipListSet((1,3,4),capacity=16)>>>tuple(things)(1,3,4)>>>things.remove(2)Traceback(mostrecentcalllast):KeyError:2
更改
0.0.6
- 修复了SkipListDict的错误，该错误在未找到启动密钥时产生太多项（Github问题1）
0.0.5
- 修正了skiplistdict repr
- 已创建SkipListSet
0.0.4
- 在视图reprs中包括开始键和反转值
- 改进的自述文件
0.0.3
- items()，values()，keys()立即返回视图
0.0.2
- 改进的自述文件
版权所有
原始版本-版权所有（C）2013 David Wilson
版权所有（c）2013 Jakub Stasiak
此源代码是在mit许可下授权的，有关详细信息，请参阅许可文件。
欢迎加入QQ群-->： 979659372
