Как говорится в названии, насколько дорогими являются словари Python? Создание, вставка, обновление, удаление, все это.
Асимптотические временные сложности сами по себе интересны, но также и то, как они сравниваются, например, кортежей или обычных списков.
dicts (точно так же, как set, когда вам не нужно связывать значение с каждым ключом, а просто записывать, если ключ присутствует или отсутствует) довольно сильно оптимизированы. Создание dict из N ключей или пар ключ/значение значений равно O(N), выборка O(1), установка амортизируется O(1) и т.д. Невозможно сделать что-то существенно лучше для любого крошечного контейнера!
Для крошечных контейнеров вы можете легко проверить границы с помощью тестов timeit. Например:
$ python -mtimeit -s'empty=()' '23 in empty'
10000000 loops, best of 3: 0.0709 usec per loop
$ python -mtimeit -s'empty=set()' '23 in empty'
10000000 loops, best of 3: 0.101 usec per loop
$ python -mtimeit -s'empty=[]' '23 in empty'
10000000 loops, best of 3: 0.0716 usec per loop
$ python -mtimeit -s'empty=dict()' '23 in empty'
10000000 loops, best of 3: 0.0926 usec per loop
это показывает, что проверка членства в пустых списках или кортежах выполняется быстрее, на 20-30 наносекунд, чем проверка членства в пустых наборах или dicts; когда каждая наносекунда имеет значение, эта информация может иметь отношение к вам. Перемещение немного...:
$ python -mtimeit -s'empty=range(7)' '23 in empty'
1000000 loops, best of 3: 0.318 usec per loop
$ python -mtimeit -s'empty=tuple(range(7))' '23 in empty'
1000000 loops, best of 3: 0.311 usec per loop
$ python -mtimeit -s'empty=set(range(7))' '23 in empty'
10000000 loops, best of 3: 0.109 usec per loop
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '23 in empty'
10000000 loops, best of 3: 0.0933 usec per loop
вы видите, что для контейнеров из 7 предметов (не считая интереса) баланс производительности сместился, и теперь дикты и наборы имеют преимущества сотнями наносекунд. Когда присутствует интересный элемент:
$ python -mtimeit -s'empty=range(7)' '5 in empty'
1000000 loops, best of 3: 0.246 usec per loop
$ python -mtimeit -s'empty=tuple(range(7))' '5 in empty'
1000000 loops, best of 3: 0.25 usec per loop
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '5 in empty'
10000000 loops, best of 3: 0.0921 usec per loop
$ python -mtimeit -s'empty=set(range(7))' '5 in empty'
10000000 loops, best of 3: 0.112 usec per loop
dicts и sets не получают многого, но кортежи и список делают, даже если dicts и set остаются значительно быстрее.
И так далее, и т.д. - timeit делает тривиально легко запускать микро-тесты (строго говоря, гарантируется только для тех чрезвычайно редких ситуаций, когда наносекунды имеют значение, но, достаточно легко сделать, что нет большие трудности для проверки ДРУГИХ случаев; -).
Словари - одна из наиболее сильно настроенных частей Python, так как они лежат в основе столь большого количества языка. Например, члены класса и переменные в кадре стека хранятся внутри словарей. Они будут хорошим выбором, если они являются правильной структурой данных.
Выбор между списками и dicts на основе производительности кажется странным: они делают разные вещи. Возможно, вы можете рассказать нам больше о проблеме, которую вы пытаетесь решить.