skiplistcollections 0.0.6

跳表字典

SkipListDict 是一个提供类似于字典的接口并使用跳表实现的容器。它按键永久排序。

• 遍历容器（从任何键开始，支持逆序）是 O(n)

• 获取、设置和删除任意键的平均时间为 O(log n)，最坏情况下的时间为 O(n)（退化的跳表）

有关详细信息，请参阅 http://pythonsweetness.tumblr.com/post/45227295342/fast-pypy-compatible-ordered-map-in-89-lines-of-python

>>> from skiplistcollections import SkipListDict
>>> things = SkipListDict(capacity=16)
>>> len(things)
0
>>> things['x'] = 1
>>> things.setdefault('x', 'DEFAULT')
1
>>> 'x' in things
True
>>> 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))
>>> del things['z']
>>> things.update({'a': 'A', 'b': 'B'})
>>> len(things)
4
>>> things
SkipListDict({'a': 'A', 'b': 'B', 'g': 2, 'x': 1}, capacity=16)

如您所见，SkipListDict 非常接近Python字典接口。事实上，它继承了 MutableMapping 抽象基类。

当然也有一些差异

• 在创建时需要设置最大字典大小

• 尚未支持使用其他映射进行初始化

• 不能使用None作为键

• items、keys 和 values 是视图，并接受 start_key 和 reverse 参数

跳表集

SkipListSet 是使用跳表实现的集合。它永久按键排序。

• 迭代容器的时间复杂度为 O(n)

• 添加、删除以及检查键是否存在于容器中的平均时间复杂度为 O(log n)，最坏情况为 O(n)（跳表退化为链表）

>>> from skiplistcollections import SkipListSet
>>> things = SkipListSet(capacity=16)
>>> len(things)
0
>>> things.add(3)
>>> len(things)
1
>>> things.add(1)
>>> things.add(4)
>>> things
SkipListSet((1, 3, 4), capacity=16)
>>> tuple(things)
(1, 3, 4)
>>> things.remove(2)
Traceback (most recent call last):
KeyError: 2

变更

版权

原始版本 - 版权所有 (C) 2013 David Wilson

版权所有 (C) 2013 Jakub Stasiak

本源代码遵循 MIT 许可协议，详情请参阅 LICENSE 文件。