Всегда ли быстрее использовать строку в качестве ключа в dict?

На этой странице я вижу что-то интересное:

Обратите внимание, что существует быстрый путь для dicts, который (на практике) касается только str-ключей; это не влияет на алгоритмическую сложность, но может существенно повлиять на постоянные факторы: как быстро заканчивается типичная программа.

Так что это значит?

Это означает использование строки, поскольку ключ всегда быстрее?

Если да, то почему?

Update:

Спасибо за предложения по оптимизации! Но на самом деле меня больше интересует простая истина, чем то, как или когда мы должны делать оптимизацию.

Обновление 2:

Спасибо за отличные ответы, я приведу контент из , предоставленный @DaveWebb здесь:

" ...

ma_lookup изначально устанавливается в функцию lookdict_string (переименована в lookdict_unicode в 3.0), которая предполагает, что оба ключа в словаре и поиск ключа - это стандартные PyStringObject. Затем он может сделать пару оптимизаций, таких как смягчение различных проверок ошибок, поскольку сравнение строк с строкой никогда не вызывает исключений. Также нет необходимости в сравнении с богатыми объектами, что означает, что мы не вызываем PyObject_RichCompareBool и всегда используем _PyString_Eq.

... "

Кроме того, для чисел эксперимента я думаю, что размер разницы будет еще больше, если нет преобразования int-to-string

Ответ 1

C-код, лежащий в основе Python dict, оптимизирован для клавиш String. Вы можете прочитать об этом здесь (и в книге, на которую ссылается блог).

Если среда выполнения Python знает, что ваш dict содержит только строковые ключи, он может делать такие вещи, как не учитывать ошибки, которые не могут произойти со строкой для сравнения строк и игнорировать операторы сравнения. Это сделает обычный случай строкового ключа только dict немного быстрее. (Обновление: время показывает, что это немного больше.)

Однако маловероятно, что это значительно изменило бы время выполнения большинства программ Python. Только беспокоитесь об этой оптимизации, если вы измерили и обнаружили, что поиск dict является узким местом в вашем коде. Как говорится в знаменитой цитате, "Преждевременная оптимизация - это корень всего зла" .

Единственный способ увидеть, насколько на самом деле быстрее, - это время:

>>> timeit.timeit('a["500"]','a ={}\nfor i in range(1000): a[str(i)] = i')
0.06659698486328125
>>> timeit.timeit('a[500]','a ={}\nfor i in range(1000): a[i] = i')
0.09005999565124512

Таким образом, использование строковых ключей примерно на 30% быстрее даже по сравнению с int ключами, и я должен признать, что я был удивлен размером разницы.

Ответ 2

Поскольку это влияет только на постоянное время, оно, вероятно, вообще не имеет значения. Единственный раз, когда вы действительно нуждаетесь в оптимизации, - это когда вы работаете с очень большими наборами данных, что не влияет на это.

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

Как указывает Игнасио Васкес-Абрамс, вероятно, что преобразование вашего ключа в строку будет стоить (намного) больше, чем небольшое повышение, которое вы могли бы получить от него, являясь строкой для dict.

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

Некоторые тесты:

python -m timeit -s "a={key: 1 for key in range(1000)}" "a[500]"
10000000 loops, best of 3: 0.0773 usec per loop

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[\"500\"]"
10000000 loops, best of 3: 0.0452 usec per loop

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[str(500)]"
1000000 loops, best of 3: 0.244 usec per loop

Как вы можете видеть, в то время как строковый dict быстрее, преобразование ключа очень дорого по сравнению, полностью уменьшая коэффициент усиления (а затем и некоторые).

Итак, да, если используемые вами данные только используются в качестве ключей к словарю, и в каком формате ваш магазин их не имеет значения, тогда строки предпочтительнее в небольшом словаре, На практике это очень редкий случай (и вы, вероятно, уже используете строки).