Python list, Dict, OrderedDict

Dictonary와 OrderedDict에 대해 정리해보자.

갑자기 딕셔너리?? 파이썬 처음 배우나봐!하고 귀엽게 봐주면 좋겠지만.. 이걸 정리하게 된 이유는

...
아니!! 흠.. 심지어 딕셔너리 관련해서 정리도 하긴 했었다..(코드 위주로)

그럴수도 있다고 생각하고... 딕셔너리가 뭔가요? 라고 누군가 질문한다면, key, value값으로 이루어져 있고, 시간복잡도는 O(1)! 밖에 기억이 안나서 있어보이는 대답을 한번 하기 위해 이참에 정리해보기로 했다!

정리하려 해보니 OrderedDict라는 것도 있어서 이참에 같이, list의 주요 연산 시간복잡도와 함께 정리해보자

연산	시간 복잡도	설명
len(a)	O(1)	전체 요소의 개수를 리턴한다.
a[i]	O(1)	인덱스 i의 요소를 가져온다.
a[i:j]	O(k)	i부터 j까지 슬라이스의 길이만큼 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다.
elem in a	O(n)	elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다.
a.count(elem)	O(n)	elem 요소의 개수를 리턴한다.
a.index(elem)	O(n)	elem 요소의 인덱스를 리턴한다.
a.append(elem)	O(1)	리스트 마지막에 elem 요소를 추가한다.
a.pop()	O(1)	리스트 마지막 요소를 추출한다. 스택 연산
a.pop(0)	O(n)	리스트 첫번째 요소를 추출한다. 큐 연산, 전체 복사가 필요하므로 O(n)이다.
del a[i]	O(n)	i에 따라 다르다. 최악의 경우 O(n)이다.
a.sort()	O(nlogn)	정렬, Timsort를 사용하며, 최선의 경우 O(n)에도 실행
min(a), max(a)	O(n)	최소, 최대를 계산하기 위해서는 전체를 선형탐색한다.
a.reverse()	O(n)	뒤집기, 리스트는 입력 순서가 유지되기 때문에, 뒤집으면 입력 순서가 반대로 된다.

딕셔너리

• 파이썬 3.7+ 에서는 입력 순서가 유지된다.
• 내부적으로 해시 테이블로 구현되어 있다.
  | 연산 | 시간 복잡도 | 설명 |
  |:---|:---|:---|
  | len(a) | O(1) | 요소의 개수를 리턴한다. |
  | a[key] | O(1) | 키를 조회하여 값을 리턴한다. |
  | a[key] = value | O(1) | 키/값을 삽입한다. |
  | key in a | O(1) | 딕셔너리에 키가 존재하는지 확인한다. |

OrderedDict
입력된 순서를 보장하는 특수한 딕셔너리 자료형 (3.6 이전에도 존재)
3.7 부터 기존 딕셔너리에서 입력 순서가 유지된다면, OrderedDict는 필요없는 것일까?
-> x

동등성을 확인할 때 OrderedDict는 순서까지 동등한지 검증한다.

# 기본 딕셔너리
>>> dict_a
{'a': 'apple', 'b': 'banana', 'p': 'pineapple'}
>>> dict_b
{'b': 'banana', 'a': 'apple', 'p': 'pineapple'}

>>> dict_a == dict_b
True

# OrderedDict
>>> ordered_a
OrderedDict([('a', 'apple'), ('b', 'banana'), ('p', 'pineapple')])
>>> ordered_b
OrderedDict([('b', 'banana'), ('a', 'apple'), ('p', 'pineapple')])

>>> ordered_a == ordered_b
False

데이터의 입력 순서가 아주 중요한 상황이나 하위 호환성을 고려해야 하는 상황에서는 OrderedDict를 사용해 순서를 보장하는 걸 고려해보자.

번외로 딕셔너리 요소 순회할 때 Index와 함께 순회하는 방법 remind

enumerate() 이용

for i, (key, value) in enumerate(my_dict.items()):
	print(f'Index: {i}, Key: {key}, value: {value}')

index와 함께 keym value 순회

keys() 혹은 values() 사용

for i, key in enumerate(my_dict.keys()):
	print(f'Index: {i}, Key: {key}')

for i, value in enumerate(my_dict.values()):
	print(f'Index: {i}, Value: {value}')

역시 알고리즘을 풀어야 이런거 안까먹는다!

작성에 참고한 사이트들 :
https://velog.io/@kimwoody/Python-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%99%80-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC%EC%9D%98-%EC%A3%BC%EC%9A%94-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84
https://blog.hwahae.co.kr/all/tech/6662
https://codechacha.com/ko/python-iterate-on-dict-with-index/