[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)
[시간 복잡도] 파이썬 - Deque vs List 퍼포먼스 비교 (append, appendleft, pop, popleft)
| code | n = 10000 | n = 100000 | n = 1000000 | Time Complexity |
| list.append() | 0.0010249615 | 0.0093748569 | 0.0974259377 | O(1) |
| deque.append() | 0.0012080669 | 0.0113868713 | 0.1131999493 | O(1) |
| list.insert(0,0) | 0.0436980724 | 4.2723989487 | 430.9322969913 | O(n) |
| deque.appendleft() | 0.0010690689 | 0.0137970448 | 0.1067051888 | O(1) |
| list.pop() | 0.0013749599 | 0.0134758949 | 0.1310129166 | O(1) |
| deque.pop() | 0.0009977818 | 0.0100331306 | 0.1004290581 | O(1) |
| list.pop(0) | 0.0262870789 | 3.5589528084 | 372.6231980324 | O(n) |
| deque.popleft() | 0.0009810925 | 0.0101020336 | 0.0985748768 | O(1) |
결론
1. append와 pop의 경우에는 List와 Deque 둘 다 Time Complexity가 O(n)으로 별차이가 없음
2. appendleft와 popleft의 경우에 Deque가 훨씬 빠름
'Programming > Python' 카테고리의 다른 글
| [Time Complexity] Python - Find Value in List vs Set vs Dict (1) | 2019.04.23 |
|---|---|
| [Time Complexity] Python - Numpy vs List of zeros declaration (0) | 2019.04.16 |
| 자주 쓰이는 정규식(Regular Expression) (0) | 2019.01.15 |
| python 버전 업그레이드에 의한 yum 재설치 (2) | 2018.10.29 |
| pip 설치 및 재설치 (0) | 2018.10.22 |