Python Programming/Sorted Container Types

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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]