효과적인 사전 검색?

Question

큰 사전을 통해 파이썬에서 검색의 효율성에 대한 빠른 질문이있었습니다. 쉼표로 구분 된 큰 파일을 읽고 각 줄에서 키와 값을 가져옵니다. 내 키가 이미 사전에있는 경우 사전에 나열된 값에 ​​값을 추가합니다. 키가 사전에없는 경우 값을 추가하기 만하면됩니다. 이전에 나는 이것을 사용했다 :

는

if key in data_dict.keys(): 
    add values 
else: 
    data_dict[key] = value 

이 꽤 빨리 시작하지만 사전이 성장함에 따라 내가 전혀 사용할 수없는 지점에, 느린 속도가 느린됩니다. 나는이에 사전에 키를 검색하는 방식 변경 :

try: 
    # This will fail if key not present 
    data_dict[keyStr] = input_data[keyStr] + load_val 
except: 
    data_dict[keyStr] = load_val 

이 무한히 빠른, 그리고/쓰기 삼초의 코드 350,000 라인 읽을 수 있습니다.

내 질문에 전화보다 훨씬 오래 sooo 걸릴 내 질문이 있었습니까? 사전에서 키를 검색 할 때 파이썬에서 try 문을 사용하지 않는 이유는 무엇입니까?

Answer 1

모든 테스트에서 .keys()이라는 새로운 키 목록을 생성하는 것이 문제입니다. 키 목록이 길어지면 필요한 시간이 길어집니다. 또한 as noted by dckrooney 키의 검색은 사전의 해시 테이블 구조를 이용하는 대신 선형이됩니다. 당신을 도와해야 시도 기능에 가깝다 뭔가가있다

if key in data_dict: 

Answer 2

이 질문에 대답하지 않지만 오히려 그것을 피합니다. collections.defaultdict을 사용해보세요. if/else 또는 try/except은 필요하지 않습니다.

from collections import defaultdict 

data_dict = defaultdict(list) 
for keyStr, load_val in data: 
    data_dict[keyStr].append(load_val) 

Answer 3

data_dict.keys()는 (적어도 파이썬 2.X에서) 사전에 키를 포함하는 목록을 반환하기 때문입니다. 키가 목록에 있는지 찾기 위해 선형 검색이 필요합니다.

반면에 dict의 요소에 직접 액세스하면 사전의 멋진 속성을 활용하므로 액세스가 거의 즉시 이루어집니다.

Answer 4

: dict.get(key, default)

data_dict[keyStr] = data_dict.get(keyStr, '') + load_val 

Answer 5

data_dict.keys()가 사전에 키의 분류되지 않은 목록을 반환과

는 교체합니다. 따라서 주어진 키가 사전에 있는지 확인할 때마다 키 목록 (O (n) 연산)을 선형 검색합니다. 목록이 길수록 지정된 키를 검색하는 데 더 오래 걸립니다.

대조적으로 data_dict[keyStr]과 비교하십시오. 이 작업은 O (1) 연산 인 해시 조회를 수행합니다. 사전에있는 키의 수에 (직접적으로) 의존하지 않습니다. 더 많은 키를 추가하는 경우에도 사전에 지정된 키가 있는지 확인하는 시간이 일정하게 유지됩니다.

Answer 6

또한 단순히

if key in data_dict: 

대신 바와 같이

if key in data_dict.keys(): 

사용하여, 제는 직접 해시 룩업합니다 - 직접 계산되는 오프셋 다음 체크 의도 한 - 그것은 대충 O (1) 인 반면 키의 확인은 O (n) 인 선형 검색입니다.

In [258]: data_dict = dict([(x, x) for x in range(100000)]) 

In [259]: %timeit 999999 in data_dict.keys() 
100 loops, best of 3: 3.47 ms per loop 

In [260]: %timeit 999999 in data_dict 
10000000 loops, best of 3: 49.3 ns per loop 

Answer 7

위로 옛날 우리가 setdefault 사용 :

data_dict.setdefault(keyStr, []).append(load_val) 

Answer 8

으로 여러 다른 사람이 언급 한이 문제는 key in data_dict.keys()가 정렬되지 않은 list가 keys() 메서드에서 반환 사용하는 사실에있다 (Python 2.x에서) linear timeO (n) 검색하려면 thr 즉, 실행 시간이 사전 크기에 따라 선형 적으로 증가하고 키 목록을 생성 할 때 크기가 올라 갈수록 길어지고 오래 걸립니다. 한편

는 key in data_dict은 내부적으로는 hash table 룩업을 수행하기 때문에 O (1)가 평균적 사전의 크기와 관계없이 검색을 수행하기 위해 일정한 시간을 필요로한다. 또한이 해시 테이블은 사전의 내부 표현 부분이므로 이미 있으므로 해시 테이블을 사용하기 전에 생성 할 필요가 없습니다.

in 연산자는 소스가 아닌 두 피연산자 유형 만 알고 있으므로 자동으로 키와 목록 만있는 첫 번째 경우를 최적화 할 수 없기 때문에 파이썬에서는이 작업을 자동으로 수행하지 않습니다.

그러나이 경우 검색 속도 문제는 내장형 collections 모듈에있는 defaultdict이라는 특수 버전의 특수 버전으로 데이터를 저장하여 피할 수 있습니다. 여기에 하나를 사용하는 경우 코드가 보일 수 있습니다 방법은 다음과 같습니다

from collections import defaultdict 

input_data = defaultdict(float) # (guessing factory type) 
... 
data_dict[keyStr] = input_data[keyStr] + load_val 

을 input_data[keyStr] 하나에 대한 기존 항목이 디폴트 값 (이 예에서는 float에 대한 0.0)을 자동으로 생성되지 않습니다있을 때. 알 수 있듯이 코드는 더 짧고 매우 빠르며 모든 것은 if 테스트 또는 예외 처리가 필요하지 않습니다.