Какие стандартные коллекции есть в Python и их особенности

Что проверяют

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

Как отвечать

Начните со встроенных типов:

• list: изменяемый динамический массив. Доступ по индексу и append в конец за O(1) (амортизированно), вставка и удаление в начале или середине за O(n), потому что элементы сдвигаются;
• tuple: неизменяемая последовательность. Хэшируется, если хэшируются все элементы, поэтому годится в ключи словаря. Занимает чуть меньше памяти, чем список;
• dict: хэш-таблица, поиск, вставка и удаление по ключу в среднем за O(1). С Python 3.7 порядок вставки ключей гарантирован языком;
• set и frozenset: уникальные хэшируемые элементы, проверка in в среднем за O(1), объединение и пересечение. frozenset неизменяем и сам может быть ключом.

Затем модуль collections:

• deque: двусторонняя очередь, добавление и извлечение с обоих концов за O(1);
• defaultdict: создаёт значение фабрикой при обращении к отсутствующему ключу;
• Counter: подсчёт элементов, есть most_common();
• namedtuple: кортеж с доступом к полям по имени;
• OrderedDict и ChainMap: первый нужен ради move_to_end() и сравнения с учётом порядка, второй объединяет несколько словарей в одно представление.

Хорошо упомянуть heapq для очереди с приоритетом и array для компактного хранения чисел одного типа.

Где спотыкаются

Говорят, что проверка наличия в set работает за O(n). Это O(1) в среднем, а за O(n) идёт поиск in по списку, и ради этой разницы множество обычно и выбирают.

Делают очередь из списка через pop(0). Каждое извлечение сдвигает весь список, на больших объёмах это заметно, правильный инструмент deque.popleft().

Путают неизменяемость и хэшируемость. Кортеж со списком внутри нельзя положить в множество, hash() упадёт с TypeError. Сюда же ловушка [[]] * 3: три ссылки на один и тот же список.