Как выбрать структуру данных
Также: Choosing a data structure · какую структуру взять · list или set · slice или map · шпаргалка по структурам данных · стоимость операций
Выбор структуры начинается не с названия, а со списка операций, которые нужны задаче. Цена одной и той же операции в list и set, срезе и map различается в сотни и тысячи раз — на замере это от единиц наносекунд до миллисекунд. Карта стоимостей Python и Go, правило выбора и случай, когда честный ответ — держать две структуры сразу.
Программа проверяет, был ли пользователь уже в рассылке, — if user in sent — и sent у неё список. На сотне адресов это незаметно. На ста тысячах каждая проверка просматривает весь список, и цикл по новым адресам из минуты превращается в час. Поменять одну скобку — sent = set() вместо sent = [] — и та же проверка станет в тысячи раз дешевле. Ниже — сколько стоят основные операции в стандартных структурах Python и Go, измеренные на сервере сайта.
Карта читается по строкам: для каждой операции зелёные клетки — структуры, где она стоит меньше двух микросекунд, красные — где от двадцати микросекунд до миллисекунд. Отметьте операции, которые нужны вашей задаче: сцена покажет, какая структура делает всё дёшево, а если такой нет — какие две делают это вместе. Например, «есть ли x», «добавить» и «достать минимум» вместе не умеет ни одна: множество не знает порядка, куча не умеет быстро искать, а отсортированный массив дорого вставляет. Держат две.
Идея
Сначала выпишите операции, которые программа будет делать часто, и для каждой — сколько раз. Потом найдите структуру, где все частые операции дешёвые. Если такой нет, держите несколько структур над одними данными, каждую для своих операций, и обновляйте их вместе. Стоимость редких операций почти не важна: программа, которая миллион раз ищет и один раз сортирует, должна быть быстрой в поиске.
Это и есть ответ на вопрос «что быстрее — список или множество»: смотря для чего. Добавить в конец списка дешевле, чем в множество, — не нужно считать хеш. Проверить, есть ли элемент, в множестве дешевле в тысячи раз. Устройство каждой структуры разобрано в своей статье — динамический массив, хеш-таблица, двоичная куча, стек и очередь, связный список; здесь они собраны на одной карте.
Шпаргалка
| Нужно часто | Python | Go | Почему |
|---|---|---|---|
| есть ли элемент | set, dict | map | хеш-таблица: O(1) в среднем |
| значение по ключу | dict | map | то же |
| по номеру, перебор подряд | list | срез | массив: O(1) по номеру, подряд — быстрее всего |
| с обоих концов | collections.deque | срез с концов или кольцевой буфер | O(1) на конце |
| минимум, следующий по приоритету | heapq | container/heap | куча: O(log n) |
| по порядку, ближайший, диапазон | отсортированный list и bisect | отсортированный срез и sort.Search | двоичный поиск O(log n), вставка O(n) — но быстрым сдвигом |
| порядок и частые вставки | сторонние: sortedcontainers | сторонние деревья | в стандартных библиотеках дерева поиска нет |
| вставка в середину у известного места | — | container/list | связный список: O(1), если место уже найдено |
Два различия между языками стоит запомнить. В Go снять элемент с начала среза ничего не стоит: a = a[1:] просто сдвигает начало, — а в Python list.pop(0) сдвигает весь хвост, и для очереди нужен deque. И наоборот, у Python есть готовое множество, а в Go множество делают из map[T]struct{} или map[T]bool.
Код
Одна задача — журнал заказов со сроками: добавить, отменить, есть ли такой срок, самый ранний срок, — и две реализации. Первая держит всё в списке. Вторая — словарь «срок → сколько заказов» для проверок и отмен и кучу для минимума, а отменённые сроки выбрасывает из кучи, только когда они всплывают наверх. Программа считает, сколько элементов потрогала каждая: это число не зависит от машины.
На тысяче операций список трогает в 60 раз больше элементов, на двадцати тысячах — в 900 раз: его работа растёт как квадрат длины журнала, а у словаря с кучей — почти линейно. Ответы при этом совпадают — это первое, что стоит проверить после смены структуры.
Сколько это стоит
Цена выбора — не только время. Две структуры над одними данными — это вдвое больше памяти и код, который должен обновлять обе согласованно: забыли уменьшить счётчик при отмене — и куча вернёт заказ, которого нет. Хеш-таблицы занимают больше массивов (сколько именно — в статье «Сколько займёт в памяти») и не хранят порядок. Отсортированный массив быстр на чтение, но каждая вставка сдвигает хвост.
Отсюда порядок действий. Простая структура, пока данных мало, — список и массив быстрее всех на сотне элементов. Прикидка, когда данных становится много: сколько операций каждого вида и сколько стоит каждая. И профилировщик, если программа медленная, а прикидка не объясняет почему: в профиле медленный x in list виден сразу.
Задачи
Задача — тот самый журнал заказов, где одной структуры мало.
Заказы по сроку