Porównanie szybkości dostępu do słownika z kluczem całkowitoliczbowym względem klucza strunowego

Question

Mam duży słownik, z którego muszę wielokrotnie wyszukiwać wartości. Moje klucze są liczbami całkowitymi, ale reprezentują etykiety, więc nie trzeba ich dodawać, odejmować itp. W końcu próbowałem ocenić czas dostępu między kluczem łańcucha a słownikiem kluczowym liczby całkowitej i tutaj jest wynik.

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)) 

która produkuje niewielkie różnice pomiędzy przebiegi odtworzone za każdym razem:

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

nie dowodzi, że przy użyciu słownika ze strunami jak klucze jest szybsze niż z dostępem do liczb całkowitych jak klucze?

Answer 1

Implementacja CPythona dict jest zoptymalizowana do wyszukiwania kluczy ciągów. Istnieją dwie różne funkcje, lookdict i lookdict_string (lookdict_unicode w Pythonie 3), które mogą być używane do wykonywania wyszukiwań. Python będzie używał wersji zoptymalizowanej dla ciągów, aż do wyszukiwania danych nie będących ciągami, po czym zostanie użyta funkcja bardziej ogólna. Możesz sprawdzić rzeczywistą implementację, pobierając źródło CPython i czytając przez dictobject.c.

W wyniku tej optymalizacji wyszukiwania są szybsze, gdy dict ma wszystkie klucze strunowe.

Answer 2

Obawiam się, że twoje czasy nie dowodzą zbyt wiele.

Twój test na ciąg w Dint jest najszybszy: na ogół test na wszystko, czego nie ma w słowniku, może być szybki, ale to tylko dlatego, że miałeś szczęście i po raz pierwszy trafiłeś w pustą komórkę, aby wyszukiwanie mogło zakończyć. Jeśli miałeś pecha i wybrałeś wartość, która uderzy w jedną lub więcej pełnych komórek, to może skończyć się wolniej niż przypadki, które faktycznie coś znajdują.

Testowanie dowolnego ciągu znaków w słowniku musi obliczyć kod skrótu dla ciągu znaków. To zajmuje czas proporcjonalny do długości napisu, ale Python ma fajną sztuczkę i oblicza ją tylko raz dla każdego ciągu. Ponieważ w teście sprawdzania czasu używasz tego samego ciągu znaków, czas potrzebny do obliczenia wartości skrótu jest tracony, ponieważ występuje tylko za pierwszym razem, a nie z innymi 99999999 razy. Jeśli używasz innego ciągu, za każdym razem otrzymasz zupełnie inny wynik.

Python ma zoptymalizowany kod dla słowników, w których klucze są ciągami. Ogólnie powinieneś zauważyć, że używanie kluczy strunowych, w których używasz tych samych klawiszy kilka razy, jest nieco szybsze, ale jeśli musisz konwertować liczby całkowite na ciąg przed wyszukiwaniem, stracisz tę przewagę.