Introduction to SortedContainers

The sortedcontainers module in Python provides a fast and efficient way to handle sorted collections. It is a powerful library that maintains order in your data structures, ensuring optimal performance during insertions, deletions, and lookups. In this blog post, we will explore various useful APIs provided by the sortedcontainers library and present some code snippets to help you get started.

Installation

To install sortedcontainers, simply use pip:

pip install sortedcontainers

Basic Usage

Let’s start with some basic usage of the sortedcontainers library:

from sortedcontainers import SortedList, SortedDict, SortedSet

# Creating a SortedList
sl = SortedList([5, 1, 3, 2, 4])
print(sl)  # Output: SortedList([1, 2, 3, 4, 5])

# Creating a SortedDict
sd = SortedDict({'banana': 3, 'apple': 5, 'pear': 1})
print(sd)  # Output: SortedDict({'apple': 5, 'banana': 3, 'pear': 1})

# Creating a SortedSet
ss = SortedSet('abracadabra')
print(ss)  # Output: SortedSet(['a', 'b', 'c', 'd', 'r'])

API Examples

SortedList API

from sortedcontainers import SortedList

# Init with iterable
sl = SortedList([5, 1, 3, 2, 4])

# Add item
sl.add(6)
print(sl)  # Output: SortedList([1, 2, 3, 4, 5, 6])

# Remove item
sl.remove(3)
print(sl)  # Output: SortedList([1, 2, 4, 5, 6])

# Checking existence
print(2 in sl)  # Output: True

# Access by index
print(sl[2])  # Output: 4

SortedDict API

from sortedcontainers import SortedDict

sd = SortedDict()

# Setting items
sd['banana'] = 3
sd['apple'] = 5
sd['pear'] = 1

# Accessing items by key
print(sd['apple'])  # Output: 5

# Iterating keys
for key in sd:
  print(key, sd[key])  # Output: apple 5, banana 3, pear 1

# Deleting items
del sd['pear']
print(sd)  # Output: SortedDict({'apple': 5, 'banana': 3})

SortedSet API

from sortedcontainers import SortedSet

ss = SortedSet('abracadabra')

# Adding items
ss.add('z')
print(ss)  # Output: SortedSet(['a', 'b', 'c', 'd', 'r', 'z'])

# Removing items
ss.remove('a')
print(ss)  # Output: SortedSet(['b', 'c', 'd', 'r', 'z'])

# Checking existence
print('c' in ss)  # Output: True

Example Application: Task Scheduler

Let’s create a simple task scheduler using SortedList:

from sortedcontainers import SortedList
import time

class TaskScheduler:
    def __init__(self):
        self.tasks = SortedList()

    def add_task(self, task, priority):
        self.tasks.add((priority, task))

    def run(self):
        while self.tasks:
            priority, task = self.tasks.pop(0)
            task()
            time.sleep(priority)  # Simulate task duration

def task1():
    print("Running Task 1")

def task2():
    print("Running Task 2")

scheduler = TaskScheduler()
scheduler.add_task(task1, 2)
scheduler.add_task(task2, 1)
scheduler.run()

In this example, we use SortedList to maintain a list of tasks sorted by their priority. The TaskScheduler class can add tasks with priorities and run them in the correct order.

With sortedcontainers, managing sorted data becomes effortless, whether you need sorted lists, dictionaries, or sets. Its efficient implementation ensures that your data operations remain fast and reliable.

Hash: 0fd0bc884fcfdb33b522d5abe5edcb49ae9441b708d46f9e3229c7b5a02e1bf1