DEV Community: Yasir Jafri

Sorted Data Structures in Python

Yasir Jafri — Fri, 27 Dec 2024 17:15:31 +0000

Sorted data structures play a critical role in optimizing search, insertion, and deletion operations while maintaining order. Python provides a variety of tools and libraries to work with such structures, offering efficient solutions for numerous real-world problems. We'll cover the following ones:

Heaps.
Sorted lists.
Sorted dictionaries.
Sorted sets.

`heapq` Module

For a robust implementation of a heap data structure (specifically a min-heap), Python's standard library provides built-in support. The heapq module provides a heap-based priority queue implementation. It uses a binary heap to maintain partial order, making it ideal for scenarios requiring repeated access to the smallest (or largest) element.

Example:

import heapq

heap = [3, 1, 4]
heapq.heapify(heap)
heapq.heappush(heap, 2)
print(heap)  # Output: [1, 2, 4, 3]

smallest = heapq.heappop(heap)
print(smallest)  # Output: 1

Refer to the official documentation for a comprehensive list of available operations and additional examples.

`sortedcontainers` Module

The sortedcontainers module provides dynamic sorted data structures that adjust automatically as elements are added or removed. This library is highly efficient and easy to use.

`SortedList`:

Maintains a sorted list with dynamic ordering.

from sortedcontainers import SortedList

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

It also accepts a key parameter, similar to the one used in the sorted() function.

from sortedcontainers import SortedList
from operator import neg

sl = SortedList([3, 1, 4], key=neg)
print(sl)  # Output: [4, 3, 1]

Note: SortedList supports almost all the methods of mutable sequences except a few which are not supported and will raise not-implemented error.

`SortedDict`:

A dictionary with keys maintained in sorted order. The design of sorted dict is simple: sorted dict inherits from dict to store items and maintains a sorted list of keys.

Sorted dict keys must be hashable and comparable. The hash and total ordering of keys must not change while they are stored in the sorted dict.

from sortedcontainers import SortedDict

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

`SortedSet`:

A set that ensures its elements are sorted.

from sortedcontainers import SortedSet

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

As with SortedList, SortedSet also accepts a key parameter which can be used in the same way.

Trade-offs of Sorted Data Structures

While sorted data structures offer significant advantages, they come with trade-offs:

Insertion/Deletion Overhead: Maintaining order during these operations may increase computational cost compared to unsorted structures.
Memory Overhead: Some implementations may use additional memory for indexing or maintaining order.

Conclusion

Sorted data structures are indispensable tools for optimizing applications requiring dynamic order maintenance. Although developers should be easily able to implement these data structures, it's nice to have these robust implementations readily available which can be uses right-off the bat without having a nightmare about a corner-case in a service that is deployed in production. Python’s built-in libraries and third-party modules like sortedcontainers provide versatile and efficient solutions for a wide array of problems. By understanding their strengths and trade-offs, you can select the right tools to build performant and scalable applications.

Concurrency Patterns: Balking Pattern

Yasir Jafri — Tue, 24 Dec 2024 18:52:52 +0000

Introduction

The Balking Design Pattern is a behavioral design pattern used to manage state-dependent actions in a system. It ensures that operations are executed only when the system is in an appropriate state. If the required precondition is not met, the operation is aborted or the system "balks". For those like me, who don't know what Balking is, this is what google has to say about it: "hesitate or be unwilling to accept an idea or undertaking". This pattern is particularly useful in multithreaded environments or systems where invalid actions could cause conflicts or errors.

Balking pattern is also considered more of an anti-pattern than a design pattern by some people in the community. If an object cannot support its API, it should either limit the API so that the offending call is not available, or so that the call can be made without limitation. This is an old pattern which seems to have arisen when JVMs were slower and synchronization wasn't as well understood and implemented as it is today. Regardless it is worth discussing and whether to use it or not is upto the developers.

The Balking Pattern relies on three fundamental concepts

Guard Condition: A condition that must be satisfied for an operation to proceed.
State-Dependent Actions: Operations that depend on the current state of the system.
Thread Safety: The pattern often uses locks or other synchronization mechanisms to ensure safety in concurrent environments.

Let's understand these with an example:

A printing system demonstrates the Balking Pattern:

Scenario: A printer can only process one print request at a time. Even though multiple processes can place the print request.
Guard Condition: The printing must not be actively "printing" to handle a new print request.
Behavior: If the printer is busy, the system balks and does not proceed with the new print requests.

Note: Yeah, we can handle this using a queue, but let's assume for now we don't know that such an elegant data structure exists.

import threading
import time

class Printer:
    def __init__(self):
        self.state = "idle"
        self.lock = threading.Lock()

    def start_printing(self, job_id):
        print(f"Attempting to start Print Job {job_id}...")

        with self.lock:  # Ensure thread safety
            if self.state == "printing":
                print(f"Balking: Print Job {job_id} cannot start. Printer is busy.")
                return
            self.state = "printing"

        # Simulate the printing process
        print(f"Print Job {job_id} started.")
        time.sleep(3)
        print(f"Print Job {job_id} completed.")

        with self.lock:
            self.printing = "idle"

# Multiple threads attempting to start print jobs
printer = Printer()

threads = [
    threading.Thread(target=printer.start_printing, args=(1,)),
    threading.Thread(target=printer.start_printing, args=(2,))
]

for t in threads:
    t.start()

for t in threads:
    t.join()

Looking at the code we can see that if we send a print request start_printing to the printer and the printer is busy it will check it's current state self.state and if the state is "printing", it will return without doing anything. Otherwise, it will take up that request and adjust its state accordingly.

When to Use the Balking Pattern

Multithreaded Systems: To prevent race conditions or invalid operations.
State-Dependent Workflows: When actions are permissible only in certain states.
Resource Management: To guard against improper use of shared resources. Objects that use this pattern are generally only in a state that is prone to balking temporarily but for an unknown amount of time. If objects are to remain in a state which is prone to balking for a known, finite period of time, then the guarded suspension pattern may be preferred.

Advantages of the Balking Pattern

Prevents Invalid Operations: Guards ensure operations occur only under valid conditions.
Thread Safety: Particularly useful in multithreaded systems.
Simplifies Logic: Encapsulates state-dependent actions into a clear, reusable pattern.

Disadvantages

Limited Applicability: Most useful when actions are binary (allowed or not allowed).
Potential Overhead: Guard checks and synchronization mechanisms can introduce performance costs.

Conclusion

The Balking Design Pattern provides an effective way to manage state-dependent actions and prevent invalid operations in software systems. By introducing clear guard conditions and ensuring thread safety, it enhances the reliability and maintainability of the system. Whether it's preventing multiple trips in a cab booking system or managing concurrent print jobs, the Balking Pattern offers a structured approach to avoid conflicts and maintain operational integrity. Ultimately, the choice to use the Balking Pattern depends on the specific requirements of your application and its concurrency needs.

References

Concurrency Patterns: Active Object

Yasir Jafri — Sun, 22 Dec 2024 18:59:09 +0000

Introduction

The Active Object Pattern is a concurrency design pattern that decouples method execution from method invocation. The primary goal of this pattern is to introduce asynchronous behavior by executing operations in a separate thread, while providing a synchronous interface to the client. This is achieved using a combination of message passing, request queues, and scheduling mechanisms.

Key Components

Proxy: Represents the public interface to the client. In even simpler terms, this is what the client is going to interact to. It translates method calls into requests for the active object.
Scheduler: Manages the request queue and determines the order of request execution.
Servant: Contains the actual implementation of the methods being invoked. This is where actual computation logic goes.
Activation Queue: Stores the requests from the proxy until the scheduler processes them.
Future/Callback: A placeholder for the result of an asynchronous computation.

Workflow

A client invokes a method on the proxy.
The proxy creates a request and places it in the activation queue.
The scheduler picks up the request and forwards it to the servant for execution.
The result is returned to the client via a future object.

Use Cases

Real-time systems requiring predictable execution patterns.
GUI applications to keep the main thread responsive.
Distributed systems for handling asynchronous requests.

Implementation

Let's say we need to do a computation, maybe a API call, a database query, etc. I am not going to implement any exception handling because I am too lazy.

def compute(x, y):
    time.sleep(2)  # Some time taking task
    return x + y

Without Active Object Pattern

Below is an example of how we might handle concurrent requests without using the Active Object Pattern.

import threading
import time


def main():
    # Start threads directly
    results = {}

    def worker(task_id, x, y):
        results[task_id] = compute(x, y)

    print("Submitting tasks...")
    thread1 = threading.Thread(target=worker, args=(1, 5, 10))
    thread2 = threading.Thread(target=worker, args=(2, 15, 20))

    thread1.start()
    thread2.start()

    print("Doing other work...")

    thread1.join()
    thread2.join()

    # Retrieve results
    print("Result 1:", results[1])
    print("Result 2:", results[2])


if __name__ == "__main__":
    main()

Drawbacks of the Above Approach

Thread Management: Direct management of threads increases complexity, especially as the number of tasks grows.
Lack of Abstraction: The client is responsible for managing the lifecycle of threads, coupling task management with business logic.
Scalability Issues: Without a proper queue or scheduling mechanism, there’s no control over task execution order.
Limited Responsiveness: The client has to wait for threads to join before accessing results.

Implementation using Active Object Pattern

Below is a Python implementation of the Active Object Pattern using threading and queues for doing the same thing as above. We'll walk through each part one by one:

MethodRequest: Encapsulates the method, arguments, and a Future to store the result.

class MethodRequest:
    def __init__(self, method, args, kwargs, future):
        self.method = method
        self.args = args
        self.kwargs = kwargs
        self.future = future

    def execute(self):
        try:
            result = self.method(*self.args, **self.kwargs)
            self.future.set_result(result)
        except Exception as e:
            self.future.set_exception(e)

Scheduler: Continuously processes requests from the activation_queue in a separate thread.

import threading
import queue


class Scheduler(threading.Thread):
    def __init__(self):
        super().__init__()
        self.activation_queue = queue.Queue()
        self._stop_event = threading.Event()

    def enqueue(self, request):
        self.activation_queue.put(request)

    def run(self):
        while not self._stop_event.is_set():
            try:
                request = self.activation_queue.get(timeout=0.1)
                request.execute()
            except queue.Empty:
                continue

    def stop(self):
        self._stop_event.set()
        self.join()

Servant: Implements the actual logic (e.g., the compute method).

import time


class Servant:
    def compute(self, x, y):
        time.sleep(2)
        return x + y

Proxy: Translates method calls into requests and returns a Future for the result.

from concurrent.futures import Future


class Proxy:
    def __init__(self, servant, scheduler):
        self.servant = servant
        self.scheduler = scheduler

    def compute(self, x, y):
        future = Future()
        request = MethodRequest(self.servant.compute, (x, y), {}, future)
        self.scheduler.enqueue(request)
        return future

Client: Submits tasks asynchronously and retrieves results when needed.

def main():
    # Initialize components
    scheduler = Scheduler()
    scheduler.start()

    servant = Servant()
    proxy = Proxy(servant, scheduler)

    # Client makes an asynchronous call
    print("Submitting tasks...")
    future1 = proxy.compute(5, 10)
    future2 = proxy.compute(15, 20)

    # Perform other tasks while computation is ongoing
    print("Doing other work...")

    # Retrieve results
    print("Result 1:", future1.result())
    print("Result 2:", future2.result())

    # Shutdown scheduler
    scheduler.stop()

if __name__ == "__main__":
    main()

Advantages

Decoupled Interface: Clients can invoke methods without worrying about the execution details.
Responsiveness: Asynchronous execution ensures that the client remains responsive.
Scalability: Supports multiple concurrent requests.

Disadvantages

Complexity: Increases architectural complexity.
Overhead: Requires additional resources for managing threads and queues.
Latency: Asynchronous processing may introduce additional latency.

Conclusion

The Active Object Pattern is a powerful tool for managing asynchronous operations in multi-threaded environments. By separating method invocation from execution, it ensures better responsiveness, scalability, and a cleaner codebase. While it comes with some complexity and potential performance overhead, its benefits make it an excellent choice for scenarios requiring high concurrency and predictable execution. However, its use depends on the specific problem at hand. As with most patterns and algorithms, there is no one-size-fits-all solution.

References

Wikipedia - Active Object

DEV Community: Yasir Jafri

Sorted Data Structures in Python

heapq Module

Example:

sortedcontainers Module

SortedList:

SortedDict:

SortedSet:

Trade-offs of Sorted Data Structures

Conclusion

Concurrency Patterns: Balking Pattern

Introduction

The Balking Pattern relies on three fundamental concepts

When to Use the Balking Pattern

Advantages of the Balking Pattern

Disadvantages

Conclusion

References

Concurrency Patterns: Active Object

Introduction

Key Components

Workflow

Use Cases

Implementation

Without Active Object Pattern

Drawbacks of the Above Approach

Implementation using Active Object Pattern

Advantages

Disadvantages

Conclusion

References

`heapq` Module

`sortedcontainers` Module

`SortedList`:

`SortedDict`:

`SortedSet`: