Продвинутые структуры данных

Эффективная работа с коллекциями

Создание и наполнение коллекций данных — одна из самых частых задач в программировании. Стандартный подход с использованием циклов for работает, но в Python есть более изящный и производительный способ — включения, или comprehensions.

Включения позволяют создавать списки, множества и словари в одну строку, описывая их содержимое декларативно. Это не просто синтаксический сахар; такой код часто выполняется быстрее, так как некоторые операции оптимизируются на уровне интерпретатора CPython.

# Стандартный подход с циклом
squares = []
for i in range(10):
    if i % 2 == 0: # Только для четных чисел
        squares.append(i * i)

# Эквивалент с использованием list comprehension
squares_comp = [i * i for i in range(10) if i % 2 == 0]

print(squares)       # [0, 4, 16, 36, 64]
print(squares_comp)  # [0, 4, 16, 36, 64]

Синтаксис интуитивно понятен: [выражение for элемент in итерируемый_объект if условие]. Условие if не является обязательным, но позволяет легко фильтровать элементы.

Этот же принцип применим к множествам и словарям, меняется только тип скобок.

# Set comprehension (фигурные скобки, нет ключей)
unique_squares = {i * i for i in range(-5, 6)}
# {0, 1, 4, 9, 16, 25}

# Dict comprehension (фигурные скобки, пара ключ:значение)
number_cubes = {x: x**3 for x in range(5)}
# {0: 0, 1: 1, 2: 8, 3: 27, 4: 64}

Когда мы работаем с очень большими объемами данных, создание полного списка в памяти может быть неэффективным. Для таких случаев существуют генераторные выражения. Они выглядят как списковые включения, но с круглыми скобками. Вместо создания всей коллекции сразу, они создают специальный объект-генератор, который «отдает» элементы по одному, по мере необходимости. Это значительно экономит память.

import sys

# Списковое включение создает полный список в памяти
list_comp = [i for i in range(10000)]
print(f"Размер списка: {sys.getsizeof(list_comp)} байт")

# Генераторное выражение создает только объект-генератор
gen_exp = (i for i in range(10000))
print(f"Размер генератора: {sys.getsizeof(gen_exp)} байт")

# Генератор можно итерировать, как и список
# Например, найти сумму всех элементов
sum_of_elements = sum(gen_exp)
print(f"Сумма: {sum_of_elements}")

Под капотом словарей

Словари в Python невероятно быстры. Поиск, вставка или удаление элемента в среднем занимают одинаково мало времени, независимо от того, сколько в словаре элементов. Секрет этой скорости — в структуре данных под названием хеш-таблица.

Когда вы добавляете пару ключ-значение в словарь, Python делает следующее:

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

Когда вы хотите получить значение по ключу, Python повторяет шаги 1 и 2, мгновенно находя нужную ячейку и возвращая значение.

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

Из-за этого механизма ключами словаря могут быть только неизменяемые (иммутабельные) типы данных: числа, строки, кортежи. Их хеш всегда будет одинаковым. А вот список не может быть ключом, так как его содержимое можно изменить, что привело бы к изменению хеша и потере данных в таблице.

Анализ производительности: O-нотация

Чтобы сравнивать эффективность разных структур данных и алгоритмов, используют «О большое» или O-нотацию. Она описывает, как время выполнения (или потребление памяти) зависит от размера входных данных (n).

$O(1)$ : Константное время. Время выполнения не зависит от размера коллекции. Это идеал, к которому стремятся.
$O(n)$ : Линейное время. Время выполнения растет пропорционально количеству элементов.
$O(\log n)$ : Логарифмическое время. Время выполнения растет очень медленно. Каждый раз, удваивая размер данных, вы лишь на одну единицу увеличиваете количество операций.

Давайте сравним сложность основных операций для списков и словарей/множеств.

Операция	Список (list)	Словарь/Множество (dict/set)
Чтение элемента	$O(1)$ (по индексу)	$O(1)$ (по ключу)
Поиск элемента	$O(n)$ (по значению)	$O(1)$ (по значению/ключу)
Вставка	$O(n)$ (в начало)	$O(1)$
Удаление	$O(n)$ (в начале)	$O(1)$

Все значения для словарей и множеств указаны для среднего случая. В редких, худших случаях (при большом количестве коллизий) сложность может деградировать до $O(n)$ .

Таблица наглядно показывает, почему для задач, требующих частого поиска, добавления и удаления элементов, словари и множества — лучший выбор. А списки хороши, когда вам нужен упорядоченный доступ к элементам по числовому индексу.

Манипуляция данными

Python предлагает мощные и лаконичные инструменты для работы с коллекциями, которые делают код чище и выразительнее.

Распаковка и срезы

Распаковка позволяет присвоить элементы коллекции нескольким переменным одновременно. Оператор * (звёздочка) используется для расширенной распаковки, захватывая «оставшиеся» элементы в список.

numbers = [1, 2, 3, 4, 5]

# Расширенная распаковка
first, *middle, last = numbers

print(f"First: {first}")    # First: 1
print(f"Middle: {middle}")  # Middle: [2, 3, 4]
print(f"Last: {last}")      # Last: 5

Функции map, filter и zip

Хотя списковые включения часто являются предпочтительным способом, встроенные функции map, filter и zip остаются важными инструментами.

map(function, iterable) применяет функцию к каждому элементу коллекции.
filter(function, iterable) отфильтровывает элементы, для которых функция возвращает False.
zip(*iterables) объединяет несколько коллекций в одну, создавая кортежи из соответствующих элементов.

Важно помнить, что в Python 3 эти функции возвращают не списки, а итераторы — ленивые объекты, похожие на генераторы. Чтобы получить результат в виде списка, нужно явно преобразовать его с помощью list().

items = ["Яблоко", "Банан", "Вишня"]
prices = [100, 80, 250]

# map: получить длину каждого слова
lengths = list(map(len, items))
# [6, 5, 5]

# filter: найти цены > 90
high_prices = list(filter(lambda p: p > 90, prices))
# [100, 250]

# zip: объединить товары и цены
store_items = list(zip(items, prices))
# [('Яблоко', 100), ('Банан', 80), ('Вишня', 250)]

Выбор между этими функциями и включениями часто зависит от контекста и личных предпочтений. Включения могут быть более читаемыми для простых случаев, в то время как map и filter удобны, когда у вас уже есть готовая функция для применения.

Quiz Questions 1/5

Какое выражение создаст генератор, а не список, что позволит сэкономить память при работе с большими объемами данных?

Quiz Questions 2/5

Почему список [1, 2, 3] не может быть использован в качестве ключа словаря в Python?

Понимание этих продвинутых концепций позволяет писать не просто работающий, а по-настоящему эффективный и идиоматичный код на Python.

Профессиональный старт в Python