Collections

The module collections gathers some useful structures.

deque

A list pops its last element in constant time. However, popping the first element costs linear time. The collections.deque has a pop_left method to pop the first element in constant time.

defaultdict

Imagine that you are building a dict[..., list[...]]. collections.defaultdict allows you to append/extend a value of this dict without prior initialization.

Exercise (easy)

Simplify the code of the exercise about project groups

src
 1def inverse_to_group_affiliation_of_students(
 2    student_composition_of_groups: dict[int, set[int]],
 3) -> dict[int, set[int]]:  # later, improvement of type hinting
 4    """from a dict[group, students], tranpose to dict[student: groups]"""
 5    group_affiliation_of_students: dict[int, set[int]] = {}
 6    for group, students in student_composition_of_groups.items():
 7        for student in students:
 8            if student not in group_affiliation_of_students:
 9                # later, improvement defaultdict
10                group_affiliation_of_students[student] = set()
11            group_affiliation_of_students[student].add(group)
12    return group_affiliation_of_students
Correction
src
1def inverse_to_group_affiliation_of_students(
2    student_composition_of_groups: dict[int, set[int]],
3) -> dict[int, set[int]]:  # later, improvement of type hinting
4    group_affiliation_of_students = collections.defaultdict(set)
5    for group, students in student_composition_of_groups.items():
6        for student in students:
7            group_affiliation_of_students[student].add(group)
8    return group_affiliation_of_students

Heapq

A heap is a structure where an order is efficiently maintained between elements, and where the smallest element can be efficiently popped heapq.heappop. The initial list has to be transformed in place in a heap with heapq.heapify.

1import heapq
2
3values = [4, 1, 3, 2]
4heapq.heapify(values)
5print(values)
6while values:
7    print(heapq.heappop(values))  # 1 2 3 4

Remember that tuples are compared from left to right. The usual pattern to use heapq as a priority queue is to push elements as: (priority, tie_breaker, item). The tie_breaker is usually the number of pushed elements. A priority queue is useful when new items are added while processing. If no new items are added, an initial sort on the priority is sufficient.

Exercise (easy)

When ‘processing’ the following priority queue, if the considered item is uppercase, re-submit this item in lowercase value and same priority. The ‘processing’ consists in yielding the item. Write a test and implement.

[
   (500, 0, "b"),
   (500, 1, "a"),
   (300, 2, "c"),
   (400, 3, "D"),
   (400, 4, "e"),
]
Correction
src
 1def process(queue: list[tuple[int, int, str]]) -> Generator[str]:
 2    heapq.heapify(queue)
 3    count = len(queue)
 4    while queue:
 5        priority, _, item = heapq.heappop(queue)
 6        if item.isupper():
 7            count += 1
 8            heapq.heappush(queue, (priority, count, item.lower()))
 9        else:
10            yield item
src
 1def test_process() -> None:
 2    queue: list[tuple[int, int, str]] = [
 3        (500, 0, "b"),
 4        (500, 1, "a"),
 5        (300, 2, "c"),
 6        (400, 3, "D"),
 7        (400, 4, "e"),
 8    ]
 9    obtained = list(process(queue))
10    expected = ["c", "e", "d", "b", "a"]
11    assert obtained == expected