Блог

Допустим, у меня есть два словаря, и я знаю, что хочу измерить время, необходимое для проверки наличия ключа в словаре. Я попытался запустить этот фрагмент кода:

 from timeit import timeit

dct1 = {str(i): 1 for i in range(10**7)}
dct2 = {i: 1 for i in range(10**7)}

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))
 

Вот результаты, которые я получаю:

 2.529034548999334
2.212983401999736
 

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

 dct1[7] = 1
dct2["7"] = 1

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
print(timeit('7 in dct1', setup='from __main__ import dct1', number=10**8))
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))
print(timeit('"7" in dct2', setup='from __main__ import dct2', number=10**8))
 

Я чувствую что-то странное:

 3.443614432000686
2.6335261530002754
2.1873921409987815
2.272667104998618
 

Первое значение намного выше, чем у меня было раньше (3,44 против 2,52). Однако третье значение в основном такое же, как и раньше (2,18 против 2,21). Почему это происходит? Вы можете воспроизвести то же самое или это только я? Кроме того, я не могу понять большой разницы между первым и вторым значением: похоже, что доступ к строковому ключу сложнее, но то же самое, похоже, лишь слегка применимо ко второму словарю. Почему?

Обновить

Вам даже не нужно добавлять новый ключ. Все, что вам нужно сделать, чтобы увидеть увеличение сложности, — это просто проверить, существует ли ключ другого типа!! Это гораздо более странно, чем я думал. Посмотрите на пример здесь:

 from timeit import timeit

dct1 = {str(i): 1 for i in range(10**7)}
dct2 = {i: 1 for i in range(10**7)}

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
# 2.55
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))
# 2.26

7 in dct1
"7" in dct2

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
# 3.34
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))
# 2.35
 

Позвольте мне попытаться ответить на мой собственный вопрос. Реализация dict в CPython оптимизирована для поиска ключей str. Действительно, для выполнения поиска используются две разные функции:

• lookdict это универсальная функция поиска по словарю, которая используется со всеми типами ключей
• lookdict_unicode это специализированная функция поиска, используемая для словарей, состоящих только из ключей str

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

И похоже, что вы даже не можете изменить поведение конкретного экземпляра dict: как только он начнет использовать универсальную функцию, вы не сможете вернуться к использованию специализированной!