[Python 2/3] dict() 안의 key 찾기...에서 시작한 dict key의 생김새 톺아보기

===== 업데이트:  여러 분들의 도움과 피드백으로 잘못된 부분을 수정했습니다. 감사드립니다. (2017-03-16 14:00) =====

인터넷을 하다 모 블로그 에서 dict() 안의 key를 찾는 것에 대한 속도 비교 글을 보았다.

내가 알고 있던 바와 달라 직접 확인해보고 간만에 글을 하나 써보려 한다.

우선, 작성자가 쓴 글과 동일한 조건에서 테스트를 해보자. 해당 글은 2015년 글이라서 일단 파이썬2라고 가정했다.

그때와 지금의 컴퓨팅 파워를 생각해(?) iteration을 10만번으로 증가시켰다.

오잉? 작성자 말이 맞잖아??? 엄청나게 차이나잖아???

아..앙돼 이건 인정할 수 없어 다시해볼거야 ㅂㄷㅂㄷ

이게 어떻게 된 일이지...

사실 나는 코딩을 이렇게 안해서 몰랐었다

테스트하면서 이정도의 성능 차이가 있는지 처음 확인했는데, 비밀은 미묘하게 다른 두 test_dict_if() 함수의 내용물에 있다.

처음 테스트한 느릿한 녀석은 if i in d.keys(): 를 통해 키를 확인하고 있고, 

두번째의 try보다 한참 빠른 녀석은 if i in d: 를 이용해 키를 확인하고 있다.

하지만!

파이썬 2는 이제 곧 가실 몸이잖아? (이미 가셨지 인공호흡기만 달아놨을뿐...)

그럼 파이썬 3에서는 뭔가 좀 다르지 않을까?

오오 갓갓 파이썬3!!

무시무시하게 빠르다. 심지어 keys() 를 쓴 버전도 별로 속도차이가 없을 정도로 빠르다.

왜지...

또 안해볼 수 없는게 keys() 없는 버전...

약간의 속도 상승을 더 기대할 수 있지만 이미 10만번 돌 때 0.04초인 시점에서 별로 속도경쟁은 의미가 없어졌다.

그런데 이걸 테스트하다가 문득 이런 생각이 들었다. 

"if k in d: 만 가지고 키를 확인할 수 있으면 그럼 d를 그냥 쓰면 키를 다룰 수 있지 않을까?"

해보면 되지뭐

올ㅋ

근데 보다보니 list(d) 같은건 의미를 파악하기 좀 어렵긴 하다. 아는 사람이 아니라면 dict를 list로 감싸면 뭐가 되는지 모를테고, 뭔가 이상해보이잖아? list(dict()) 라니... 불가능해 보인달까 말이 안 돼 보인달까...

자 그럼 이제 본격적으로 위에서 나온 이상현상(?)의 원인을 파헤쳐보자.

---

1. dict().keys()

이게 참 별것 아닌 것 같은데, 여기서부터 내용이 꽤 많다. 일단 파이썬 2와 파이썬 3에서 같은 함수를 썼음에도 성능에 어마어마한 차이가 있었던 이유를 먼저 보고자 한다.

파이썬 2 공식문서에서는 이렇게 말하고 있다.

Return a copy of the dictionary’s list of keys. See the note for dict.items().

키 리스트를 복사해서 던져준단다. 그래서 d.keys()의 타입을 찍어보면 list라고 한다.

그럼 파이썬 3에서는 어떨까? 3.5 문서에서는 이렇게 말하고 있다.

Return a new view of the dictionary’s keys. See the documentation of view objects.

뷰를 준다고 하네? 뷰는 뭐지 처음본다. 여튼 그래서 타입을 찍어보면 dict_keys 라고 한다..

2. dictionary veiw objects

위에서 읽어보세요! 하는 링크를 들어가면 이런 글을 볼 수 있다. "Dictionary view objects"

파이썬 3에서는 keys(), values(), items() 를 부르면 뷰 객체를 반환한다고 한다. 이는 무엇인고 하니 일종의 "사전 정보 바구니" 라고 하면 되려나... 해당 dict() 의 정보를 담고 있는 객체이다. 얘는 참 좋은 게 원본의 변경을 바로 반영하고, 안에 담긴 정보를 순회할 수도 있으며, 멤버십 테스트도 할 수 있다고 한다.

무슨 말이냐면, dict() 안의 값을 복사해 별도의 객체를 만드는 게 아니라 말 그대로 "뷰" 여서 원본이 변경되면 같이 변경된다는 말이다. 파이썬 2에서의 keys()는 키를 "복사해서" 준다고 했기 때문에 일단 키를 얻고나면 이는 원본에 관계없이 계속 그대로 유지된다. 그래서 원본 사전을 변경하면 다시 받아서 써야하는데, 이는 그럴 필요가 없다는 것.

다음으로는 순회와 멤버십 테스트인데, 이는 우리가 사전을 쓰며 많이 하는 것들이다.

for k in d.keys():  라거나 if k in d.keys():  라거나...

그 중에서도 특별하게 keys() 를 통해 얻은 뷰는 dict key가 사전 전체에서 유일함이 보장되기 때문에 set-like 한 특징을 가진다고 한다.

이게 뭐냐면 사전의 키는 기본적으로 hashable하고, 그것만 가져온 keys() 안에 있는 것들 또한 중복 없이 hashable한 값들의 모임이기 때문에 set 과 동일한 작업을 할 수 있다는 말이다. 공식 문서에 있는 설명과 예제 코드를 보면 도움이 될 것 같다.

여기서 위에서 본 이상현상(?) 하나가 해결된다. 파이썬 2의 keys()는 리스트이고, 파이썬 3의 keys()는 set-like한 view 객체이므로, k in d 작업을 하는데 속도가 상당히 차이가 난다. 하나는 O(n), 하나는 O(1) 이니까...

파이썬 2 문서를 보면 파이썬 2에도 이미 이런 게 있다는 것을 확이인할 수 있다. 여기에 viewkeys() 라거나 하는 것들이 있다. 그리고 바로 아래에 보면 파이썬 2에도 이미 뷰 객체가 선언되어 있고 역시나 set-like 하다는 설명이 있다. 

뭔가 keys() 와 viewkeys()는 range()와 xrange()의 관계같군...

3. if k in d:

그럼 이제 남은 문제는 하나뿐. k in d.keys()가 set-like 특성을 가지는 view라는 것까지는 알겠는데, if k in d: 는 어째서 작동하냐는거.

해답은 __contains__() 함수에 있다. 여기를 보면 그런 내용이 있는데, 멤버십 테스트라는 내용과 함께 설명이 나온다. 

기본적으로 list, tuple, set, dict 같은  container 타입의 x in y 는 다음과 같다고 한다: any(x is e or x == e for e in y)

참 거시기해보이는 구문이지만, 같은 객체이거나 값이 같은게 1개라도 있는가? 를 묻는거라고 하면 된다.

파이썬에서의 in / not in 연산자는 멤버십 테스트를 진행한다고 한다. 멤버십 테스트는 다음과 같은 순서로 진행된다고 한다.

1.  __contains__() 함수가 정의되어 있는 경우 y.__contains__(x) 가 참일 경우에만 True이다.
2.  __contains__() 함수가 없지만 __iter__() 함수가 정의되어 있는 경우 y를 순회하며 그 안의 값 z 중에 x==z 를 만족하는 게 있는지 본다.
3. 둘 다 없으면 마지막으로 __getitem__() 을 시도한다. 이 함수가 정의되어 있는 경우 x==y[i] 의 음수가 아닌 index i가 존재하면 참이 된다.

그럼 dict는 어떻게 돼있을까? C 구현체를 까보았다. 여기를 보면 __contains__() 가 친절하게 구현되어 있다.

내용을 조금 보자면 검색하려는 키로 해시를 만들고, 해당 객체의 키 안에서 이 해시를 가지고 값을 검색한다. 에러가 나거나 값이 비어있으면  False, 있으면 True를 반환한다.

이를 통해 파이썬 2, 3 모두에서 if k in d: 를 사용하면 매우 빠른 이유를 알 수 있다. 여기서는 파이썬 2/3 모두 hash를 이용해 값을 찾고 있기 때문에 빨랐던 것이다. 참 별 것도 아닌 것 같은데 내용이 많다. 언어 설계의 심오함이란...

4. (WIP) list(dict())

list(dict())를 하면 잘 작동한다. 그리고 d의 키들을 리스트로 만들어 반환한다. 어떤 원리로 저게 굴러가는지 보고싶어서 파이썬 코드를 까보고 있는데 내가 바보인건지 하루종일 찾다가 포기하고 나중에 추가하기로 했다...

결론. 파이썬 3 쓰면 뭘 해도 별 상관 없습니다. 파이썬 3 쓰세요 파이썬 3

+

위 스샷을 보면 파이썬 2, 3의 for k in d: 라거나 list(d) 결과가 다르다. 왤까? 해싱하는 방식이 달라졌나...?

P.S.

멍때리고 있다가 갑자기 defaultdict()가 생각나서 해봤다.

상황이 잘 맞아준다면 defaultdict() 를 쓰는게 보기에는 더 깔끔해보일 수 있겠다.

근데 int를 기본 자료형으로 넣으면 0을 넣어주는건가...

ㅇㅇ 그런가봄...