Пишешь на Python, код работает, таски закрываются... Но иногда что-то идёт не так: скрипт тормозит на больших данных, коллеги неодобрительно качают головой над вашим `for` в `for` там, где хватило бы `set`, а на очередном собеседовании внезапно требуют объяснить разницу в производительности `append` и `insert(0)` для списка. Хочется писать не просто работающий, но и эффективный код, верно?
Это первая часть из ультимативного гайда по структурам данных и алгоритмам. Что вас ждёт?
Итак, сегодня мы закладываем фундамент. Готовы понять, почему кортеж может быть ключом словаря, а список — нет? Почему проверка `element in my_set` работает почти мгновенно? И чем так хорош `list.append()`?
Поехали разбираться! 👇🏻
Строки (str): текстовый фундамент
Строки — это, вероятно, первый тип данных, с которым сталкивается любой, кто начинает изучать Python или программирование в целом. Мы используем их постоянно, часто не задумываясь об их природе. Логи, пользовательский ввод, HTML, JSON — везде текст. В Python строка — это упорядоченная, неизменяемая (immutable) последовательность символов Unicode. Звучит просто? Дьявол, как обычно, в деталях, особенно в слове "неизменяемая".
# Строки можно создавать разными кавычками
greeting = "Привет, мир! 👋" # Да, эмоджи - это тоже символы Unicode
code_mantra = 'Readability counts.'
long_text = """Это многострочная строка,
удобная для больших кусков текста.
Beautiful is better than ugly."""
print(greeting)
print(type(code_mantra)) # <class 'str'>Ключевые особенности строк
Неизменяемость. Это самое важное свойство строк. После создания строки её нельзя изменить. Любая операция, которая выглядит как модификация строки (конкатенация, замена символов, изменение регистра), на самом деле создает и возвращает новую строку, оставляя исходную нетронутой.
Важно! Склеиваете строку из кучи мелких кусочков в цикле? Никогда не используйте `+=`! Каждая такая операция создает новую строку, копируя всё содержимое старой и добавляя новый кусок. Ужасно неэффективно (O(n^2) для n добавлений).
original = "python"
print(f"Исходное: '{original}', id: {id(original)}")
# Пытаемся изменить? TypeError!
# original[0] = "P"
# "Изменения" создают НОВЫЕ строки
capitalized = original.capitalize()
print(f"Capitalize: '{capitalized}', id: {id(capitalized)}") # Новый id!
replaced = original.replace('o', '0')
print(f"Replace: '{replaced}', id: {id(replaced)}") # Новый id!
combined = original + "ista"
print(f"Combine: '{combined}', id: {id(combined)}") # Новый id!
print(f"Исходное всё то же: '{original}', id: {id(original)}") # Старый id!Упорядоченность. Символы идут друг за другом в четком порядке. Можно обращаться по индексу (`s[i]`, O(1) — мгновенно) и делать срезы (`s[i:j:k]`, O(k), где k — длина среза).
word = "Алгоритм"
print(f"\nСлово: {word}")
print(f" Первый символ [0]: {word[0]}") # А (O(1))
print(f" Последний [-1]: {word[-1]}") # м (O(1))
print(f" Срез [2:6]: {word[2:6]}") # гори (O(4))
print(f" Каждый второй [::2]: {word[::2]}") # Агрт (O(n/2))
print(f" Задом наперёд [::-1]: {word[::-1]}") # мтироглА (O(n))Unicode по умолчанию. Python из коробки работает с Unicode. Забудьте про боль с кодировками внутри кода (до момента ввода/вывода). Кириллица, иероглифы, эмоджи — всё работает "просто так".
Нет отдельного типа "символ". В отличие от C++ или Java, в Python нет специального типа `char`. Отдельный символ — это просто строка длиной 1.
word = "Python"
char_A = word[0]
print(f"\nТип символа '{char_A}': {type(char_A)}") # <class 'str'>
print(f"Длина строки '{char_A}': {len(char_A)}") # 1Богатство методов. У строк куча встроенных методов для поиска, замены, разделения, проверки (`.find()`, `.replace()`, `.split()`, `.strip()`, `.lower()`, `.startswith()`, etc.). Изучите их! Для форматирования — **f-строки** (`f"Value: {variable}"`) — ваш лучший друг: читаемо и быстро.
Когда использовать строки? Всегда, когда работаете с текстом. Это ваш основной инструмент для текстовых данных любого рода. Главное — помнить про неизменяемость и активно юзать встроенные методы.
С текстом разобрались. Но что делать, когда нужно работать с "сырыми" данными — картинками, звуком, сетевыми пакетами? Переходим к `bytes` и `bytearray`!
Байты (bytes, bytearray): работа с "сырыми" данными
Итак, строки — это про текст, про понятные нам символы Unicode. Но что если нужно работать с данными в их первозданном, "сыром" виде? Картинки, музыка, видео, сжатые архивы, сетевые пакеты, данные с железок — всё это не текст, а последовательности байтов.
Для работы с такими данными в Python есть два типа:
Для работы с такими данными в Python есть два типа:
- bytes: неизменяемая (immutable) последовательность байтов. Используется для представления бинарных данных, которые не должны меняться.
- bytearray: изменяемая (mutable) последовательность байтов. Используется как буфер для сборки или модификации бинарных данных.
bytes: неизменяемый бинарный блок
Объекты `bytes` гарантируют, что бинарные данные останутся неизменными.
Примеры того, как можно создать такой объект:
Литерал `b`. Удобен для ASCII-совместимых символов или явного задания байтов через \xHH.
Примеры того, как можно создать такой объект:
Литерал `b`. Удобен для ASCII-совместимых символов или явного задания байтов через \xHH.
http_method = b"POST"
png_magic = b'\x89PNG\r\n\x1a\n' # Первые 8 байт PNG файла
print(f"Метод (bytes): {http_method}") # b'POST'
print(f"Тип: {type(http_method)}") # <class 'bytes'>`str.encode(encoding)`. Основной способ получить bytes из текста. Строка кодируется в байты согласно указанной кодировке.
message = "Кодируй меня полностью!"
utf8_bytes = message.encode('utf-8')
print(f"'{message}' в UTF-8: {utf8_bytes}")
# 'Кодируй меня полностью!' в UTF-8: b'\xd0\x9a\xd0\xbe\xd0\xb4\xd0\xb8\xd1\x80\xd1\x83\xd0\xb9 \xd0\xbc\xd0\xb5\xd0\xbd\xd1\x8f \xd0\xbf\xd0\xbe\xd0\xbb\xd0\xbd\xd0\xbe\xd1\x81\xd1\x82\xd1\x8c\xd1\x8e!'bytearray: изменяемый бинарный буфер
Когда нужно формировать бинарное сообщение по частям, модифицировать прочитанный блок данных или работать с буфером, который будет меняться, используется `bytearray`.
# Создаем изменяемый буфер, например, с пустым заголовком
# Изначально заполним '----' (ASCII байтами)
packet_buffer = bytearray(b'----SOME_DATA')
print(f"Изначальный буфер: {packet_buffer}")
# Изначальный буфер: bytearray(b'----SOME_DATA')
user_id = 1025 # ID = 1025 = 0x0401 в hex (2 байта)
# Нужны байты! ID нужно представить как байты.
# Можно использовать struct или просто to_bytes для чисел
# (предположим, порядок байтов big-endian - от старшего к младшему)
user_id_bytes = user_id.to_bytes(4, byteorder='big') # 4 байта
print(f"ID {user_id} как байты: {user_id_bytes}")
# ID 1025 как байты: b'\x00\x00\x04\x01'
# Записываем ID в начало буфера (изменяем существующий bytearray!)
packet_buffer[0:4] = user_id_bytes
print(f"Буфер с ID: {packet_buffer}")
# Вывод: Буфер с ID: bytearray(b'\x00\x00\x04\x01SOME_DATA')
# Можем добавлять байты в конец
packet_buffer.extend(b'END')
print(f"Добавили маркер конца: {packet_buffer}")
# Добавили маркер конца: bytearray(b'\x00\x00\x04\x01SOME_DATAEND')Ключевое различие строки и байтов — кодировки
Ещё раз зафиксируем:
Переход между ними — это кодирование (`str` -> `bytes`) и декодирование (`bytes` -> `str`). И здесь поджидает главный подводный камень — кодировка.
Кодировка — это набор правил, который говорит, какими байтами представлять какие символы. Популярные кодировки: 'utf-8' (стандарт де-факто в вебе, умеет кодировать любые символы Unicode), 'cp1251' (старая для русского Windows), 'ascii' (только базовые латинские символы).
Золотое правило: Используйте ОДНУ И ТУ ЖЕ кодировку для encode и decode! Иначе получите либо ошибку UnicodeDecodeError, либо знаменитые "кракозябры" (неправильно отображенные символы).
- Строка − это последовательность Unicode символов.
- bytes/bytearray − последовательность байтов (чисел 0−255).
Переход между ними — это кодирование (`str` -> `bytes`) и декодирование (`bytes` -> `str`). И здесь поджидает главный подводный камень — кодировка.
Кодировка — это набор правил, который говорит, какими байтами представлять какие символы. Популярные кодировки: 'utf-8' (стандарт де-факто в вебе, умеет кодировать любые символы Unicode), 'cp1251' (старая для русского Windows), 'ascii' (только базовые латинские символы).
Золотое правило: Используйте ОДНУ И ТУ ЖЕ кодировку для encode и decode! Иначе получите либо ошибку UnicodeDecodeError, либо знаменитые "кракозябры" (неправильно отображенные символы).
russian_text = "Тест кириллицы"
utf8_data = russian_text.encode('utf-8')
cp1251_data = russian_text.encode('cp1251')
print(f"\n'{russian_text}' в UTF-8: {utf8_data}")
print(f"'{russian_text}' в CP1251: {cp1251_data}")
# Правильное декодирование
print(f" UTF-8 -> str: '{utf8_data.decode('utf-8')}'")
print(f" CP1251 -> str: '{cp1251_data.decode('cp1251')}'")
# Неправильное декодирование
try:
print(f" UTF-8 -> str (as cp1251): '{utf8_data.decode('cp1251')}'") # Может дать кракозябры
except UnicodeDecodeError as e:
print(f" Ошибка UTF-8 as cp1251: {e}")
try:
print(f" CP1251 -> str (as utf-8): '{cp1251_data.decode('utf-8')}'")
except UnicodeDecodeError as e:
print(f" Ошибка CP1251 as utf-8: {e}") # Скорее всего будет ошибкаСовет: По возможности всегда используйте utf-8 и указывайте кодировку явно при чтении/записи файлов (`open('file.txt', 'r', encoding='utf-8')`) и сетевых взаимодействиях. Не полагайтесь на системные настройки по умолчанию, они могут отличаться!
Когда использовать bytes / bytearray?
- Чтение/запись бинарных файлов (изображения, аудио, исполняемые файлы, архивы, `pickle` и т. д.).
- Работа с сетевыми протоколами на низком уровне (создание/парсинг пакетов).
- Взаимодействие с аппаратным обеспечением, портами, бинарными потоками данных.
- Криптография, работа с хешами, шифрование/дешифрование данных.
- Представление неизменяемых бинарных констант или данных (`bytes`).
- Работа с изменяемыми бинарными буферами, сборка/модификация данных (`bytearray`).
Списки (list): гибкость ценой O(n) при вставке
Если вы писали на Python хоть пару строк, вы точно встречали списки. Это, пожалуй, самая универсальная и часто используемая встроенная коллекция. Представьте себе стеллаж с пронумерованными полками, куда можно ставить что угодно (числа, строки, другие стеллажи!), менять предметы местами, добавлять новые полки или убирать старые.
Ключевые особенности списков
- Упорядоченность. Элементы хранятся и извлекаются в том же порядке, в котором были добавлены. `[1, 2] != [2, 1]`.
- Изменяемость. Списки можно модифицировать после создания — добавлять, удалять, изменять элементы.
- Динамический размер. Списки автоматически меняют размер при добавлении/удалении элементов.
- Разнородность. Могут содержать элементы абсолютно любых типов одновременно.
- Индексация и срезы. Поддерживают доступ к элементам и подпоследовательностям по числовым индексам.
# Создаем список - микс из всего
my_stuff = [42, "котики", 3.14, True, None, ["еще", "список"]]
print(f"Мой список: {my_stuff}")
# Доступ по индексу (начинается с 0) - это быстро: O(1)
print(f"Первый элемент: {my_stuff[0]}") # 42
print(f"Последний элемент: {my_stuff[-1]}") # ['еще', 'список']
# Изменение элемента по индексу - тоже быстро: O(1)
my_stuff[1] = "собачки"
print(f"После замены: {my_stuff}")
# Длина списка - мгновенно: O(1)
print(f"Длина списка: {len(my_stuff)}")
# Срез (создает НОВЫЙ список) - O(k), где k - размер среза
sub_list = my_stuff[1:4] # Элементы с индексами 1, 2, 3
print(f"Срез [1:4]: {sub_list}")Что под капотом у списков?
Чтобы понять, почему одни операции со списками быстрые, а другие — нет, нужно заглянуть под капот. В стандартной реализации Python (CPython) списки реализованы как динамический массив. Это, по сути, непрерывный блок памяти, хранящий ссылки на объекты списка.
Когда вы добавляете элемент, а в блоке еще есть место, Python просто кладет ссылку в следующую свободную ячейку. Но что, если место кончилось? Python выделяет новый блок памяти, побольше (с запасом, чтобы не делать это постоянно), копирует туда все старые ссылки и только потом добавляет новую.
Когда вы добавляете элемент, а в блоке еще есть место, Python просто кладет ссылку в следующую свободную ячейку. Но что, если место кончилось? Python выделяет новый блок памяти, побольше (с запасом, чтобы не делать это постоянно), копирует туда все старые ссылки и только потом добавляет новую.
Это объясняет следующую временную сложность операций 👇🏻
👍 Быстрые операции
- Доступ по индексу (`items[i]`): O(1). Адрес элемента вычисляется мгновенно по формуле `адрес_начала + i * размер_ссылки `
- Получение длины (`len (items)`): O(1). Размер хранится отдельно, его не нужно считать.
- Добавление в конец (`items.append (x)`): Амортизированное O(1). Слово "амортизированное" значит, что в среднем это быстро. Большинство `append` просто добавляют ссылку в конец (O(1)). Изредка происходит переаллокация и копирование (O(n)), но это случается достаточно редко, чтобы средняя стоимость оставалась O(1).
- Удаление с конца (`items.pop ()`): O(1). Просто убираем последнюю ссылку и уменьшаем счетчик длины. Ничего сдвигать не нужно.
👎 Медленные операции (O(n))
- Вставка в начало или середину (`items.insert(i, x)`): O(n). Это главная "боль" списков! Чтобы вставить элемент на позицию `i`, все элементы начиная с `i` и до конца списка (а их может быть до `n`) должны сдвинуться в памяти на одну позицию вправо, чтобы освободить место. Вставка в самое начало (`insert(0, ...)`) — самый медленный случай, так как сдвигаются все `n` элементов.
- Удаление из начала или середины (`items.pop(i)`, `del items[i]`): O(n). Аналогично вставке: после удаления элемента на позиции `i`, все элементы справа от него должны сдвинуться на одну позицию влево, чтобы заполнить образовавшуюся "дыру". Удаление из начала (`pop(0)`) — тоже самый медленный случай.
- Поиск элемента по значению (`x in items`, `items.index(x)`): O(n). Чтобы найти элемент (или убедиться, что его нет), Python в худшем случае должен просмотреть каждый элемент списка один за другим.
Вывод: Списки идеальны для доступа по индексу и операций в конце структуры. Но если вам часто нужно вставлять/удалять элементы в начале или середине, или часто искать элементы по значению в больших коллекциях — списки могут стать узким местом.
Давайте наглядно увидим разницу во времени выполнения `append` и `insert` с помощью модуля `time`:
import time
n = 200000 # Достаточно большой размер для наглядности
print(f"\nСравнение производительности для {n} элементов:")
# --- Замеряем append (O(1) амортизированно) ---
big_list_append = []
start_time_append = time.perf_counter() # Используем perf_counter для более точных замеров
for i in range(n):
big_list_append.append(i)
end_time_append = time.perf_counter()
print(f" Время append {n} элементов: {end_time_append - start_time_append:.6f} сек")
# --- Замеряем insert(0, ...) (O(n)) ---
# Делаем в 10 раз меньше итераций, т.к. insert(0) намного медленнее!
iterations_insert = n // 10
big_list_insert = []
start_time_insert = time.perf_counter()
for i in range(iterations_insert):
big_list_insert.insert(0, -i) # Вставляем в начало
end_time_insert = time.perf_counter()
print(f" Время insert(0, ...) {iterations_insert} элементов: {end_time_insert - start_time_insert:.6f} сек")
# Очевидно, что insert(0,...) намного медленнее на больших n, даже при меньшем числе операцийКогда использовать списки? Списки — отличный выбор, когда:
- Нужна упорядоченная коллекция.
- Часто нужен доступ к элементам по индексу.
- Основные операции добавления/удаления происходят в конце (`append`, `pop`).
- Коллекция не гигантская, или операции со сложностью O(n) (вставка/удаление в середине/начале, поиск по значению) выполняются редко.
Если же вам нужна скорость с обоих концов (как для очереди), присмотритесь к `collections.deque`. А если нужна неизменяемость или возможность использовать коллекцию как ключ словаря — вам к кортежам. О них — прямо сейчас!
Кортежи (tuple): неизменяемые братья списков
Кортежи на первый взгляд очень похожи на списки: это тоже упорядоченные коллекции, способные хранить элементы разных типов. Вы так же можете получить доступ к элементу по индексу или сделать срез.
# Создание кортежа - круглые скобки (или их отсутствие)
point_3d = (10.0, -5.5, 2.0)
api_key_info = "user123", "secret_key", True # Скобки не обязательны
empty_tuple = ()
print(f"3D Точка: {point_3d}")
print(f"API Инфо: {api_key_info}")
print(f"Тип: {type(point_3d)}") # <class 'tuple'>
# Доступ и срезы - как у списков (O(1) и O(k))
print(f"Координата X: {point_3d[0]}")
print(f"Ключ и статус: {api_key_info[1:]}") # ('secret_key', True)Нюанс: как создать кортеж из одного элемента? Просто (42) не сработает — Python подумает, что это число 42 в скобках (которые используются для приоритета операций). Нужно поставить запятую после элемента!
single_element_tuple = (42,) # Вот так!
also_a_tuple = 42, # И так тоже можно
not_a_tuple = (42) # А это просто int
print(f"\nТип (42,): {type(single_element_tuple)}") # <class 'tuple'>
print(f"Тип (42): {type(not_a_tuple)}") # <class 'int'>Так в чем же соль? Фундаментальное отличие, которое определяет всю суть кортежей: они НЕИЗМЕНЯЕМЫ.
После того как кортеж создан, вы не можете:
А любая операция, которая "изменяет" кортеж (например, конкатенация), на самом деле создает НОВЫЙ кортеж.
После того как кортеж создан, вы не можете:
- Изменить существующий элемент.
- Добавить новый элемент.
- Удалить элемент.
А любая операция, которая "изменяет" кортеж (например, конкатенация), на самом деле создает НОВЫЙ кортеж.
config = ("localhost", 8080)
print(f"\nКонфиг: {config}, id: {id(config)}")
try:
# Пытаемся изменить порт - Не выйдет!
config[1] = 9000
except TypeError as e:
print(f" Ошибка изменения: {e}")
# Вывод: Ошибка изменения: 'tuple' object does not support item assignment
# Любая "модификация" (конкатенация) создает НОВЫЙ кортеж
new_config = config + (True,) # Добавим флаг SSL
print(f"Новый конфиг: {new_config}, id: {id(new_config)}") # Другой id!
print(f"Старый конфиг не изменился: {config}, id: {id(config)}") # Старый id!Преимущества неизменяемости
На первый взгляд, это ограничение кортежей. Но на практике неизменяемость дает кортежам несколько ключевых преимуществ.
- Гарантия целостности данных. Если у вас есть набор значений, который по логике не должен меняться (координаты, RGB цвет, версия ПО, неизменяемые настройки), кортеж — это ваша страховка. Никакая заблудшая часть кода случайно не изменит эти данные. Код становится надежнее и предсказуемее. 👍
- Производительность и оптимизация (микро-бонус). Иногда кортежи могут быть чуть компактнее в памяти и чуточку быстрее при доступе, чем списки с теми же данными. Но эта разница обычно невелика и редко бывает решающим фактором.
- Хешируемость. Вот это действительно важно! Поскольку кортежи неизменяемы, Python может вычислить для них хеш — уникальное (в идеале) числовое представление объекта, которое не меняется. А зачем это нужно? Потому что ключи словарей и элементы множеств в Python ОБЯЗАНЫ быть хешируемыми!
Важное исключение: Кортеж хешируем только тогда, когда все его элементы хешируемы. Если кортеж содержит изменяемый объект (например, список), то сам кортеж становится нехешируемым.
Когда использовать кортежи?
- Для представления неизменяемых наборов данных.
- Когда требуется хешируемая последовательность (например, для использования в качестве элементов множеств, о которых мы скоро поговорим).
- Для возврата нескольких значений из функции (`return x, y` неявно создает кортеж `(x, y)`).
- Как простую, легковесную структуру для хранения небольшого фиксированного числа полей (иногда альтернатива простым классам).
- В редких случаях для микрооптимизации.
А что, если порядок нам не важен, а главное — уникальность элементов и сверхбыстрая проверка на наличие?
Множества (set, frozenset): уникальность и скорость, порядок не важен
Представьте, что вам нужно хранить коллекцию элементов, но вас интересует только факт наличия элемента, а не его порядок или количество копий. Например, список уникальных IP-адресов, посетивших сайт, или набор разрешенных прав доступа для пользователя. Для таких задач в Python есть множества.
Какие у них свойства?
- Неупорядоченность. Элементы не хранятся в каком-либо предсказуемом порядке. Порядок при итерации может меняться.
- Уникальные элементы. Каждый элемент может содержаться во множестве только один раз. Дубликаты автоматически игнорируются.
- Хешируемые элементы. Элементами множества могут быть только объекты неизменяемых, хешируемых типов (числа, строки, bool, `None`, `bytes`, кортежи из хешируемых элементов). Помните, мы обсуждали хешируемость кортежей? Вот одно из мест, где это свойство критически важно! Изменяемые `list` или другие `set` не могут быть элементами множества.
# Создание множества из списка - дубликаты 'web', 'python' 101 уйдут
# True схлопнется с 1 (т.к. True == 1 и hash(True) == hash(1))
raw_tags = ['python', 'web', 101, True, 'api', 'python', 101, 1]
unique_tags = set(raw_tags)
print(f"Исходные теги: {raw_tags}")
print(f"Уникальные теги (set): {unique_tags}")
# {1, 'web', 'api', 'python'} (порядок не гарантирован!)
# Создание с помощью литерала {...}
# (Внимание: {} - это пустой СЛОВАРЬ, не множество!)
languages = {'python', 'java', 'javascript', 'python'} # Дубликат 'python' игнорируется
print(f"Языки: {languages}")
# {'javascript', 'python', 'java'}
# Создание ПУСТОГО множества - ТОЛЬКО через set()
empty_set = set()
possibly_a_dict = {} # Это словарь!
print(f"Пустое множество: {empty_set}, тип: {type(empty_set)}")
print(f"Пустой объект от {}: {}, тип: {type(possibly_a_dict)}")Внутреннее устройство: хеш-таблицы
Внутренняя структура данных, на которой основаны множества — хеш-таблицы. Представьте себе большую "картотеку" с множеством пронумерованных ящиков (или "корзин" — buckets). Когда вы хотите добавить новый элемент (например, строку "python") во множество:
- Вычисляется хеш. Сначала Python вычисляет специальное числовое значение для этого элемента — его хеш (`hash("python")` -> какое-то большое число). Важно, что для одинаковых элементов хеш всегда будет одинаковым, и вычисляется он очень быстро.
- Определение "корзины" (bucket). По этому хешу (обычно через остаток от деления на размер таблицы) Python определяет номер ящика, куда положить (или где искать) этот элемент.
- Обработка коллизий. Что если два разных ключа дадут одинаковый хеш или попадут в одну и ту же корзину? Это называется коллизией. Python имеет механизмы для их разрешения (например, хранение цепочек элементов в одной корзине или использование "открытой адресации" для поиска следующего свободного слота). Хорошая хеш-функция и правильное управление размером таблицы минимизируют коллизии.
- Изменение размера. Чтобы поддерживать низкое количество коллизий и высокую производительность, Python автоматически увеличивает размер внутренней хеш-таблицы и перехеширует все элементы, когда таблица становится слишком заполненной (обычно при заполнении на 2/3).
И когда вы, например, проверяете `if "python" in my_set:`, Python:
Именно поэтому операции `in`, `add`, `remove`/`discard` в среднем выполняются за O(1) — их время выполнения почти не зависит от общего числа элементов во множестве, а зависит только от того, насколько "заполнена" конкретная корзина.
- Вычисляет hash("python").
- Определяет номер нужного ящика (`индекс = hash("python") % количество_ящиков`).
- Смотрит ТОЛЬКО В ЭТОТ ЯЩИК! Ему не нужно перебирать все остальные элементы.
Именно поэтому операции `in`, `add`, `remove`/`discard` в среднем выполняются за O(1) — их время выполнения почти не зависит от общего числа элементов во множестве, а зависит только от того, насколько "заполнена" конкретная корзина.
set — изменяемый вариант
Множества, созданные через `set()` или литерал `{элементы...}`, являются изменяемыми. Вы можете добавлять и удалять элементы после создания.
active_users = {'user1', 'user3'}
print(f"\nАктивные пользователи: {active_users}")
# Добавление (O(1) в среднем)
active_users.add('user2')
print(f"Добавили user2: {active_users}") # Порядок не гарантирован
active_users.add('user1') # Добавление существующего - ничего не меняет
print(f"Попытка добавить user1: {active_users}")
# Удаление - remove() (O(1) в среднем)
active_users.remove('user3') # Удаляет элемент. Вызовет KeyError, если элемента нет.
print(f"Удалили user3: {active_users}")
# active_users.remove('user99') # <-- Вызовет KeyError
# Безопасное удаление - discard() (O(1) в среднем)
active_users.discard('user1') # Пытается удалить 'user1'. Успешно.
print(f"Удалили user1 через discard: {active_users}")
active_users.discard('user99') # Пытается удалить 'user99'. Его нет, но ошибки НЕТ.
print(f"Попытка удалить user99 через discard: {active_users}")
# Очистка множества
active_users.clear() frozenset — неизменяемый и хешируемый вариант
Поскольку `set` изменяемы, они не являются хешируемыми. Вы не можете использовать `set` как элемент другого множества.
Для этих целей существует `frozenset` — это неизменяемая версия множества. Она поддерживает все операции, не изменяющие множество (проверка `in`, математические операции), но не имеет методов `add`, `remove`, `discard `и т.п. Зато frozenset хешируем.
Для этих целей существует `frozenset` — это неизменяемая версия множества. Она поддерживает все операции, не изменяющие множество (проверка `in`, математические операции), но не имеет методов `add`, `remove`, `discard `и т.п. Зато frozenset хешируем.
# Создание frozenset
read_only_permissions = frozenset(['read', 'list'])
admin_permissions = frozenset(['read', 'write', 'delete', 'list'])
print(f"\nПрава на чтение: {read_only_permissions}")
# read_only_permissions.add('write') # Вызовет AttributeError!
# Использование frozenset как ЭЛЕМЕНТА другого множества
# (Обычный set так использовать нельзя!)
common_permission_sets = {read_only_permissions, admin_permissions}
print(f"Наборы прав: {common_permission_sets}")
# Наборы прав: {frozenset({'list', 'read'}), frozenset({'write', 'list', 'delete', 'read'})}
# Проверка хешируемости
print(f"read_only хешируем? {'Да' if hash(read_only_permissions) else 'Нет'}")Математические операции над множествами
Множества идеально подходят для выполнения стандартных операций теории множеств. Они реализованы очень эффективно (часто быстрее, чем если бы вы делали то же самое со списками в циклах).
programmers = {'Анна', 'Борис', 'Виктор', 'Галина'}
testers = {'Виктор', 'Галина', 'Дарья'}
managers = {'Егор', 'Жанна'}
# Объединение (| или .union()): Все уникальные сотрудники IT-отдела
it_department = programmers | testers | managers
print(f"Весь IT-отдел: {it_department}") # {'Борис', 'Галина', 'Егор', 'Дарья', 'Виктор', 'Анна', 'Жанна'}
# Пересечение (& или .intersection()): Кто и разработчик, И тестировщик?
dev_and_qa = programmers & testers
print(f"И разработчики, и QA: {dev_and_qa}") # {'Виктор', 'Галина'}
# Разность (- или .difference()): Кто разработчик, но НЕ тестировщик?
only_programmers = programmers - testers
print(f"Только разработчики: {only_programmers}") # {'Борис', 'Анна'}
# Симметрическая разность (^ или .symmetric_difference()): Кто только в одной из групп (программисты ИЛИ тестировщики, но не в обеих)?
exclusive_roles = programmers ^ testers
print(f"Только в одной роли (Прог/QA): {exclusive_roles}") # {'Борис', 'Дарья', 'Анна'}
# Проверка на подмножество/надмножество (<=, >=, <, > или .issubset(), .issuperset())
print(f"dev_and_qa - подмножество programmers? {dev_and_qa <= programmers}") # True
print(f"programmers - надмножество testers? {programmers >= testers}") # FalseКогда использовать set / frozenset?
- Для быстрого удаления дубликатов из любой последовательности.
- Когда критически важна быстрая (O(1)) проверка принадлежности элемента к коллекции (`in`).
- Для выполнения эффективных теоретико-множественных операций (объединение, пересечение, разность и т.д.).
- Используйте `frozenset`, когда вам нужен неизменяемый набор или вы хотите использовать его в качестве ключа словаря или элемента другого множества.
Итого: множества — отличный инструмент, когда порядок не важен, а уникальность и скорость проверки — да. Теперь, когда мы знаем о них и о хешируемости, мы готовы к словарям!
Словари (dict): связка ключ-значения и (почти) O(1) доступ
Словари используют ту же самую идею хеш-таблиц, что и множества, но идут на шаг дальше: они позволяют связать с каждым уникальным хешируемым ключом (key) некоторое значение (value).
Думайте о словаре как об идеальной картотеке или адресной книге: по уникальному идентификатору (имени человека, артикулу товара, ID пользователя) вы мгновенно находите всю связанную с ним информацию.
Ключевые характеристики словарей
- Пары ключ-значение. Основа словаря. Каждый элемент — это пара.
- Уникальные и хешируемые ключи. Все ключи в пределах одного словаря должны быть уникальны. Если вы попытаетесь присвоить значение по уже существующему ключу, старое значение будет перезаписано. И ключи должны быть хешируемыми (неизменяемыми типами, для которых можно вычислить хеш — строки, числа, `bool`, `None`, кортежи из хешируемых типов, `frozenset`). Изменяемые типы (`list`, `set`, другие `dict`) ключами быть не могут.
- Произвольные значения. значениями могут быть объекты абсолютно любого типа (включая списки, другие словари, функции, объекты классов).
- Изменяемость. Словари можно изменять после создания: добавлять новые пары, удалять существующие, обновлять значения по ключу.
- Динамический размер. Словари могут менять длину при добавлении/удалении элементов.
- Сохранение порядка вставки. Исторически словари были неупорядоченными (порядок обхода не гарантировался). Но в современных версиях Python (CPython 3.6+, стандарт 3.7+) словари помнят порядок, в котором элементы были в них добавлены.
phone_book = {
"Иван": "+7-911-...",
"Мария": "+7-922-...",
"Сергей": "+7-933-..."
}
# Разные типы ключей и значений
item_info = {
"id": 10542,
"name": "Чайник",
"price": 1500.50,
"available": True,
("склад_1", "полка_3"): 5 # Кортеж как ключ - количество на складе
}
# Пустой словарь
empty_d = {} Производительность словарей
Словари используют хеш-таблицы точно так же, как и множества, но в "корзинах" хранятся не просто элементы, а пары ключ-значение. Когда вы обращаетесь к словарю по ключу (`my_dict[key]`), происходит следующее:
- Вычисляется `hash(key)`.
- По хешу определяется индекс корзины.
- В этой корзине ищется элемент с таким же ключом (с учетом возможной обработки коллизий).
- Если ключ найден, возвращается связанное с ним значение.
Благодаря этому (в среднем) операции со словарями очень быстрые.
- 👍 Доступ по ключу (`my_dict[key]`): O(1). Вычисление хеша и индекса корзины — быстрые операции.
- 👍 Вставка/обновление (`my_dict[key] = value`): амортизированное O(1). Обычно быстро, но иногда (при изменении размера таблицы) может занять O(n) для копирования, но в среднем остается O(1).
- 👍 Удаление (`del my_dict[key]`): O(1) (в среднем).
- 👍 Проверка наличия ключа (`key in my_dict`): O(1) (в среднем). Это гораздо быстрее, чем `key in my_list` (которое O(n)).
Это делает словари идеальными для задач, где нужен быстрый поиск, добавление или удаление по уникальному идентификатору.
# Доступ (O(1))
ivan_phone = phone_book["Иван"]
print(f" Телефон Ивана: {ivan_phone}")
# Безопасный доступ .get() (O(1))
olga_phone = phone_book.get("Ольга", "Контакт не найден")
print(f" Телефон Ольги: {olga_phone}")
# Вставка/Обновление (Аморт. O(1))
phone_book["Ольга"] = "+7-955-..." # Вставка
phone_book["Иван"] = "+7-911-111-11-11" # Обновление
print(f" Добавлена Ольга, обновлен Иван.")
# Удаление (O(1))
removed_who = phone_book.pop("Сергей") # Удаляет пару и возвращает значение
print(f" Удален Сергей (тел: {removed_who}).")
print(f" Текущая книга: {phone_book}")
# Проверка наличия ключа (O(1))
if "Мария" in phone_book:
print(f" Контакт 'Мария' есть.")Итерация по словарю (O(n))
Обход всех `n` элементов словаря, естественно, требует времени O(n). В Python есть такие способы это сделать:
# По ключам (по умолчанию)
print(" Ключи:", end=" ")
for name in phone_book:
print(name, end=" ")
# По значениям (используем .values())
print(" Телефоны:", end=" ")
for phone in phone_book.values():
print(phone, end=" ")
# По парам ключ-значение (используем .items())
print(" Записи:", end=" ")
for name, phone in phone_book.items():
print(f"({name}: {phone})", end=" ") Важно: методы `.keys()`, `.values()`, `.items()` в Python возвращают представления (views), а не создают полные копии списков ключей/значений/пар. Это экономит память, особенно для больших словарей. Представления динамически отражают изменения в словаре.
Когда использовать словари?
- Для сопоставления уникальных идентификаторов (ключей) со значениями (информация о пользователе, настройки, счетчики, переводы и т.д.).
- Когда нужен мгновенный (O(1)) доступ, вставка или удаление по ключу.
- Для представления структурированных данных (конфиги, JSON-подобные объекты, записи из БД).
- Для подсчета частоты элементов или группировки данных.
- В качестве кеша для мемоизации в динамическом программировании (увидим в следующих частях гайда).
- Везде, где важна связь "ключ-значение", а не строгий числовой порядок как в списках.
Словари лежат в основе многих механизмов самого Python (например, пространства имен объектов реализованы через словари). Понимание их работы очень важно.
Заключение: фундамент заложен!
Итак, мы завершили первую часть нашего путешествия по миру структур данных и алгоритмов Python, сосредоточившись на встроенных инструментах, которые язык предоставляет нам "из коробки".
Теперь мы можем не просто использовать их, а делать это осознанно, выбирая правильный инструмент для каждой задачи
Теперь мы можем не просто использовать их, а делать это осознанно, выбирая правильный инструмент для каждой задачи
Главный вывод
Понимание того, как эти структуры данных работают под капотом и какова асимптотическая сложность (Big O) их операций — это не занудная теория, а практическая необходимость. Знание, когда список начнет тормозить, а множество или словарь справятся мгновенно, отличает просто работающий код от эффективного. Особенно когда объемы данных начинают расти (а они всегда начинают расти 😉).
В следующей части мы:
- Познакомимся с `collections.deque` — как стандартная библиотека решает проблему медленных операций в начале списка, создавая эффективные очереди и стеки.
- Погрузимся в классическую концепцию связанных списков, что важно для понимания более сложных структур данных.
