클라우드로 크고 싶은 블로그 입니다

얼마 전 회사에서 코드관련 글 중, 누군가,

 

if a in dict_type.keys():

    블라블라블라~~~

 

는 in 연산 시 선형적으로 탐색하므로 시간 복잡도가 O(n) 된다는 글을 보았다.

파이썬 위키의 시간 복잡도 관련 글 ( https://wiki.python.org/moin/TimeComplexity )에서도 따로 Keys() 메서드에 관한 내용은 없었다.

 

정말 일까? 코드로 테스트해 보았다.\

 

import timeit

test_dict = {x:x*2 for x in range(100000)}
test_list = list(range(100000))

print(type(test_dict.keys()))

print(timeit.timeit(lambda: 999999 in test_dict.keys(), number=10000))
print(timeit.timeit(lambda: 999999 in test_dict, number=10000))
print(timeit.timeit(lambda: 999999 in test_list, number=10000))

 

<class 'dict_keys'>
0.001331400000026406
0.0006685999999263004
10.455946499999982

 

결과 적으로 말하면, dict_type.keys() 의 반환값은 dict_keys 클래스 이고,

이 클래스는 list 클래스와 다르다는 결론이다.

 

그래도 key만 뽑기 위해 뭔가 다른 동작을 하는지, 바로 비교하는 2번째 연산에 비하면,

오래 걸린다.

 

결론 : 딕셔너리의 키 유무를 확인하기 위해 in 연산을 사용할 때는 2번째 처럼 바로 사용하자.