Сравнение скорости доступа к словарю с целочисленным ключом против строкового ключа

Question

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

from timeit import Timer

Dint = dict()
Dstr = dict()

for i in range(10000):
    Dint[i] = i
    Dstr[str(i)] = i


print 'string key in Dint',
print(Timer("'7498' in Dint", "from __main__ import Dint").timeit(100000000))
print 'int key in Dint',
print(Timer("7498 in Dint", "from __main__ import Dint").timeit(100000000))
print 'string key in Dstr',
print(Timer("'7498' in Dstr", "from __main__ import Dstr").timeit(100000000))
print 'int key in Dstr',
print(Timer("7498 in Dstr", "from __main__ import Dstr").timeit(100000000))

, который производит небольшие вариации между сериями, воспроизводимыми каждый раз:

string key in Dint 4.5552944017
int key in Dint 7.14334390267
string key in Dstr 6.69923791116
int key in Dstr 5.03503126455

Доказывает ли это, что использование словаря со строками в качестве ключей быстрее для доступа, чем с целыми числами в качестве ключей?

Answer 1

Реализация dict в CPython фактически оптимизирована для поиска по строковому ключу.Есть две разные функции, lookdict и lookdict_string (lookdict_unicode в Python 3), которые можно использовать для поиска.Python будет использовать оптимизированную для строк версию до поиска нестроковых данных, после чего используется более общая функция.Вы можете посмотреть на фактическую реализацию, загрузив исходный код CPython и прочитав dictobject.c.

В результате этой оптимизации поиск быстрее, когда dict имеет все строковые ключи.

Answer 2

Боюсь, что твои времена не очень-то доказывают.

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

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

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