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

21

На этомстраницаВижу что-то интересное

Note that there is a fast-path for dicts that (in practice) only deal with str keys; this doesn't affect the algorithmic complexity, but it can significantly affect the constant factors: how quickly a typical program finishes.

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

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

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

Update:

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

Update 2:

Спасибо за отличные ответы. Я процитирую содержаниессылка на сайт предоставлено @DaveWebb здесь:

" ...

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

... "

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

@ Lattyware Ах, я понимаю. Хотя я все еще могу представить себе случаи, когда вы могли бы показать улучшение от предварительной конвертации строк. Wilduck
@ Wilduck Я не говорю о строительстве. Если ваши ключи не были строками для начала, каждый раз, когда вам нужно выполнить поиск, вам нужно будет преобразовать ваш ключ в строку. (Если вы не делаете что-то тривиальное со словарем). Gareth Latty
Я думаю, все сводится к тому, как быстро__hash__ Метод ключевого объекта есть. Я предполагаю, что довольно просто хэшировать строку, но мне было бы очень интересно узнать, какая часть поиска в словаре тратится на хеширование. Wilduck
Ваше обновление ничего не меняет. Нет, в большинстве случаев это не будет быстрее, если ваши ключи не были строками. Gareth Latty
@ Lattyware связанная страница, кажется, подразумевает увеличение скоростиfor each lookup не только для строительства. Wilduck

Ваш Ответ

2   ответа
8

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

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

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

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

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

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 быстрее, преобразование ключа очень дорого по сравнению, полностью уменьшая усиление (а затем и некоторые).

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

Тем более что преобразование некоторых типов в строку может быть более дорогостоящим, чем просто использование их в качестве ключа.
+1 для & quot; используйте то, что имеет отношение к вашей ситуации. & Quot; При этом было бы очень интересно построить ситуацию, в которой использование только строковых ключей показывает значительное улучшение. Насколько экстремальной должна быть ситуация?
@ Wilduck Как я уже сказал, он покажет наибольшую выгоду в небольших словарях, где ключи должны были быть строками. При любом большом диктанте переменный фактор времени уничтожит постоянный выигрыш, который он вам дает. Если вы конвертируете в строку, это сведет на нет все выгоды.
извините, думаю, мне следует изменить мой вопрос xvatar
@ IgnacioVazquez-Abrams Очень верно.
19

Код C, который лежит в основе Python, оптимизирован для ключей 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 ключи, и я должен признать, что я был удивлен размером разницы.

Ваш тест предполагает, что получение"500" в отличие от500 - что имеет огромное значение - см. мой ответ.
Я не думаю, что ваш пример доказывает, что он медленен для "любого способа получения ключей строки". На ум приходит пример объекта сотрудника с уникальным строковым атрибутом идентификатора сотрудника; конечно, искусственный пример, но в этом есть смысл. И, как я уже сказал, если вы делаете такую оптимизацию, вы все равно будете измерять и сравнивать.
Это выводит его из контекста. Нет смысла знать, что строковые ключи быстрее использовать, если любой способ получить строковые ключи замедляет его.
Вопрос задал вопрос, всегда ли строковые ключи были быстрее, и мой тест должен был показать, что он сделал. Я не думаю, что вопрос заключался в том, чтобы задать вопрос о преобразовании из другого объекта в строку и использовать его в качестве ключа - что было бы плохо по ряду причин - но скорее просто, если стоило всегда использовать строки, если выбор был доступен.

Похожие вопросы