py-fast-trie

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, 13):
...     t += i					# Value insertion/removal operations have intuitive
>>> t.min					# shorthands
10
>>> t += b'\x0d'				# The library can handle byte strings less than the
>>> t.max					# max length by treating them as integers
13
>>> for val in t:
...     print val
10
11
12
13
>>> t < 12					# Predecessor/successor queries have intuitive
11						# shorthands
>>> t > 0
10
t -= 13
>>> t > 12
>>>