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

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

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

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

Ответ 1

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

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

Ответ 2

Я боюсь, что ваши времена на самом деле не очень много.

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

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

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