Skip to main content

Python library for tries with different grades of fastness

Project description


GitHub Workflow 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 2.0.1
Filename, size File type Python version Upload date Hashes
Filename, size py_fast_trie-2.0.1-py3-none-any.whl (14.7 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size py-fast-trie-2.0.1.tar.gz (19.6 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page