2learn

Данные и итерация

Что это такое

Встроенные коллекции Python — список, кортеж, словарь и множество — плюс синтаксис включений и протокол итерации, который все они реализуют: словарь отображает ключи в значения с быстрым поиском, множество хранит уникальные значения, список остаётся упорядоченной изменяемой последовательностью, а кортеж — упорядоченной неизменяемой. Итерация — не синтаксис, а протокол: в цикле может стоять всё, что умеет выдавать значения по одному.

Почему это важно

Выбор подходящей коллекции — самое крупное решение о производительности в обычном коде на Python, куда крупнее, чем микрооптимизация цикла: поиск в словаре занимает фактически константное время, тогда как проход по списку пропорционален его длине. Поэтому программа, которая ищет по списку внутри цикла, может оказаться квадратичной, хотя по виду этого не скажешь. Итерация важна по той же причине: генератор, который выдаёт значения по требованию, держит память плоской там, где список хранил бы всё сразу.

Ключевые идеи

Четыре коллекции отвечают на разные вопросы

Список отвечает на вопрос «что стоит на позиции n» и сохраняет порядок, словарь быстро отвечает на вопрос «какое значение у этого ключа», множество быстро отвечает «есть ли это здесь» и убирает дубликаты, а кортеж — упорядоченное значение, которое нельзя изменить и потому можно взять в качестве ключа словаря. Выбор делают по вопросу, который код задаёт чаще всего, а не по тому, какой тип привычнее.

members = [1, 2, 3]                 -> упорядочен, индексируется, поиск — скан
index   = {1: "a", 2: "b"}         -> поиск по ключу за константное время
unique  = {1, 2, 3}                -> проверка вхождения за константное время
point   = (3, 4)                   -> неизменяем, годится как ключ

Включения выражают преобразование без обвязки цикла

Включение строит коллекцию из итерируемого объекта одним выражением, при необходимости с фильтром, и читается оно, пока остаётся близко к естественному языку; вложенное или несущее побочные эффекты включение становится враждебным. Полезное правило здесь — держать один for и не больше одного if, а иначе писать обычный цикл.

Итерация ленива, а генераторы делают её ленивее

В цикле for может стоять всё итерируемое, включая файл, курсор базы данных и генератор. Функция-генератор выдаёт значения по мере запроса, поэтому конвейер из генераторов обрабатывает по одному элементу и держит в памяти только текущий, — а значит, справляется и с файлом, который больше памяти.

def rows(path):
    with open(path) as f:
        for line in f:
            yield line.strip()

Сортировка и группировка опираются на ключи и словари

Сортировка принимает функцию-ключ, а не сравнение, и это оставляет частые случаи короткими. Группировка обычно идёт через словарь со списками в значениях, а приём с setdefault или defaultdict убирает ветку, которая иначе стояла бы перед каждым добавлением; вместе это обычный способ превратить поток записей в структуру.

Копирование поверхностно, пока не сказано иное

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

Порядок словаря теперь гарантирован, но это не повод на него полагаться

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

Практика

Замените квадратичный скан поиском

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

Готово, когда: переписанная версия даёт те же результаты на тех же входных данных и вы можете сказать, почему её стоимость больше не пропорциональна обеим длинам.

Обработайте большой файл лениво

Напишите конвейер из функций-генераторов, который читает файл, фильтрует строки и выдаёт преобразованное значение, и убедитесь, что память не растёт вместе с файлом.

Готово, когда: файл, в несколько раз больший доступной памяти, обрабатывается успешно и даёт тот же результат, что и неленивая версия на маленьком входе.

Частые ошибки

  • Поиск по списку внутри цикла — стоимость становится квадратичной; исправить: используйте множество или словарь для вхождения и поиска.
  • Построение списка, когда нужен только первый подходящий элемент — память и время уходят на значения, которые отбрасываются; исправить: используйте генератор или выйдите из цикла.
  • Поверхностное копирование вложенных структур — внутренние объекты всё ещё общие; исправить: копируйте глубоко или, лучше, считайте данные неизменяемыми.
  • Вложенные включения ради них самих — выражение перестаёт читаться; исправить: используйте цикл с именем для каждого шага.
  • Порядок словаря как условие корректности — порядок идёт от вставки, а не от замысла; исправить: используйте явно упорядоченную структуру, когда порядок важен.

Что читать дальше

Разобранные примеры

Файлы cookie аналитики ставятся только с вашего согласия. До вашего выбора ничего не загружается и никуда не отправляется.