[Time Complexity] Python - Find Value in List vs Set vs Dict

[시간 복잡도] 파이썬 - List vs Set vs Dict 에서 Value 찾기

code n = 100000 n = 1000000 n = 1000000 Time Complexity
x in list 0.000494 0.019270
 0.235368
 O(n)
list.index(x) 0.000537
 0.020288
 0.246275
 O(n)
for a in list:  if(a==x) 0.010289
 0.107806
 1.036934
 O(n)
x in set 0.000002
 0.000002
 0.000006
 O(1)
list to set 0.115826
 0.066516
 0.716471
  
x in dict 0.000005
 0.000005
 0.000004 O(1)
list to dict 0.147385
0.223651
2.232983  

결론

1. Set, Dict 에서 value를 찾을 경우에 시간 복잡도 O(1)로 가장 빠름

2. 다만 List to Set/Dict conversation이 필요한 경우에 일정 값 이하의 n에서는 List를 사용

'Programming > Python' 카테고리의 다른 글

[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)  (2) 2019.04.17
[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

[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

[Time Complexity] Python - Numpy vs List of zeros declaration

[시간 복잡도] 파이썬 - Numpy vs List의 제로 배열 선언 비교

code n = 10000000 n = 100000000 n = 1000000000 Time Complexity
[0] * n 0.0831630230  0.8130910397 8.0924339294 O(n)
[0 for i in xrange(n)] 0.3735442162  3.7914631367  37.1647899151  O(n)
x = [] 
for i in xrange(n):
    x.append(0)		 0.9481530190  9.4668169022  94.6755440235  O(n)
numpy.zeros((n,)) 0.0000300407 0.0000290871  0.0000340939  O(1)
numpy.full((n,),0) 0.0420970917 0.4114339352 4.0288629532 O(n)
numpy to list 0.5932991505 5.9227490425 59.9193470478 O(n)

결론

1. 제로 리스트 선언은 numpy.zeros가 가장 빠름

2. 다만 numpy to list 시간 복잡도가 O(n)이므로 리스트로 변환이 필요시에 [0] * n 가 가장 빠름

'Programming > Python' 카테고리의 다른 글

[Time Complexity] Python - Find Value in List vs Set vs Dict  (1) 2019.04.23
[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)  (2) 2019.04.17
자주 쓰이는 정규식(Regular Expression)  (0) 2019.01.15
python 버전 업그레이드에 의한 yum 재설치  (2) 2018.10.29
pip 설치 및 재설치  (0) 2018.10.22

+ Recent posts

티스토리툴바