Python Programming/Sorted Container Types

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

Sorted Container Types[edit]

Python does not provide modules like C++'s set and map data types as part of its standard library. This is a concious decision on the part of Guido, 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. Several implementations are described here.

  • Python SortedContainers Module - Pure-Python implementation that is fast-as-C implementations. Implements sorted list, dict, and set data types. Testing includes 100% code coverage and hours of stress. Documentation includes full API reference, performance comparison, and contributing/development guidelines.
  • Python rbtree Module - Provides a fast, C-implementation for dict and set data types. Based on a red-black tree implementation.
  • Python treap Module - Provides a sorted dict data type. Uses a treap for implementation and improves performance using Cython.
  • Python bintrees Module - 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.
  • Python banyan Module - Provides a fast, C-implementation for dict and set data types.
  • Python skiplistcollections Module - Pure-Python implementation based on skip-lists providing a limited API for dict and set data types.
  • Python blist Module - Provides sorted list, dict and set data types based on the "blist" data type, a B-tree implementation. Implemented in Python and C.