Runtime Performance Comparison¶
Because sortedcontainers is implemented in pure-Python, its performance depends directly on the Python runtime. SortedContainers was primarily developed, tested and benchmarked on CPython 2.7, specifically build:
Python 2.7.10 (default, Oct 15 2015, 09:48:56)
[GCC 4.2.1 Compatible Apple LLVM 7.0.0 (clang-700.0.72)] on darwin
Not all runtimes are created equal. The graphs below compare sortedcontainers running on the CPython 2.7, CPython 3.4 and PyPy 2.6 runtimes. The PyPy 2.6 runtime displays much more variability due to its JIT-ed nature. Once the just-in-time compiler optimizes the code, performance is often several to tens of times faster.
Performance of competing implementations are benchmarked against the CPython 2.7 runtime. An implementation performance comparison is also included with data from popular sorted container packages.
SortedContainers uses a segmented-list data structure similar to a B-tree limited to two levels of nodes. As part of the implementation, a load factor is used to determine how many values should be stored in each node. This can have a significant impact on performance and a load factor performance comparison is also provided.
Though these benchmarks exercise only one API repeatedly, an effort has also been made to simulate real-world workloads. The simulated workload performance comparison contains examples with comparisons to other implementations, load factors, and runtimes.
SortedList¶
Graphs comparing SortedList performance.
SortedDict¶
Graphs comparing SortedDict performance.
__contains__¶
Given a key at random, test whether the key is in the dictionary using SortedDict.__contains__.
