Python library for tries with different grades of fastness
Project description
py-fast-trie
py-fast-trie is a package that contains pure-Python implementations of an X-fast Trie and a Y-fast trie, as described in the foundational paper.
The most notable benefit of X-fast and Y-fast tries compared to more common data structures such as binary search trees is that searches are log-logarithmic in the cardinality of the universe as opposed to being logarithmic in the number of elements in the structure itself; For reference if you needed to store 2^20 items with a potential maximum value of 2^32 - 1, finding a particular item would take 20 operations in a red/black or AVL tree, but only 5 with an X-fast or Y-fast trie.
Usage
The interfaces of the X-fast and Y-fast tries are identical, the Y-fast trie is used here as an example
>>> from py_fast_trie import YFastTrie
>>> t = YFastTrie(max_length=32) # The library defaults to the machine's word size
>>> for i in range(10, 20):
... t += i # Value insertion/removal operations have intuitive
>>> t.min # shorthands
10
>>> t.max
19
>>> t < 14 # Predecessor/successor queries have intuitive
13 # shorthands
>>> t > 0
10
>>> t -= 19
>>> t > 19
>>>
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for py_fast_trie-1.0.0-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f41c045c7463131893c7369caa2ec9f24bd788d385c48b9c5dab13e3d4f03331 |
|
MD5 | f1e8ba112e00b0e3c67f819317ba97b7 |
|
BLAKE2b-256 | 6840829c60075d006032c72eba95855c909a0277b96f55358ee6f297b4d7dc65 |