Python Programming/Sorted Container Types
Python does not provide modules for sorted set and dictionary data types as part of its standard library. This is a concious decision on the part of Guido van Rossum, et al. to preserve "one obvious way to do it." Instead, Python delegates this task to third-party libraries that are available on the Python Package Index. These libraries use various techniques to maintain list, dict, and set types in sorted order. Maintaining order using a specialized data structure can avoid very slow behavior (quadratic run-time) in the naive approach of editing and constantly re-sorting.
Third-party modules supporting sorted containers:
- SortedContainers - Pure-Python implementation that is fast-as-C implementations. Implements sorted list, dict, and set. Testing includes 100% code coverage and hours of stress. Documentation includes full API reference, performance comparison, and contributing/development guidelines. License: Apache2.
- rbtree - Provides a fast, C-implementation for sorted dict and set data types. Based on a red-black tree implementation.
- treap - Provides a sorted dict data type. Uses a treap for implementation and improves performance using Cython.
- bintrees - Provides several tree-based implementations for dict and set data types. Fastest implementations are based on AVL and Red-Black trees. Implemented in C. Extends the conventional API to provide set operations for dict data types.
- banyan - Provides a fast, C-implementation for dict and set data types.
- skiplistcollections - Pure-Python implementation based on skip-lists providing a limited API for dict and set data types.
- blist - Provides sorted list, dict and set data types based on the "blist" data type, a B-tree implementation. Implemented in Python and C.
External links
[edit | edit source]- SortedContainers, pypi.python.org
- rbtree, pypi.python.org
- treap, pypi.python.org
- bintrees, pypi.python.org
- Banyan, pypi.python.org
- skiplistcollections, pypi.python.org
- blist, pypi.python.org