사전은 문자열 키에 대한 정수 키와의 속도 비교를 수행합니다.

Question

많은 시간 값을 찾아야하는 큰 사전이 있습니다. 내 키는 정수이지만 레이블을 나타내므로 더하기, 빼기 등을 할 필요가 없습니다. 문자열 키와 정수 키 사전 사이의 액세스 시간을 평가하려고했지만 결과는 여기에 있습니다.

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

그것이 문자열 사전을 사용하는 키는 키와 정수보다 액세스 빠른으로 증명합니까 : 실행 때마다 재현 사이에 약간의 변형을 생산

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

?

Answer 1

CPython의 dict 구현은 실제로 문자열 키 조회에 최적화되어 있습니다. 조회를 수행하는 데 사용할 수있는 lookdict과 lookdict_string (Python 3에는 lookdict_unicode)의 두 가지 기능이 있습니다. 파이썬은 문자열이 아닌 데이터를 검색 할 때까지 문자열 최적화 버전을 사용합니다. 그 다음에 더 일반적인 함수가 사용됩니다. CPython의 소스를 다운로드하고 dictobject.c을 통해 읽음으로써 실제 구현을 볼 수 있습니다.

dict에 모든 문자열 키가있는 경우이 최적화 조회의 결과가 더 빠릅니다.

Answer 2

시간이 정말 많이 증명되지는 않을까 걱정됩니다.

Dint의 문자열 테스트는 가장 빠릅니다. 일반적으로 사전에없는 테스트는 빠르지 만 운이 좋았고 처음으로 빈 셀에 도달하여 조회가 수행 될 수 있었기 때문입니다 끝내다. 당신이 불길한 사람이라면 하나 이상의 셀 전체에 치명타를 치는 값을 선택하면 실제로 뭔가를 발견하는 경우보다 느리게 끝날 수 있습니다.

사전에서 임의의 문자열을 테스트하면 문자열의 해시 코드를 계산해야합니다. 그것은 문자열의 길이에 비례하여 시간이 걸리지 만, 파이썬은 깔끔한 트릭을 가지고 있으며 각 문자열에 대해 한번만 계산합니다. 타이밍 테스트에서 동일한 문자열을 반복해서 사용하기 때문에 해시를 계산하는 데 걸리는 시간은 처음으로 발생하기 때문에 손실됩니다. 다른 99999999 번은 발생하지 않습니다. 매번 다른 문자열을 사용한다면 매우 다른 결과를 얻을 수 있습니다.

파이썬은 키가 문자열 인 사전에 대한 코드를 최적화했습니다. 전체적으로 동일한 키를 여러 번 사용하는 경우 문자열 키를 사용하는 것이 약간 빠르지 만 조회 전에 정수로 문자열을 변환해야하는 경우 이점을 잃을 수 있습니다.