Features and Specifications

Sorted Containers offers a remarkable set of features that differentiate it from other libraries:

• Pure-Python implementation.
• Comprehensive documentation.
• Benchmark comparisons with alternative implementations, runtimes, and load factors.
• Complete test coverage.
• Extensive stress testing for reliability.
• Performance that often exceeds that of C implementations.
• An API that closely resembles older blist and bintrees modules.
• A feature-rich API supporting operations like retrieving ranges of keys/values.
• Pragmatic design, such as SortedSet functioning as a Python set with a SortedList index.
• Developed and maintained for Python 3.10.
• Extensively tested on CPython versions 3.7 through 3.10 and PyPy3.
• Verified compatibility across Linux, Mac OSX, and Windows operating systems.

Quickstart Guide

Getting started with Sorted Containers is seamless thanks to Python's pip package manager. Just run:

$ pip install sortedcontainers

You can then begin using sorted containers in your Python code! Moreover, Sorted Containers has excellent documentation available directly from the Python interpreter through the built-in help function:

>>> import sortedcontainers
>>> help(sortedcontainers)

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

This feature makes it easy to explore the library's capabilities and quickly locate the information you need.

With its robust features, established performance, and simple integration, it's no wonder Sorted Containers has become the preferred choice for sorted data structures within the Python community. Whether you're developing a large-scale distributed system, analyzing intricate datasets, or simply require a dependable and efficient method to keep your data organized, Sorted Containers is the answer.

The first video titled "The Sorted Containers in Python | SortedSet | SortedList | SortedDict" provides an overview of sorted containers and their applications.

Here's a more detailed code snippet showcasing the basic usage of each sorted container type:

from sortedcontainers import SortedList, SortedSet, SortedDict

# SortedList sl = SortedList([3, 1, 4, 1, 5]) sl.add(2) print(sl) # SortedList([1, 1, 2, 3, 4, 5])

# SortedSet ss = SortedSet([3, 1, 4, 1, 5]) ss.add(2) print(ss) # SortedSet([1, 2, 3, 4, 5])

# SortedDict sd = SortedDict({'c': 3, 'a': 1, 'b': 2}) sd['d'] = 4 print(sd) # SortedDict({'a': 1, 'b': 2, 'c': 3, 'd': 4})

# Get the 3 smallest keys in a SortedDict print(sd.keys()[:3]) # ['a', 'b', 'c']

This example illustrates the creation and manipulation of each sorted container type, as well as a simple use case for the SortedDict's capability to efficiently retrieve a range of keys.

The compatibility of the Sorted Containers API with other well-known sorted container libraries like blist and bintrees is also a significant benefit, facilitating an easy transition to Sorted Containers without extensive code refactoring.

The fact that Sorted Containers is a pure-Python solution, thoroughly documented, and rigorously tested across multiple Python versions and platforms makes it a reliable choice for projects of any scale. Its performance characteristics, frequently exceeding even C implementations, further contribute to its popularity.

Understanding the Power of Sorted Containers

At the core of sorted containers are three essential data structures:

1. Sorted Lists: Standard Python lists preserved in sorted order.
2. Sorted Sets: Sets that are implemented as sorted lists, uniting set operations with sorted order.
3. Sorted Dicts: Dictionaries that maintain sorted keys, allowing for key-based lookup alongside sorted traversal.

The main advantages of using sorted containers include:

• Enhanced performance for lookup, insertion, and deletion due to sorted order.
• More efficient memory usage by eliminating the need for additional indexing.
• Simplified code that is easier to read, test, and maintain.
• Streamlined deployment without the burden of external dependencies.

By selecting the appropriate sorted container for your specific use case, you can achieve substantial performance improvements and simplify your code with minimal developer effort. Let's explore each one in greater detail.

Sorted Lists: Fast Ordered Sequences

The simplest sorted container is the sorted list, which maintains its elements in ascending or descending order based on a comparison function. Here’s a straightforward example:

from sortedcontainers import SortedList

sl = SortedList([3, 1, 4, 1, 5]) print(sl) # SortedList([1, 1, 3, 4, 5])

Sorted lists exhibit O(log n) time complexity for insertions, deletions, and lookups, making them significantly faster than the O(n) lookups associated with regular lists. This performance advantage becomes especially apparent with larger datasets.

Some common applications for sorted lists include:

• Maintaining a leaderboard or high score table in gaming.
• Implementing a priority queue.
• Tracking a sorted stream of data, such as stock prices or sensor readings.

Sorted Sets: Combining Uniqueness and Order

Sorted sets maintain the uniqueness characteristic of Python's built-in set type while also keeping elements in sorted order, similar to a sorted list. This merges the performance benefits of both data structures. Here’s an example:

from sortedcontainers import SortedSet

ss = SortedSet([3, 1, 4, 1, 5]) print(ss) # SortedSet([1, 3, 4, 5])

Sorted sets have the same O(log n) performance as sorted lists for insertions, deletions, and lookups, while also supporting additional set operations like unions and intersections.

Ideal use cases for sorted sets encompass:

• Tracking unique values in sorted order, such as user IDs or product SKUs.
• Efficiently verifying membership in extensive sorted datasets.
• Simplifying set operations that depend on element ordering.

Sorted Dicts: Combining Mapping and Ordering

Sorted dictionaries preserve key-value pairs like standard Python dictionaries but store the keys in sorted order. This allows for value lookups by key and iterating over the keys or items in sorted order. Here’s an example:

from sortedcontainers import SortedDict

sd = SortedDict({'cat': 2, 'dog': 1, 'bird': 3}) print(sd) # SortedDict({'bird': 3, 'cat': 2, 'dog': 1})

print(sd['cat']) # 2 print(list(sd)) # ['bird', 'cat', 'dog']

Sorted dictionaries provide O(log n) lookup performance, making them suitable for large mapping scenarios. Some optimal applications include:

• Creating indexes that need to be searched and maintained in sorted key order.
• Building LRU caches with fast lookups and easy sorted access to the oldest/newest entries.
• Storing configuration data that requires stable iteration order.

The sorted order of the keys also facilitates powerful operations such as efficient nearest-key lookups and range queries.

Sorted Container Performance Comparison

To demonstrate the performance advantages of sorted containers, let’s compare them with their unsorted counterparts for various common operations using the timeit module.

First, we will examine lookups in a list versus a sorted list:

from timeit import timeit

def reg_list_lookup():

lst = list(range(10000))

return 9999 in lst

def sorted_list_lookup():

slst = SortedList(range(10000))

return 9999 in slst

print(f"Regular list lookup: {timeit(reg_list_lookup, number=1000):.3f} sec") print(f"Sorted list lookup: {timeit(sorted_list_lookup, number=1000):.3f} sec")

The output may look like this:

Regular list lookup: 0.956 sec Sorted list lookup: 0.004 sec

This example highlights that lookups in a sorted list are over 200 times quicker than in a regular list for this dataset size.

We can observe similar improvements for set membership testing:

def reg_set_membership():

s = set(range(10000))

return 9999 in s

def sorted_set_membership():

ss = SortedSet(range(10000))

return 9999 in ss

print(f"Regular set membership: {timeit(reg_set_membership, number=1000):.3f} sec") print(f"Sorted set membership: {timeit(sorted_set_membership, number=1000):.3f} sec")

The output may indicate:

Regular set membership: 0.001 sec Sorted set membership: 0.004 sec

Here, the sorted set membership test matches the speed of a regular set, illustrating that the sorted order does not impede performance.

Finally, let's compare key lookups in a dictionary versus a sorted dictionary:

def reg_dict_lookup():

d = {i: i for i in range(10000)}

return d[9999]

def sorted_dict_lookup():

sd = SortedDict({i: i for i in range(10000)})

return sd[9999]

print(f"Regular dict lookup: {timeit(reg_dict_lookup, number=1000):.3f} sec") print(f"Sorted dict lookup: {timeit(sorted_dict_lookup, number=1000):.3f} sec")

The output will typically show:

Regular dict lookup: 0.001 sec Sorted dict lookup: 0.006 sec

While the sorted dictionary lookup is slightly slower than a regular dictionary, it remains fast for most applications. The ability to iterate over the keys in sorted order often compensates for this minor performance difference.

Real-World Example: Building a Leaderboard

To illustrate a practical application of sorted containers, let’s examine how to construct a leaderboard for a game using a sorted dictionary:

from sortedcontainers import SortedDict

scores = SortedDict()

def add_score(player, score):

scores[player] = max(scores.get(player, 0), score)

def get_leaderboard():

return [(p, s) for p, s in scores.items()]

add_score('Alice', 500) add_score('Bob', 750) add_score('Carol', 600) add_score('Alice', 800)

print(get_leaderboard()) # [('Alice', 800), ('Bob', 750), ('Carol', 600)]

Using a sorted dictionary simplifies maintaining the leaderboard in sorted order by score. It allows for efficient score updates, adding new players, and retrieving current rankings.

In contrast, using a regular dictionary would require an additional sorting step every time the leaderboard is accessed:

scores = {}

def add_score(player, score):

scores[player] = max(scores.get(player, 0), score)

def get_leaderboard():

return sorted(scores.items(), key=lambda x: x[1], reverse=True)

add_score('Alice', 500) add_score('Bob', 750) add_score('Carol', 600) add_score('Alice', 800)

print(get_leaderboard()) # [('Alice', 800), ('Bob', 750), ('Carol', 600)]

While this method works, it necessitates extra sorting, which becomes inefficient for larger leaderboards with frequent updates. Utilizing a sorted dictionary greatly enhances efficiency.

Real-World Usage

Sorted Containers have demonstrated their value in various real-world applications. They are employed in several prominent open-source projects, such as:

• Zipline, an algorithmic trading library from Quantopian.
• Angr, a binary analysis platform from UC Santa Barbara.
• Trio, an asynchronous I/O library.
• Dask Distributed, a computation library supported by Continuum Analytics.

The adoption of Sorted Containers by these noteworthy projects highlights its performance, reliability, and effectiveness in addressing complex challenges at scale.

Key Takeaways

• Sorted containers deliver rapid O(log n) performance for insertions, deletions, and lookups.
• Sorted lists are excellent for ordered sequences, sorted sets are ideal for unique elements, and sorted dicts are perfect for mapping keys to values.
• Utilizing sorted containers can significantly enhance your code's speed and simplify deployment compared to unsorted alternatives.
• Real-world applications include leaderboards, priority queues, uniqueness checks, and beyond.
• Sorted Containers are battle-tested in high-profile projects like Zipline, Angr, Trio, and Dask Distributed.
• The library offers a rich set of features, including pure-Python code, comprehensive documentation, complete test coverage, and cross-platform compatibility.
• Installation and initial setup with Sorted Containers is straightforward with pip and interactive documentation.

Conclusion

Sorted containers can serve as a powerful asset in enhancing the performance and clarity of your Python code. By utilizing the efficient, ordered data structures provided by the sortedcontainers module, you can accelerate your code, minimize memory usage, and create programs that are easier to read and maintain.

Whether you're employing sorted lists for fast ordered sequences, sorted sets for effective set operations on unique elements, or sorted dicts for mapping keys to values with sorted key ordering, mastering how and when to use sorted containers is a crucial skill for any Python developer striving for excellence.

So the next time you're engaged in a project that could benefit from sorted data, consider giving sorted containers a try. You may be amazed at how significantly they can simplify and enhance your code!

The second video titled "Sorting lists of dictionaries in Python" provides insights on sorting techniques for more complex data structures.