Поиск будет быстрее в dict и set, потому что это хеш-таблицы, доступ к элементу которых выполняется за O(1). Для list и tuple поиск будет выполняться в среднем за O(n).

Исключение работает только для очень маленьких списков длиной до 5 элементов. В этом случае интерпретатору будет быстрей пробежаться по списку, чем считать хеш.

В Python 2 методы словаря keys, values, items возвращают список. То есть перед итерацией по словарю (или сету) интерпретатор сначала создает новый список, что занимает дополнительное время и память, но после создания это уже обыкновенный список. То есть в Python 2 итерация по словарям и сетам выполняется дольше за счет создания нового списка и копирования в него элементов.

В Python 3 эти методы создают объект-представление. Это определенно происходит быстрее, чем создание нового списка в Python2. Но итерирование по такому представлению должно происходить немного дольше, чем по списку из-за того, что данные в словарях хранятся разреженно (редко, негусто). В подтверждение вышесказанного (Python 3):

>>> l = list(range(1000000))
>>> d = dict.fromkeys(l)
>>> s = set(l)
>>> def iter_list():
...     for i in l:
...         pass
...
>>> def iter_dict():
...     for i in d:
...         pass
...
>>> def iter_set():
...     for i in s:
...         pass
...
>>> timeit.timeit(iter_list, number=1000)
 6.727667486004066
>>> timeit.timeit(iter_dict, number=1000)
 9.293120226997416
>>> timeit.timeit(iter_set, number=1000)
 8.627948219014797

 

Oct. 12, 2023, Источник

Вопрос о том, что быстрее - словарь или список, зависит от конкретной задачи и способа использования этих структур данных.

Если вам нужно осуществлять поиск элементов по ключу, то словарь (тип данных `dict`) будет быстрее списка (тип данных `list`). В словаре поиск элемента по ключу выполняется за время, близкое к O(1), в то время как в списке поиск элемента выполняется за время O(n), где n - это количество элементов в списке.

Однако, если вам нужно осуществлять доступ к элементам по индексу или выполнять итерацию по всем элементам в определенном порядке, то список может быть быстрее. В списке доступ к элементу по индексу выполняется за время O(1), в то время как в словаре доступ к элементу по ключу также выполняется за время, близкое к O(1), но требует дополнительных вычислений для хеширования ключа.

Выбор между словарем и списком зависит от конкретной задачи и требований к производительности. Если вам нужен быстрый поиск по ключу, используйте словарь. Когда вам нужно хранить элементы в определенном порядке или выполнить доступ к элементам по индексу, используйте список. В некоторых случаях также можно использовать компромисные решения, такие как использование списка кортежей (tuple) или списков словарей (list of dicts), чтобы объединить преимущества обеих структур данных.

Feb. 17, 2024, easyoffer