[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. appendleftpopleft의 경우에 Deque가 훨씬 빠름

>>> a = ['한글','영어','수학']
>>> print a
['\xc7\xd1\xb1\xdb', '\xbf\xb5\xbe\xee', '\xbc\xf6\xc7\xd0']
>>> print repr(a).decode('string-escape')
['한글', '영어', '수학']


- Reference

http://egloos.zum.com/ZHANITEST/v/1279856

+ Recent posts