快速、纯python可索引跳过列表
pyskiplist的Python项目详细描述
pyskiplist是可转位skiplist的快速、纯python实现。它 实现一个SkipList数据结构，该结构提供始终排序的， （键，值）对的类似列表的数据结构。它有效地支持 以下操作：
- 在列表中插入一对，保持排序顺序。
- 找到给定密钥的值。
- 基于密钥移除给定对。
- 按排序顺序遍历所有对。
- 找到给定键的位置。
- 在某个位置接近一对。
- 在某个位置删除一对。
因为pyskiplist是一个纯python实现，所以它应该在 pypy和jython等其他python实现。
示例
下面提供一些关于如何使用SkipListapi的示例：
>>> from pyskiplist import SkipList
>>> sl = SkipList()
>>> sl.insert('foo', 'bar')
>>> sl.insert('baz', 'qux')
>>> sl
SkipList((('baz', 'qux'), ('foo', 'bar')))
>>> sl.search('foo')
'bar'
>>> sl[0]
('baz', 'qux')
>>> sl.remove('foo') # remove by key
>>> del sl[0] # remove by position
渐近复杂度
下面是由不同的操作实现的大O复杂度 Pyskiplist:
| Operation | Complexity |
|---|---|
| insertion | O(log N) |
| search by key | O(log N) |
| removal by key | O(log N) |
| forward iteration | O(1) |
| find by position | O(log N) |
| access by position | O(log N) |
| delete by position | O(log N) |
性能
下面是一些性能测试的结果。这些是针对python 3.4.2的 我的Linux笔记本电脑：
| Test | Operations / second |
|---|---|
| Insert @ 1k nodes | 45,056 |
| Insert @ 10k nodes | 42,137 |
| Insert @ 100k nodes | 28,086 |
| Remove @ 1k nodes | 54,316 |
| Remove @ 10k nodes | 46,240 |
| Remove @ 100k nodes | 35,114 |
| Search @ 1k nodes | 137,248 |
| Search @ 10k nodes | 109,480 |
| Search @ 100k nodes | 77,939 |
内存使用量
Pyskiplist试图提高内存使用效率。数字 下面是我的Linux笔记本电脑上的Python3.4.2。此特定测试存储对 在SkipList中的整数键和整数值。两者的总尺寸 这个python版本的整数是56字节。
| Nodes | Bytes / node | Overhead (fixed) |
|---|---|---|
| 1k | 164 | 108 |
| 10k | 162 | 106 |
| 100k | 162 | 106 |
实施说明
关于技巧的参考论文：
- ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf（原纸）
- http://drum.lib.umd.edu/bitstream/1903/544/2/CS-TR-2286.1.pdf（食谱）
这个实现使用了一种新的（据我所知）技术来存储 每个节点只有一个链接宽度，并且仅在级别为>；0的节点中。链接 对应于最高传入链接跳过的节点数。其他 我看到的所有实现都为每个链接存储一个宽度。这种方法 节省了很多内存。开销应该是1/e（0.37）整数/ 节点。它使一个可转位的技巧家的内存效率几乎与它的 不可转位的表亲。
此实现中允许重复键，插入顺序为 保持。
SkipList节点实现为普通列表而不是对象。这节省了 记忆。感谢http://pythonsweetness.tumblr.com/post/45227295342为 想法。
内置的梅森捻线机用作随机源。这样比较好 因为它不需要系统调用也不需要 用于加密安全数字。
欢迎加入QQ群-->： 979659372
