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

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

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 

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

2 Solutions collect form web for “Сравнение скорости доступа к словарю с целым ключом от строкового ключа”

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

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

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

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

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

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

Python - лучший язык программирования в мире.