Модуль Collections в Python

Модуль collections является частью стандартной библиотеки Python и предоставляет удобные и эффективные альтернативы встроенным типам данных, таким как списки, словари и множества. Он содержит множество классов и функций, которые упрощают работу с различными структурами данных, такими как namedtuple, deque, Counter, defaultdict, OrderedDict, ChainMap, UserList, UserDict и UserString.

Примеры практических задач, которые помогает решить использование collections:

• Подсчет элементов в списке или словаре с помощью Counter
• Использование namedtuple для хранения данных в виде именованных кортежей
• Использование deque для реализации очереди и стека
• Использование defaultdict для инициализации словаря по умолчанию
• Использование OrderedDict для упорядочивания элементов в словаре по ключам
• Объединение нескольких словарей в один с помощью ChainMap
• Создание подкласса списка, словаря или строки с помощью UserList, UserDict или UserString

Все эти задачи могут быть решены и с помощью встроенных типов данных в Python, но использование структур данных из модуля collections позволяет реализовать решение более эффективно и удобно.

Основные структуры данных модуля Collections

Namedtuple

Namedtuple — это подкласс кортежа, который определяет именованные поля. Он позволяет создавать объекты, которые похожи на записи в базе данных или структуры данных в других языках программирования. Названия полей определяются заранее, что позволяет удобно работать с данными.

Пример реализации:

from collections import namedtuple

# создание именованного кортежа
Person = namedtuple('Person', ['name', 'age', 'gender'])

# создание объекта
person1 = Person('Alice', 25, 'female')

# доступ к полям объекта
print(person1.name)
print(person1.age)
print(person1.gender)

Допустим, у нас есть список пользователей, представленных в виде словарей, и мы хотим вывести на экран список их имен и возрастов, используя именованный кортеж. Мы можем создать именованный кортеж, описывающий структуру данных пользователя, а затем создать список объектов этого кортежа, используя данные из списка словарей:

from collections import namedtuple

# создание именованного кортежа
User = namedtuple('User', ['name', 'age'])

# список пользователей
users = [{'name': 'Alice', 'age': 25},
         {'name': 'Bob', 'age': 30},
         {'name': 'Charlie', 'age': 35}]

# создание списка объектов именованного кортежа
user_objects = [User(user['name'], user['age']) for user in users]

# вывод списка имен и возрастов пользователей
for user in user_objects:
    print(user.name, user.age)

Отличие namedtuple от словарей

Как вы могли заметить, использование namedtuple немного напоминает работу со словарями. В чем же отличия, и когда лучше использовать именованные кортежи, а когда словари?

namedtuple и dict представляют собой разные структуры данных с разными преимуществами и недостатками.

Преимущества использования namedtuple:

1. Код становится более читабельным и легко понятным, так как определение именованных полей явно задает структуру данных и делает ее интуитивно понятной.
2. При использовании namedtuple нет необходимости использовать ключи для доступа к значениям. Вместо этого можно использовать имена полей, что делает код более удобочитаемым.
3. namedtuple — это неизменяемые объекты, что может быть полезно в тех случаях, когда данные не должны изменяться.

Преимущества использования dict:

1. Словари dict могут иметь любые имена ключей, что дает большую гибкость в хранении и доступе к данным.
2. Словари могут легко изменяться в процессе выполнения программы.
3. Словари могут использоваться для хранения нескольких значений с одинаковым ключом, что может быть полезно в некоторых случаях.

Таким образом, выбор между namedtuple и dict зависит от конкретных потребностей в проекте. Если вы хотите использовать неизменяемые объекты с предопределенными полями, то namedtuple может быть хорошим выбором. Если же вы хотите хранить данные с произвольными ключами и изменять их в процессе выполнения программы, то лучше использовать словари dict.

Практические задачи для закрепления

Задание 1. Хранение информации о студентах: Вы можете использовать namedtuple для хранения информации о студентах, включая их имя, фамилию, возраст и другие характеристики.

from collections import namedtuple

# Создаем класс "Student" с полями "name", "surname" и "age"
Student = namedtuple("Student", ["name", "surname", "age"])

# Создаем список студентов
students = [
    Student("Иван", "Иванов", 21),
    Student("Петр", "Петров", 23),
    Student("Анна", "Сидорова", 20),
]

# Выводим информацию о каждом студенте
for student in students:
    print(f"{student.name} {student.surname}, возраст: {student.age}")

Задание 2. Хранение информации о продуктах: Вы можете использовать namedtuple для хранения информации о продуктах, включая их название, цену, количество и другие характеристики.

from collections import namedtuple

# Создаем класс "Product" с полями "name", "price" и "quantity"
Product = namedtuple("Product", ["name", "price", "quantity"])

# Создаем список продуктов
products = [
    Product("Молоко", 50, 10),
    Product("Хлеб", 30, 20),
    Product("Яблоки", 100, 5),
]

# Выводим информацию о каждом продукте
for product in products:
    print(f"{product.name}: {product.price} руб. x {product.quantity}")

Задание 3. Хранение информации о фильмах: Вы можете использовать namedtuple для хранения информации о фильмах, включая их название, год выпуска, режиссера и другие характеристики.

from collections import namedtuple

# Создаем класс "Movie" с полями "title", "year" и "director"
Movie = namedtuple("Movie", ["title", "year", "director"])

# Создаем список фильмов
movies = [
    Movie("Зеленая миля", 1999, "Фрэнк Дарабонт"),
    Movie("Побег из Шоушенка", 1994, "Фрэнк Дарабонт"),
    Movie("Форрест Гамп", 1994, "Роберт Земекис"),
]

# Выводим информацию о каждом фильме
for movie in movies:
    print(f"{movie.title} ({movie.year}), режиссер: {movie.director}")

Задание 4. Представление матрицы: Вы можете использовать namedtuple для представления матрицы, включая ее размерность и элементы. Например, вы можете создать namedtuple с именем Matrix и полями rows и cols для хранения размерности матрицы, а также полем data для хранения ее элементов.

from collections import namedtuple

# Создаем класс "Matrix" с полями "rows", "cols" и "data"
Matrix = namedtuple("Matrix", ["rows", "cols", "data"])

# Создаем матрицу
matrix = Matrix(3, 3, [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
])

# Выводим элементы матрицы
for row in matrix.data:
    print(row)

Задание 5. Хранение информации о событиях: Вы можете использовать namedtuple для хранения информации о событиях, включая их название, дату, место проведения и другие характеристики.

from collections import namedtuple
from datetime import datetime

# Создаем класс "Event" с полями "title", "date" и "location"
Event = namedtuple("Event", ["title", "date", "location"])

# Создаем список событий
events = [
    Event("День рождения Ивана", datetime(2023, 4, 1, 

Задание 6. Хранение информации о пользователях: Вы можете использовать namedtuple для хранения информации о пользователях, включая их имя, электронную почту, пароль и другие характеристики.

from collections import namedtuple

# Создаем класс "User" с полями "username", "email" и "age"
User = namedtuple("User", ["username", "email", "age"])

# Создаем список пользователей
users = [
    User("user1", "user1@mail.com", 25),
    User("user2", "user2@mail.com", 30),
    User("user3", "user3@mail.com", 28),
]

# Выводим информацию о каждом пользователе
for user in users:
    print(f"Имя пользователя: {user.username}, email: {user.email}, возраст: {user.age}")

Deque

Deque (Double Ended Queue) — это коллекция, которая представляет собой двустороннюю очередь. Она может использоваться как стек или очередь с добавлением и удалением элементов с обоих концов. В отличие от списков, добавление и удаление элементов из начала и конца очереди выполняется за константное время O(1).

Понятие О (О большое) характеризует скорость работы алгоритма. Оно измеряется в количестве элементарных операций, которые требуются, чтобы сделать то или иное действие. Чем меньше количество операций, тем быстрее будет алгоритм. О(1) означает, что для реализации добавления элемента потребуется одна операция.

Пример реализации.

from collections import deque

# создание deque
queue = deque([1, 2, 3])

# добавление элемента в конец очереди
queue.append(4)

# добавление элемента в начало очереди
queue.appendleft(0)

# удаление элемента из конца очереди
queue.pop()

# удаление элемента из начала очереди
queue.popleft()

# вывод содержимого очереди
print(queue)

Пример решения практической задачи с помощью deque — обработка очереди задач:

from collections import deque

# Создаем пустую очередь задач
tasks = deque()

# Добавляем задачи в очередь
tasks.append("Задача 1")
tasks.append("Задача 2")
tasks.append("Задача 3")

# Обработка задач
while tasks:
    task = tasks.popleft()  # берем задачу из начала очереди
    print(f"Обработка задачи: {task}")

В этом примере мы создаем пустую очередь задач и добавляем в нее несколько задач. Затем мы обрабатываем задачи в порядке их добавления в очередь с помощью цикла while и метода popleft() объекта deque. Метод popleft() удаляет первый элемент из очереди и возвращает его значение. Благодаря deque мы можем эффективно добавлять и удалять элементы в начале и конце очереди.

Практические задания на стеки и очередь

Задание 7. Обработка логов. Предположим, что у нас есть файл с логами, содержащий миллионы записей. Мы хотим прочитать этот файл и вывести на экран последние N записей в обратном порядке.

from collections import deque

N = 10  # количество последних записей, которые нужно вывести
logs = deque(maxlen=N)  # создаем deque с ограниченной длиной

with open("logs.txt") as f:
    for line in f:
        logs.append(line.strip())  # добавляем запись в конец deque
for log in reversed(logs):
    print(log)  # выводим записи в обратном порядке

Задание 8. Реализовать систему обработки заказов в виде очереди.

from collections import deque

class Order:
    def __init__(self, order_id, customer_name, items):
        self.order_id = order_id
        self.customer_name = customer_name
        self.items = items

class OrderQueue:
    def __init__(self):
        self.queue = deque()

    def add_order(self, order):
        self.queue.append(order)

    def process_orders(self):
        while self.queue:
            order = self.queue.popleft()
            print(f"Processing order {order.order_id} for customer {order.customer_name}.")
            # Process order here...

Задание 9. Разобрать математическое выражение в обратной польской записи. Польская запись (или префиксная запись) — это форма записи математических выражений, в которой операторы располагаются перед операндами. В польской записи каждое выражение начинается с оператора, за которым следуют операнды. Например, вместо того, чтобы записывать «2 + 3», в польской записи это будет выглядеть как «+ 2 3».

from collections import deque

def evaluate_expression(expression):
    stack = deque()
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            if token == "+":
                result = operand1 + operand2
            elif token == "-":
                result = operand1 - operand2
            elif token == "*":
                result = operand1 * operand2
            elif token == "/":
                result = operand1 / operand2
            else:
                raise ValueError("Unknown operator: {}".format(token))
            stack.append(result)
    return stack.pop()

expression = "+ * 2 3 4"
result = evaluate_expression(expression)
print("{} = {}".format(expression, result)) # Output: + * 2 3 4 = 10

Класс counter

Counter — это класс из модуля collections в Python, предназначенный для подсчета количества объектов в списке или другой итерируемой последовательности. Он создает словарь, в котором каждый элемент итерируемой последовательности является ключом, а его значение — количество раз, которое он встречается в последовательности.

Пример использования Counter:

from collections import Counter

lst = ['apple', 'orange', 'banana', 'apple', 'orange', 'apple']
cnt = Counter(lst)

print(cnt)
# Counter({'apple': 3, 'orange': 2, 'banana': 1})

print(cnt['apple'])
# 3

print(cnt.most_common())
# [('apple', 3), ('orange', 2), ('banana', 1)]

В данном примере мы создаем список lst и передаем его в объект Counter. Затем мы можем обращаться к элементам словаря по ключу и получать количество их повторений в списке. Метод most_common() возвращает список кортежей, отсортированный по количеству повторений элементов в итерируемой последовательности, начиная с наиболее часто встречающихся элементов.

Counter может быть полезен в различных задачах, связанных с подсчетом элементов в последовательности. Например, он может использоваться для подсчета количества уникальных элементов в списке, для анализа частоты встречаемости слов в тексте или для подсчета количества ошибок в журнале событий.

Методы класса Counter

Класс Counter имеет следующие методы и атрибуты:

Методы:

• elements(): возвращает итератор со всеми элементами объекта Counter, повторяющимися столько раз, сколько их было в исходной последовательности.
• most_common([n]): возвращает список кортежей с n наиболее часто встречающимися элементами и их количеством в порядке убывания. Если n не указан, возвращаются все элементы в порядке убывания.
• subtract([iterable-or-mapping]): вычитает из текущего объекта Counter все элементы из переданного итерируемого объекта или словаря, обновляя счетчики элементов.
• update([iterable-or-mapping]): обновляет счетчики элементов текущего объекта Counter на основе переданного итерируемого объекта или словаря.

Пример использования:

from collections import Counter

c = Counter('abracadabra')

print(c)
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

print(c.most_common())
# [('a', 5), ('b', 2), ('r', 2), ('c', 1), ('d', 1)]

print(list(c.elements()))
# ['a', 'a', 'a', 'a', 'a', 'b', 'b', 'r', 'r', 'c', 'd']

c.subtract('aaa')
print(c)
# Counter({'a': 2, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

c.update('aae')
print(c)
# Counter({'a': 4, 'b': 2, 'r': 2, 'c': 1, 'd': 1, 'e': 1})

В данном примере мы создаем объект Counter на основе строки ‘abracadabra’. Затем мы используем методы most_common(), elements(), subtract() и update(), а также свойства most_common и elements.

Задание для закрепления

Задание 10. Дан большой текстовый файл с множеством слов и мы хотим посчитать количество уникальных слов в этом файле.

from collections import Counter

# Открываем файл и считываем все его содержимое
with open('text.txt', 'r') as file:
    text = file.read()

# Разбиваем текст на отдельные слова
words = text.split()

# Считаем количество вхождений каждого слова в текст
word_counts = Counter(words)

# Выводим 10 самых часто встречающихся слов
print(word_counts.most_common(10))

Класс defaultdict

defaultdict — это подкласс словаря (dict), который автоматически создает значения для ключей, которые еще не были установлены. При создании defaultdict вы указываете функцию-фабрику, которая будет вызываться для создания значения по умолчанию для каждого нового ключа.

Этот инструмент полезен, когда мы работаем со словарями и хотим избежать ошибок, которые могут возникнуть, когда мы пытаемся обратиться к несуществующему ключу. Вместо этого defaultdict автоматически создаст новый ключ и присвоит ему значение, которое было указано при создании объекта.

Примеры использования defaultdict:

1. Подсчет количества вхождений элементов в списке:

from collections import defaultdict

# Создаем defaultdict с типом int, который автоматически инициализирует новые ключи значением 0
d = defaultdict(int)

# Список элементов
lst = ['apple', 'banana', 'apple', 'cherry', 'cherry', 'cherry']

# Подсчитываем количество вхождений каждого элемента
for item in lst:
    d[item] += 1

print(d)
# defaultdict(<class 'int'>, {'apple': 2, 'banana': 1, 'cherry': 3})

2. Группировка элементов списка по какому-то критерию:

from collections import defaultdict

# Создаем defaultdict с типом list, который автоматически инициализирует новые ключи пустым списком
d = defaultdict(list)

# Список элементов
lst = ['apple', 'banana', 'cherry', 'date', 'elderberry', 'fig', 'grape']

# Группируем элементы по длине
for item in lst:
    key = len(item)
    d[key].append(item)

print(d)
# defaultdict(<class 'list'>, {5: ['apple', 'grape'], 6: ['banana', 'cherry'], 4: ['date', 'fig'], 10: ['elderberry']})

Здесь мы создаем defaultdict с типом list, который автоматически инициализирует новые ключи пустым списком. Затем мы группируем элементы списка lst по длине слова с помощью метода len() и добавляем элементы в соответствующий список внутри словаря defaultdict.

Задание на закрепление

Задание 11. Источник: школьное задание ЕГЭ №26. Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками.

Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию.

В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.

В первой строке входного файла находится одно число: N  — количество занятых мест (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета (числа не превышают 100 000). Образец файла.

from collections import defaultdict

with open('input.txt') as f:
    n = int(f.readline())
    seats = defaultdict(set)
    for i in range(n):
        row, seat = map(int, f.readline().split())
        seats[row].add(seat)

max_row = max_seat = 0
for row, row_seats in seats.items():
    for seat in range(1, max(row_seats)):
        if seat + 1 in row_seats and seat - 1 in row_seats:
            if row > max_row or (row == max_row and seat < max_seat):
                max_row, max_seat = row, seat

with open('output.txt', 'w') as f:
    f.write(f"{max_row} {max_seat}\n")