파이썬 데이터 구조: Big O 이론을 넘어 최적화된 성능 탐구
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
데이터 분석
대상자
- *중급 Python 개발자 및 성능 최적화에 관심 있는 프로그래머**
- 난이도: 중간 수준 (Big O 개념 이해 및 데이터 구조 특성 분석 필요)*
핵심 요약
list와deque의 삽입/삭제 성능 차이:list의pop(0)은 O(N) (선형 시간),deque의popleft()는 O(1) (상수 시간).set과dict의 검색 효율성:set의in연산은 O(1),list의in연산은 O(N).tuple의 불변성 활용: 불변 데이터 처리 시 메모리 효율성과 해시 가능성에 유리.
섹션별 세부 요약
1. Big O 표기법 리마인더
- O(1) - 상수 시간: 입력 크기와 관계없이 동일한 시간 소요 (예:
dict의 키 검색). - O(N) - 선형 시간: 입력 크기 증가에 비례하여 시간 증가 (예:
list의in연산). - O(N²) - 제곱 시간: 대규모 입력 시 성능 저하 (예: 중첩 루프).
2. 데이터 구조 성능 비교 표
list
- 삽입/삭제: 끝부분 O(1), 중간/시작 O(N).
- append()는 O(1) (할당 확장 시 평균 성능).
set
- 중복 제거 및 in 연산 O(1).
- 요소는 해시 가능 (불변 타입만 허용).
dict
- 키-값 검색: O(1).
- 키는 해시 가능 (불변 타입만 허용).
deque
- 양 끝 삽입/삭제: O(1).
- 중간 접근: O(N) (연결 리스트 구조).
3. `list` vs `deque` 성능 테스트 예시
list사용 시:pop(0)은 O(N) (모든 요소 이동).deque사용 시:popleft()는 O(1) (양 끝 효율성).- 코드 예시:
```python
from collections import deque
my_deque = deque(range(100000))
start_time = time.time()
for _ in range(100000):
my_deque.popleft() # O(1)
end_time = time.time()
print(f"Deque time: {end_time - start_time:.6f} seconds")
```
4. `set`의 멤버십 테스트 효율성
setvslist:
- 123456 in large_set (O(1)) vs 123456 in large_list (O(N)).
- 대규모 데이터에서 100배 이상의 속도 차이 발생.
- 코드 예시:
```python
large_set = set(range(1000000))
start_time = time.time()
- in large_set # O(1)
end_time = time.time()
print(f"Set membership test time: {end_time - start_time:.9f} seconds")
```
5. `tuple`의 불변성과 성능
- 불변성:
tuple은 해시 가능 (딕셔너리 키, 세트 요소에 사용 가능). - 메모리 효율성: 고정 크기로 인해 리스트보다 메모리 사용량 적음.
- 코드 예시:
```python
import dis
dis.dis(compile("(1, 2, 3)", "", "eval")) # tuple 생성 시 보다 적은 바이트코드 연산
```
6. `dict`의 해시 테이블 구조
- 키-값 검색:
my_dict["key"]는 O(1) (해시 테이블 기반). - 동적 확장: 키/값 추가, 수정, 삭제 가능 (변경 가능한 구조).
- 주의 사항: Python 3.7 이전 버전은 삽입 순서 보장 X (현재는 보장됨).
7. `deque`의 연결 리스트 구조
- 양 끝 연산 효율성:
append(),appendleft(),pop(),popleft()모두 O(1). - 중간 접근 비용:
deque[i]는 O(N) (연결 리스트 특성). - 메모리 효율성: 대규모 데이터 시 리스트보다 메모리 사용량 적음.
결론
- 성능 최적화를 위한 핵심 팁:
- 대규모 데이터 처리 시: set을 list 대신 사용 (멤버십 검색 O(1)).
- 큐 구현 시: deque 사용 (양 끝 삽입/삭제 O(1)).
- 불변 데이터 처리 시: tuple 사용 (메모리 효율성 및 해시 가능성).
- 문서의 주요 구현 방법: 데이터 구조의 내부 구현 방식을 이해하고, 성능 요구사항에 맞는 구조 선택.