Skip to main content

Python library for tries with different grades of fastness

Project description


Travis Codecov Python Versions Package Version License

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.


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

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for py-fast-trie, version 1.0.1
Filename, size File type Python version Upload date Hashes
Filename, size py_fast_trie-1.0.1-py2.py3-none-any.whl (14.1 kB) File type Wheel Python version py2.py3 Upload date Hashes View hashes
Filename, size py-fast-trie-1.0.1.tar.gz (16.8 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page