Skip to main content

Python library for tries with different grades of fastness.

Project description


GitHub Workflow Codecov Python Versions Package Version

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.

Source Distribution

py-fast-trie-2.1.2.tar.gz (17.9 kB view hashes)

Uploaded Source

Built Distribution

py_fast_trie-2.1.2-py3-none-any.whl (12.4 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page