전에 언패킹과 튜플의 고급 활용법, 가변/불변형의 연산자 동작 차이에 대해 공부했다.
오늘(3월 27일)은 파이썬 딕셔너리의 내부 구조인 해시테이블과 딕셔너리를 더 효율적으로 사용하는 방법에 대해 공부했다.
해시테이블의 원리
파이썬의 딕셔너리가 내부적으로 동작하는 원리인 해시테이블에 대해 공부해봤다.
사실 대학때 알고리즘 수업 때 배우면서 내부 구조를 배운 적이 있다.
해시테이블은 Key-Value 구조로 데이터를 저장하는 방식인데, 핵심은 탐색 속도가 매우 빠르다는 것이다. 일반 리스트에서 특정 값을 찾으려면 처음부터 끝까지 하나씩 뒤져야 하지만(O(n)) 해시테이블은 그럴 필요가 없다.
Key → 해싱 함수 → 해시 주소 → Value 참조Key 값을 해싱 함수에 넣으면 고유한 해시 주소가 나오고, 그 주소로 바로 Value에 접근(O(1))한다. 중간에 다른 데이터를 거칠 필요가 없으니 당연히 빠를 수밖에 없다.
실제로 파이썬의 __builtins__도 내부적으로 딕셔너리 구조로 되어 있다는 걸 확인할 수 있다.
print(__builtins__.__dict__)
# 여기서 __builtins__는 파이썬 내장 함수들해시 가능 규칙
해시테이블을 사용하려면 Key 값이 해시 가능 해야 한다. 그리고 해시 가능하려면 불변형 객체여야 한다.
좀만 생각해봐도 당연하다. 해시 주소는 Key 값(Key에 넣은 값)을 기반으로 계산되는데, Key가 나중에 바뀌어버리면 주소도 달라져서 Value를 찾을 수 없게 된다. 그래서 변하지 않는다는 보장이 있는 불변형만 Key로 사용할 수 있다.
t1 = (10, 20, (30, 40, 50)) # 내부까지 전부 불변형
t2 = (10, 20, [30, 40, 50]) # 내부에 가변형(리스트) 포함
print(hash(t1)) # 결과: 465510690262297113 (정상)
print(hash(t2)) # 결과: TypeError: unhashable type: 'list't1은 튜플 안에 튜플이 있어서 내부까지 완전히 불변형이다. 반면 t2는 겉은 튜플이지만 안에 리스트가 들어있다. 리스트는 언제든 값이 바뀔 수 있는 가변형이라서 해시값을 만들 수 없다.
겉이 불변형이어도 내부에 가변형이 하나라도 섞이면 해시 불가능하다. 완전히 불변이어야 한다.
딕셔너리 성능 최적화: setdefault
데이터를 특정 Key를 기준으로 그룹화할 때 보통 이렇게 작성한다.
source = (('k1', 'val1'),
('k1', 'val2'),
('k2', 'val3'),
('k2', 'val4'),
('k2', 'val5'))
new_dict1 = {}
# 일반적인 방법
for k, v in source:
if k in new_dict1:
new_dict1[k].append(v)
else:
new_dict1[k] = [v]
print(new_dict1)
# 결과: {'k1': ['val1', 'val2'], 'k2': ['val3', 'val4', 'val5']}동작은 하지만 if k in dict로 키 존재 여부를 매번 확인하는 게 성능 저하를 유발한다. 이걸 setdefault로 한 줄로 줄일 수 있다.
new_dict2 = {}
# setdefault 사용
for k, v in source:
new_dict2.setdefault(k, []).append(v)
print(new_dict2)
# 결과: {'k1': ['val1', 'val2'], 'k2': ['val3', 'val4', 'val5']}
setdefault(k, [])는 Keyk가 없으면 빈 리스트를 만들어서 초기화하고, 이미 있으면 기존 리스트를 그대로 반환한다. 그 결과에 바로.append(v)를 연결해서 붙이는 구조다.
코드도 훨씬 간결해지고 속도도 빠르다. 앞으로 데이터를 그룹화할 일이 생기면 이 방식을 쓰는 게 좋다.
그렇지만 아직은 손에 익지 않아서 막상 이런 상황에서 기억이 안날 수 있을 것 같다. 최대한 이러한 코드를 봤을 떄 당황하지 않게 까지만 눈에 익히자.
딕셔너리 컴프리헨션 주의점
딕셔너리 컴프리헨션을 사용할 때 한 가지 조심해야 할 게 있다.
new_dict3 = {k: v for k, v in source}
print(new_dict3)
# 결과: {'k1': 'val2', 'k2': 'val5'}source에는 k1이 두 번, k2가 세 번 등장한다. 딕셔너리는 Key 중복을 허용하지 않기 때문에 에러 없이 가장 마지막 Value로 조용히 덮어써버린다. 에러가 발생하지 않아서 이걸 모르면 데이터 유실이 발생했는데도 알아채기가 어렵다.
setdefault로 그룹화하면{'k1': ['val1', 'val2'], 'k2': ['val3', 'val4', 'val5']}로 모든 데이터가 보존되지만, 컴프리헨션으로 만들면{'k1': 'val2', 'k2': 'val5'}로 앞의 데이터가 전부 날아간다. 목적에 맞게 구분해서 사용해야 한다.
오늘 공부하면서 딕셔너리가 그냥 Key-Value를 담는 통이 아니라, 내부적으로 해시테이블이라는 구조로 동작한다는 걸 다시 한번 공부하면서 제대로 이해했다. setdefault는 최대한 보고 뭔지 상기할 수 있을 정도로만 다시보자.
