DOCSEARCHbyAlgolia
Submit Docs

Sorted Containers

repository·master·Indexed 25 days ago

https://github.com/grantjenks/python-sortedcontainers

A pure-Python library providing Sorted List, Sorted Dict, and Sorted Set implementations. It is designed to provide efficient sorted collections that are as fast as C-extensions without requiring a C compiler. The library includes SortedList for mutable sequences, SortedDict for sorted key-value mappings, and SortedSet for sorted unique collections, all supporting logarithmic time lookups and custom sort keys.

Tokens
10.5K
Snippets
17
Records
79
Agent score
87%

What's inside sortedcontainers

  1. Overview of Sorted Containers API

    master

    The Sorted Containers library provides three main sorted collection types designed to be efficient and easy to use:

    • Sorted List (SortedList): A MutableSequence that maintains sort order. It supports bisect_left and bisect_right methods, and behaves similarly to a standard Python list but with enforced ordering.
    • Sorted Dictionary (SortedDict): A MutableMapping where iteration yields items in sorted order. It supports efficient positional indexing via an iloc view.
    • Sorted Set (SortedSet): A MutableSet that also acts as a Sequence to support efficient positional indexing.

  2. Overview of Sorted Containers features and APIs

    master

    Sorted Containers provides pure-Python, high-performance implementations of sorted sequences, mappings, and sets. It is compatible with both Python 2 and Python 3 and is optimized for speed, performing well on both CPython and PyPy.

    Key API Features

    Sorted Lists

    • Includes bisect methods for efficient searching and insertion.
    • Includes an islice method that implements slice indexing but returns an iterator.

    Sorted Dictionaries

    • Supports integer indexing.
    • Allows looking up the index of a key or bisecting keys within the mapping.
    • Includes an iloc attribute for positional indexing (similar to Pandas DataFrames).
    • Includes an irange method to iterate over ranges of keys.

    Sorted Sets

    • Fully supports positional indexing and lookup.

  3. Overview of Sorted Containers data types

    master

    The sortedcontainers library provides sorted variants of Python's three core collection types. These containers extend standard semantics to ensure elements remain sorted during mutating operations.

    Supported types include:

    • Sorted List: A sorted sequence.
    • Sorted Dictionary: A sorted mapping.
    • Sorted Set: A sorted set.

    All container types support a key parameter during initialization, which accepts a callable used to extract a comparison key from elements, similar to Python's built-in sorted() function.

  4. Understand the performance scaling of SortedList

    master

    The SortedList implementation uses a B-tree-like data structure limited to two levels of nodes to achieve high performance at scale. It is designed to handle tens of billions of items efficiently.

    Key performance characteristics:

    • Adding elements (SortedList.add): The amortized cost of adding an individual item is proportional to the cube root of n ($O(n^{1/3})$) or the square root of n ($O(n^{1/2})$), depending on the load factor. In practice, the default load is 1,000.
    • Deleting elements (SortedList.__delitem__): The amortized time complexity for deleting elements by index is also proportional to the cube root of n ($O(n^{1/3})$).

    While tree-based implementations offer $O(\log n)$ complexity, SortedList often outperforms them in practice due to lower constant factors and better memory locality, especially when the number of elements does not reach extreme theoretical limits.

  5. Understand runtime performance considerations

    master

    Since Sorted Containers is implemented in pure-Python, its performance is directly tied to the Python runtime being used:

    • CPython: The library is primarily developed and benchmarked on CPython 3.7. Performance is generally stable across CPython versions.
    • PyPy: Can be significantly faster (often 2x to 10x) once the Just-In-Time (JIT) compiler optimizes the code, though performance can show more variability during the optimization phase.

    Performance is also influenced by the internal load factor, which determines how many values are stored in each node of the segmented-list data structure.

  6. Understand Simulated Workload Patterns

    master

    The sortedcontainers library is optimized for several common real-world usage patterns. Use these patterns to determine if SortedList or SortedKeyList fits your use case:

    • Priority Queue: Requires efficient add and pop operations, the ability to test for value ownership (__contains__), occasional removal (discard), and linear-time sorted iteration.
    • Multiset: Requires efficient lookup of the greatest or least item, alongside add, remove, and __contains__ operations.
    • Ranking: Involves repeatedly looking up the index of items (index) and accessing items by position (__getitem__), often used to report the rank of an element in a queue.
    • Neighbor: Common in machine-learning (e.g., K-nearest-neighbor). Involves repeated bisection (bisect) to find values nearest to a target, combined with occasional add, remove, and iteration.
    • Intervals: Complex pattern involving maintaining intervals. Requires bisect to identify nearest intervals, range queries via __getitem__, frequent indexing, and add/discard operations.

  7. Understand Sorted Containers performance and scalability

    master

    Sorted Containers is designed for high performance and can handle datasets up to ten billion elements. The primary limiting factor for extremely large datasets is memory. For example, storing 100 million CPython integers in a SortedList requires approximately 3 GB of memory.

    Performance characteristics include:

    • Implementation: Pure-Python using a segmented-list data structure (similar to a B-tree limited to two levels).
    • Load Factor: Performance can be influenced by the load factor used to determine how many values are stored in each node.
    • Complexity: For set operations, Sorted Containers uses different algorithms based on the size of the right-hand-side operand to optimize performance.

  10. Migrate from other sorted container libraries

    master

    If you are migrating from other projects to Sorted Containers, note the following:

    From blist

    • pop() behavior: blist.pop() pops the first element by default. Sorted Containers' pop() pops the last element to match Python's built-in list API.
    • Views: Sorted Containers uses Python 3 semantics for dict views.

    From bintrees

    • Sorted Containers is the recommended successor. The Tree object in bintrees is most similar to SortedDict.
    • Slicing and iterator methods in bintrees correspond to SortedDict.irange() in Sorted Containers.

    From banyan

    • Sorted Containers does not support tree augmentation (used for interval/segment trees).
    • To implement hashing for mutable instances, you must manually inherit and define __hash__ (use with caution).

    General Version 1 to Version 2 Migration

    • SortedList changes: __setitem__, append, and extend now raise NotImplementedError. Use add() or update() instead.
    • SortedDict changes: keys(), items(), and values() now return optimized views. Use these methods directly for better performance.
    • Renaming: SortedListWithKey is now SortedKeyList (an alias remains). Many methods that used val now use value for readability.

  11. Run and plot performance benchmarks

    master

    To run benchmarks for SortedList, export the results to a text file, and then generate and save performance graphs, execute the following commands in sequence:

    1. Run the benchmark script and redirect output to a file.
    2. Run the plotting script using the generated file, specifying the container type and the --save flag.
    $ python -m tests.benchmark_sortedlist --bare > tests/results_sortedlist.txt
$ python -m tests.benchmark_plot tests/results_sortedlist.txt SortedList --save

  12. Access documentation via Python help()

    master

    You can inspect the modules, classes, and methods of sortedcontainers directly in your Python interpreter using the built-in help() function.

    import sortedcontainers
help(sortedcontainers)

from sortedcontainers import SortedDict
help(SortedDict)
help(SortedDict.popitem)