Sorting Through Data: Using Custom Classes and Comparators in Python Maps

Lesson 4

Topic Overview

Welcome to our exploration of sorted maps using custom classes and comparators in Python. In today's lesson, we'll learn how to use custom classes as keys in sorted maps. This approach enhances data organization and access. With the addition of comparators, we can dictate the order in such maps.

Quick Recap on Sorted Maps

A sorted map is a dictionary with its keys always in order. This arrangement makes operations like searching for keys within a range more efficient. In Python, we use the SortedDict class from the sortedcontainers library to create sorted maps:

Python
1from sortedcontainers import SortedDict
2
3s_map = SortedDict({'a': 1, 'b': 2, 'c': 3})
4print(s_map)  # Outputs SortedDict({'a': 1, 'b': 2, 'c': 3})

Introduction to Custom Classes in Python

Custom classes enable us to create objects that fit our data — for instance, a "Person" class for employee information or a "Book" class for a library database. In Python, classes are the blueprints for creating objects.

Consider this simple class, for example:

Python
1from sortedcontainers import SortedDict
2
3class Person:
4    def __init__(self, name, age):
5        self.name = name
6        self.age = age
7
8person = Person("John Doe", 30)
9print(person.name)  # Outputs "John Doe"
10print(person.age)   # Outputs 30

Using Custom Classes as Keys in Sorted Maps

Using custom classes as map keys helps organize complex multivariate keys in a sorted map. Below is an example of how to use comparators to dictate the order when using custom classes as keys:

Python
1from sortedcontainers import SortedDict
2
3class Person:
4    def __init__(self, name, age):
5        self.name = name
6        self.age = age
7
8    def __hash__(self):
9        return hash((self.name, self.score))
10
11people = SortedDict()
12
13john = Person("John", 30)
14alice = Person("Alice", 25)
15
16people[john] = "Programmer"
17people[alice] = "Designer"

In this example, John is assigned the value "Programmer", and Alice is assigned the value "Designer". However, this code doesn't work, can you guess why?

Comparators and their Role in Sorted Maps

Python uses a comparator to determine the order of two keys. To make this comparison, we add special methods to our class — __lt__ (less than), __gt__ (greater than), __eq__ (equals), __ne__ (not equals), and __hash__ (the hash of the class instance). Without these methods, SortedDict can't compare its Person class keys.

Python
1from sortedcontainers import SortedDict
2
3class Person:
4    def __init__(self, name, age):
5        self.name = name
6        self.age = age
7
8    def __lt__(self, other):
9        return (self.age, self.name) < (other.age, other.name)
10
11    def __gt__(self, other):
12        return (self.age, self.name) > (other.age, other.name)
13
14    def __eq__(self, other):
15        return (self.age, self.name) == (other.age, other.name)
16
17    def __ne__(self, other):
18        return (self.age, self.name) != (other.age, other.name)
19    
20    def __hash__(self):
21        return hash((self.name, self.age))
22
23people = SortedDict()
24
25john = Person("John", 30)
26alice = Person("Alice", 25)
27
28people[john] = "Programmer"
29people[alice] = "Designer"
30
31for person in people:
32    print(f'{person.name} is a {people[person]}')
33# Output:
34# Alice is a Designer
35# John is a Programmer

Lesson Summary and Practice

We've explored how to use custom classes as keys in sorted maps and how comparators work in this context. Now, prepare for some hands-on exercises to reinforce these concepts.

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.