Модуль 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
:
- Код становится более читабельным и легко понятным, так как определение именованных полей явно задает структуру данных и делает ее интуитивно понятной.
- При использовании
namedtuple
нет необходимости использовать ключи для доступа к значениям. Вместо этого можно использовать имена полей, что делает код более удобочитаемым. namedtuple
— это неизменяемые объекты, что может быть полезно в тех случаях, когда данные не должны изменяться.
Преимущества использования dict
:
- Словари
dict
могут иметь любые имена ключей, что дает большую гибкость в хранении и доступе к данным. - Словари могут легко изменяться в процессе выполнения программы.
- Словари могут использоваться для хранения нескольких значений с одинаковым ключом, что может быть полезно в некоторых случаях.
Таким образом, выбор между 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...
В этом примере мы создали класс Order
, представляющий заказ, содержащий информацию о order_id
, customer_name
и items
.
Мы также создали класс OrderQueue
, представляющий очередь заказов. Мы создали пустую очередь с помощью deque
и добавили методы для добавления заказов в очередь
Задание 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
Здесь мы используем deque в качестве стека для хранения операндов во время разбора выражения в польской записи. Мы итерируемся по каждому токену в выражении, и если токен является числом, то мы добавляем его в стек. Если же токен является оператором, то мы извлекаем два последних операнда из стека, выполняем соответствующую операцию и помещаем результат обратно в стек. По завершению разбора выражения, результат находится в единственном элементе стека, который мы извлекаем и возвращаем.
Класс 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))
Здесь мы считываем содержимое файла с помощью метода read()
, разбиваем текст на отдельные слова с помощью метода split()
, создаем объект Counter и используем его метод most_common()
для вывода наиболее часто встречающихся слов.
Класс 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). Образец файла.
Для решения данной задачи можно использовать defaultdict. Мы будем считывать данные из входного файла и заполнять defaultdict
для каждого ряда местами, которые уже распределены между сотрудниками. Затем мы будем перебирать все ряды, начиная с самого верхнего и находить первую пару соседних мест, которые еще не заняты.
Вот код решения задачи с помощью defaultdict
:
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")
Как можно заметить, мы создали defaultdict(set)
, который будет хранить занятые места для каждого ряда. Затем мы считали данные из входного файла и добавляли занятые места в defaultdict
.
Далее мы перебирали все ряды и места, и проверяли, есть ли два соседних места, которые еще не заняты. Если такие места находились и текущий ряд был выше предыдущих найденных рядов, то мы обновляли переменные max_row
и max_seat
.
В конце мы записывали ответ в выходной файл в формате, указанном в условии задачи.