🌱dict와 defaultdict + Counter (Python)

관련글 :

set과 dict 설명 (딕셔너리 참고)

https://waydd.tistory.com/34

 

 

1. defaultdict

• collections 모듈에 있는 클래스로 dict를 상속받음 (= 딕셔너리의 확장형 클래스)
• 존재하지 않는 키에 접근할 때 자동으로 기본값을 생성 ( 키 존재 여부를 검사 없이 초기화 가능 )
  → 키가 없으면 생성자에 지정한 기본값 생성 함수 를 호출
  ex) defaultdict(int) 에서 없는 키 접근 시, int() 호출
• 키 조회 / 삽입: O(1) 평균 (해시 기반)

from collections import defaultdict

d = defaultdict(default_factory)

※ default_factory는 기본값을 생성해줄 함수 또는 호출 가능한 객체(callable) ex)int, list, set, lambda 등
※ 왜 int, list 등이 함수로 취급하는지?
- 본래 클래스지만 int(), list(), set() 처럼 생성자 호출을 통해 객체를 반환하는 함수처럼 사용하기 떄문에

 

 

- 자주 사용하는 기본 팩토리(기본값 생성 함수)

• 반환된 기본값을 해당 키에 저장한 뒤 반환
• 키 존재 여부를 매번  if key in dict 로 검사하거나 setdefault() 를 호출할 필요가 없음
• 기본값 생성 함수 호출: O(1)  (단, 팩토리 함수가 복잡한 연산을 포함하면 그만큼 추가 비용 발생)

int	기본값: 0
list	기본값: 빈 리스트 []
set	기본값: 빈 집합 set()
lambda: 100	기본값: 100 (사용자 정의 가능)

 

 

2. dict와 defaultdict 비교

 

- dict에서 존재하지 않는 키 접근 시 오류

d = {}
print(d['x'])  # KeyError

 

- defaultdict에서는 존재하지 않는 키 접근 시, 기본값으로 자동 초기화되어 생성

from collections import defaultdict

d = defaultdict(int)
print(d['x'])  # 0 (기본값)

 

- 언제 defaultdict를 써야하는지

• 키가 없는 경우에 기본값을 넣어야 할 때
• 빈도수, 카운팅이 필요할 때
• 그룹핑 : defaultdict(list)  를 이용해 키별로 항목 묶기
• 집합 형태로 데이터 누적 : defaultdict(set)  으로 중복 없는 값 집계
• 그래프 인접 리스트 표현 : defaultdict(list) 
• 중첩 딕셔너리 쓸 때

# 중첩 딕셔너리
nested_dict = {
    "user1": {
        "name": "John Doe",
        "age": 20,
        "address": {
            "street": "123 Main St",
            "city": "Anytown"
        },
        "score" : 0
    }
}

# 일반 딕셔너리에서 중첩 구조 쓰기 (불편한 방식)
d = {}
d['user1'] = {}
d['user1']['score'] = 100 # 키가 없으면 미리 만들어야 함

# defaultdict로 중첩 딕셔너리 만들기
from collections import defaultdict

nested = defaultdict(lambda: defaultdict(int))
nested['user1']['score'] += 10 # 자동으로 0으로 생성

 

 

3. Counter

 

• 동일하게 collections 모듈에 있으며 dict 를 상속받은 서브 클래스
  → 키 = 각 요소, 값 = 등장 횟수 (해시 기반 동작)
• 내부적으로 defaultdict(int)  처럼 기본값이 0인 구조 기반, 빠른 빈도 계산 (카운팅) 에 특화된 도구
  → 유사하게 동작, But. 카운팅에 특화된 메서드를 제공 
  → 기본값 생성 방식은 int() (= 기본값 0), ※ 아래의 과정(내부 로직 개념) 을 따름
    ①   c['없는키']  호출
    ②  내부 딕셔너리에 '없는키'  가 있는지 확인
    ③  없으면(= 새로운 키 접근 시) int() 호출 : 0 반환  (일반 dict 는 KeyError)
    ④  그 값을 기본값으로 저장 후 반환 
  → 중복되는 요소가 있으면 자동으로 카운트를 증가
• 기본 생성자에 iterable을 넣으면, 내부에서 C로 구현된 counting 루프 를 돌아서 요소를 카운팅
  → 함수 호출, 인터프리터 오버헤드 최소화
  → 파이썬 바이트코드 루프보다 훨씬 빠름
• 음수까지 지원

from collections import Counter

c = Counter('aabc')
print(c)  # Counter({'a': 2, 'b': 1, 'c': 1})

 

 

- 예시와 동일한 기능을 defaultdict로 직접 구현 ( defaultdict + 파이썬 for 루프 )

• 매 반복마다 파이썬 레벨의 바이트코드가 실행
• 각 반복 제어, __getitem__ / __setitem__ 호출, +1 연산 등이 모두 파이썬 인터프리터 거침
  → 파이썬 for 루프 + 속성 접근(인덱싱) + 메서드 호출(객체 매서드 실행, int 객체에 대한  +1  산술연산)
  → C에서 한 번에 처리하는 Counter보다 오버헤드 누적 많음
• 커스터마이징된 누적 로직 (ex.특정 조건일 때만 증가)에 사용
• 메모리 사용은 사실상 동일

from collections import defaultdict
d = defaultdict(int)
for char in 'aabc':
    d[char] += 1
print(d) # defaultdict(<class 'int'>, {'a': 2, 'b': 1, 'c': 1})

※ 일반적으로 Counter 방식이 약 1.3~1.5배 빠름 (입력 크기 커질수록 차이 확대)

※ defaultdict, Counter 메모리 사용량 정리
- 둘다 dict 엔트리 를 만들기 때문에, 핵심 메모리 사용처는 키(문자열)와 값(정수), 그리고 dict 엔트리
  → 자료구조 클래스 차이는 미미
- dict 기반 자료구조 오버헤드 는 수백 바이트 수준에 불과 
  → dict는 아무 데이터가 없어도 이미 몇십 ~ 수백 차지
  → 타입 포인터(어떤 자료형인지), 참조 카운트(GC), 버킷 배열 포인터, 해시 테이블 크기와 상태 정보, 버전 관리 번호, 기타 내부 플래그 등 관리용 데이터
  → dict는 해시값과 포인터 배열 중심의 단순 + 효율적인 구조
  → 버킷 배열 미리 넉넉하게 (load factor 관리) 할당 +
    파이썬 객체 특성상 모든 키, 값이 객체 포인터 (실제 값X, 메모리 주소O) 이므로 추가 메모리 있음
  → 고급 자료구조에 비해선 낮은편 이지만, C 배열 처럼 아주 단순한 구조와 비교하면 여전히 높은 편
    (트리 기반 맵 구조는 포인터/노드 관리로 오버헤드가 훨씬 큼)
∴ Counter와 defaultdict의 메모리 사용량은 서로 다른 키(문자열)와 값(정수) 가 저장되느냐 가 메모리 사용량을 결정

 

 

- Counter 주요 메서드/기능

• 요소 카운팅(생성) : O(N)  (N 은 입력 크기, 해시 기반이라 평균적으로 빠름)
• 단일 키 조회 / 수정 : O(1) 평균
• 정렬 관련 메서드 (most_common) : O(K log K)  (K는 고유 요소 개수)

메서드	설명	예시
Counter(iterable) / Counter(mapping)	생성, 초기
.most_common([n=None])	가장 빈도 높은 n개 반환 (n 생략되면 모든 요소 정렬 후 반환)	c.most_common(1) → [('a', 2)]
.elements()	등장 횟수만큼 요소를 반복자로 반환  ( 요소를 원소로 복원 )	list(c.elements()) → ['a', 'a', 'b', 'c']
.update(iterable)	기존 카운터에 새로운 요소를 추가 집계	cnt.update("apple")
.subtract(iterable)	기존 카운터에서 특정 요소의 횟수를 차감	cnt.subtract("an")
산술 연산자	+  : 항목 개수 합침 -  : 겹치는 항목에서 뺀다 (0보다 작으면 무시) &  : 겹치는 키에 대해서 최소값 (교집합) |  : 겹치는 키에 대해 최대값 (합집합)	c1 | c2 → | (합집합) 가능

 

 

- 멀티셋 (multiset) 구현 가능

• 집합(set) : 원소를 한 번만 가짐  ex) {a,b,c}
• 멀티셋(multiset) : 같은 원소를 여러 번 가질 수 있는 집합, {a,a,b} 가능 (수학적 기호 : ⟦a,a,b⟧)
• 사실상  원소 → 개수  를 기록한 딕셔너리

from collections import Counter

arr = ["사과", "바나나", "사과", "포도"]
cnt = Counter(arr)
print(cnt)  # 출력 : Counter({'사과': 2, '바나나': 1, '포도': 1})

print(cnt["사과"])  # 2
print(cnt["포도"])  # 1