Что хотят услышать интервьюеры:

Нужно показать, что у структур данных разные асимптотики по времени и памяти, и выбор зависит от типа операций: поиск, вставка, удаление, обход. Важно уметь сравнивать не “в целом быстрее”, а по конкретным сценариям использования. Также полезно понимать, что в Python у встроенных структур есть практические константы и реализация на C, поэтому в реальном коде они часто быстрее самодельных альтернатив.

Определение:

Показатели производительности структур данных — это обычно оценка времени выполнения операций и объёма памяти, который они потребляют. Чаще всего сравнивают сложность доступа по индексу, поиска элемента, добавления, удаления и перебора. Для этого используют нотацию Big O, например O(1), O(log n), O(n).

У разных структур разные сильные стороны:

list удобен для доступа по индексу и прохода по элементам.
set быстро проверяет наличие элемента.
dict быстро хранит и ищет пары ключ-значение.
deque удобен для операций с обоих концов.
tuple похож на list, но неизменяемый и обычно компактнее.

Пример использования:

Если нужно часто проверять, был ли элемент уже обработан, лучше взять set, а не list.

seen = set()

for value in data:
    if value in seen:
        continue
    seen.add(value)
    process(value)

Если нужно быстро обращаться к элементу по позиции, подходит list:

items = ["a", "b", "c"]
print(items[1])  # "b"

Пояснение кода:

Код показывает два типичных сценария.

В первом примере set используется для проверки уникальности:

value in seen обычно выполняется быстро;
seen.add(value) тоже обычно работает быстро;
это лучше, чем искать элемент в списке, где проверка наличия может занимать линейное время.

Во втором примере list используется для доступа по индексу:

items[1] возвращает второй элемент напрямую;
такой доступ обычно очень быстрый;
это удобно, когда важен порядок и позиция элемента.

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

Ключевые моменты:

Не существует “самой быстрой” структуры данных для всех задач.
Нужно сравнивать не структуру целиком, а конкретные операции: поиск, вставку, удаление, доступ.
list хорош для последовательного хранения и доступа по индексу, но поиск внутри списка — O(n).
set и dict обычно дают быстрый поиск и вставку в среднем, но требуют дополнительной памяти.
Выбор структуры данных часто важнее микрооптимизаций кода.
В Python встроенные структуры обычно предпочтительнее самописных из-за оптимизаций на уровне реализации.

Как отличаются показатели производительности различных структур данных?