Wikibooks

Python Programming/Sorted Container Types

< Python Programming

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

Retrieved from "https://en.wikibooks.org/w/index.php?title=Python_Programming/Sorted_Container_Types&oldid=3198895"