[지식/이론][python] 컬렉션 자료구조

2023-05-22 5 분 소요

개요

컬렉션(collection) 자료구조는 시퀀스 자료구조와 비슷해보이나, 데이터를 서로 연관시키지 않고 그저 모아두기만 하는 일종의 컨테어니이다.

컬렉션 자료구조는 시퀀스 자료구조가 가지는 일부 속성을 지닌다.

멤버십 연산자 in
크기 함수 len(seq) 제공
반복성: 반복문의 데이터 순회 가능.

파이썬 내장 컬렉션 자료형에는 셋, 딕셔너리가 있고, 파이썬 내장 모듈인 collections에서도 다른 컬렉션 자료형들을 제공한다.

셋 (set)

집합이라는 뜻을 가진 셋은 파이썬의 내장 컬렉션 자료형 중 하나로, 다음의 특징들을 가진다.

가변적이다.
반복 가능하다.
중복 요소가 없다. (있는 경우 하나로 줄여 중복을 없앤다)
정렬되지 않는다.
인덱스 연산을 할 수 없다.
멤버십 테스트나 중복 항목 제거에 사용될 수 있다.

셋에 대한 시간복잡도는 다음과 같다고 한다.

삽입: O(1)
합집합(union) : O(m + n)
교집합(intersection) : O(n) (두 셋 중 더 작은 셋에 대해서만 계산하면 되므로 → 무슨 말인지 이해가 안감)

프로즌 셋(frozen set)은 셋과 달리 불변 객체이다. 따라서 셋의 요소를 변경하는데에 쓰이는 메서드들을 쓸 수 없다. 파이썬에선, frozenset(iterable) 함수를 사용하면 생성할 수 있다.

셋 메서드

Set 문서에 없는 셋 메서드들 또는 부족한 설명을 여기서 기술한다.

add()

add(x)는 셋에 어떤 요소 x가 없는 경우 해당 요소를 셋에 추가한다. 이미 셋에 존재하는 경우, 아무런 변화가 일어나지 않는다.

some_set = {1, 2, 3}
some_set.add(4)
some_set.add(3)
print(some_set)

{1, 2, 3, 4}

update()와 |= 연산자

A.update(B) 또는 A

= B는 셋 A에 셋 B를 합치는 합집합 연산을 수행한다. update() 메서드 자체는 아무것도 반환하지 않는다.

A_set = {1, 2, 3}
B_set = {'a', 'b', 'c', 1, 2}
A_set.update(B_set)
print(A_set)
print(B_set)

{1, 2, 3, 'a', 'b', 'c'}
{1, 2, 'a', 'b', 'c'}

union()과 | 연산자

update()와 똑같이 합집합 연산을 하지만 update()와 달리 A.union(B)는 연산 결과를 셋 A에 저장시키지 않고 연산 결과의 복사본을 반환하는 형태이다. 따라서 update()와 달리 union()의 연산 결과가 기존 셋의 내용을 바꾸지 않는다.

A_set = {1, 2, 3}
B_set = {'a', 'b', 'c', 1, 2}
assemble = A_set.union(B_set)
print(assemble)
print(A_set)
print(B_set)

{1, 2, 3, 'a', 'b', 'c'}
{1, 2, 3}
{1, 2, 'a', 'b', 'c'}

위 예제를 보면 union()의 연산 결과가 기존의 A_set, B_set 변수의 내용을 변경시키지 않음을 알 수 있다.

clear()

해당 메서드는 셋의 모든 요소들을 제거하여 빈 셋이 되도록 한다.

A_set = {1, 2, 3}
A_set.clear()
print(A_set)

set()

discard(), remove(), pop()

세 메서드 모두 셋의 특정 요소를 제거하는 역할을 가지나, 그 특성이 조금씩 다르다.

discard(x) → None 셋의 요소 x를 제거한다. 셋에 없는 요소를 제거하려 하는 경우, 아무런 일도 일어나지 않는다.

  a_set = {'코끼리', '바다사자', '토끼', '사자', '하마'}
  set_discard = a_set.discard('바다사자')
  set_discard_no_ele = a_set.discard('바다사자')
  print(set_discard)  # 반환값이 있을까?
  print(set_discard_no_ele)  # 반환값이 있을까?
  print(a_set)

  None
  None
  {'토끼', '코끼리', '사자', '하마'}

remove(x) → None 셋의 요소 x를 제거한다. 셋에 없는 요소를 제거하려 하는 경우, KeyError 예외를 일으킨다.

  a_set = {'코끼리', '바다사자', '토끼', '사자', '하마'}
  set_remove = a_set.remove('바다사자')
  print(set_remove)
  print(a_set)
    
  set_remove_no_ele = a_set.remove('바다사자')
  print(set_remove_no_ele)  # KeyError 발생

  None
  {'사자', '하마', '토끼', '코끼리'}
  KeyError: '바다사자'

pop() 셋에서 무작위로 한 요소를 제거하고 그 요소를 반환한다. 빈 셋일 경우 KeyError 예외를 발생시킨다.

  a_set = {'코끼리', '바다사자'} 
  set_pop = a_set.pop()
  set_pop2 = a_set.pop()
    
  print(set_pop)
  print(set_pop2)
  print(a_set)
    
  print(a_set.pop()) # KeyError 예외 발생

  바다사자
  코끼리
  set()
  KeyError: 'pop from an empty set'

딕셔너리 (dictionary)

key: value 형태를 지니는 파이썬 내장 컬렉션 자료형인 딕셔너리는 해시 테이블(hash table)로 구현되어 있다. 여기서 해시 테이블은 키-값이 서로 연관되어 있고, 키를 통해 키와 연관된 값을 얻는 연관 배열(asssociative array)을 구현하는 데에 사용되는 자료구조이다. 해시 함수는 특정 객체에 해당하는 임의의 정수 값을 상수 시간 내에 계산한다. 이렇게 계산된 정수 값은 연관 배열의 인덱스로 쓰인다.

해시에 관한 내용은 hashlib 문서의 “해시의 개념” 참조 (해당 페이지 준비 중).

딕셔너리는 다음의 특징을 지닌다.

반복 가능
멤버십 연산자 in 사용 가능
길이를 구하는 len() 함수 사용 가능
컬렉션 매핑 타입(mapping type)이라고 불린다. 키와 값을 연결하기에 붙여진 이름 같다.
딕셔너리의 특정 요소에 접근하는 시간복잡도는 O(1)이다. 이는 딕셔너리의 요소들은 모두 고유하기 때문이다.
가변 객체이다. 그러나 key에는 불변 객체를 사용해야 한다. (value는 불변, 가변 모두 상관없다)
딕셔너리는 요소의 삽입 순서를 기억하지 않아 인덱스와 슬라이싱을 사용할 수 없다.

이 외 딕셔너리에 대한 자세한 설명과 관련 메서드들은 딕셔너리 (dictionary) 문서 참조.

딕셔너리 메서드

pop(), popitem()

pop(key)는 딕셔너리 내의 key 요소를 제거한 후, 해당 키에 연결된 값을 반환한다.

popitem()은 파이썬 3.6 버전 이상에서는 마지막 요소를 삭제하고, 그 요소를 (키, 값) 튜플 형태로 반환한다. 파이썬 3.5 이하 버전에서는 임의의 요소를 삭제하고 반환하므로 실행할 때마다 그 값이 달라진다고 한다. 다음은 파이썬 3.6 이상 버전에서 작성하였다.

some_dict = {
    'name': '김이썬',
    'age': 20,
    'user_id': 'kim_python',
    'job': '개발자'
}

a = some_dict.pop('user_id')
print(a)
print(some_dict)
print('======')

b = some_dict.popitem()
print(b)
print(some_dict)

kim_python
{'name': '김이썬', 'age': 20, 'job': '개발자'}
======
('job', '개발자')
{'name': '김이썬', 'age': 20}

clear()

clear()는 딕셔너리 내의 모든 요소들을 삭제한다.

some_dict = {
    'name': '김이썬',
    'age': 20,
    'user_id': 'kim_python',
    'job': '개발자'
}

some_dict.clear()
print(some_dict)

{}

딕셔너리 관련 작업 시간복잡도

연산	시간복잡도
복사	O(n)
항목 조회	O(1)
항목 할당	O(1)
항목 삭제	O(1)
멤버십 테스트 in	O(1)
반복	O(n)

딕셔너리 순회

반복문에서 딕셔너리 순회 시 보통 키를 이용한다. 파이썬 3.6 버전 이하에서는 딕셔너리의 키가 임의의 순서대로 나타나고, 그 이상의 버전에서는 삽입한 순서대로 나타난다.

다음은 딕셔너리의 keys(), items() 메서드를 이용하여 딕셔너리를 반복문 내에서 순회하여 출력하는 예제이다.

some_dict = {
    'name': '김이썬',
    'age': 20,
    'user_id': 'kim_python',
    'job': '개발자'
}

for key in some_dict.keys():
    print(key, some_dict[key])
print('=====')

for key, value in some_dict.items():
    print(key, value)

name 김이썬
age 20     
user_id kim_python
job 개발자
=====
name 김이썬
age 20
user_id kim_python
job 개발자

딕셔너리 분기

딕셔너리를 이용하면 if문 대신 더 효율적인 분기문을 만들 수 있다.

def print_true():
    print(True)

def print_false():
    print(False)

functions = {'t': print_true, 'f': print_false}
choose = 't'
functions[choose]()

True

collections: 파이썬 컬렉션 데이터 자료형

파이썬 표준 라이브러리인 collections 모듈에서는 다양한 딕셔너리 자료형을 제공한다. 이미 파이썬 표준 라이브러리 (1) 문서의 defaultdict, OrderedDict, Counter 부분에 설명이 되어 있는데 이들 모두 collections 모듈에서 제공하는 딕셔너리 자료형들에 해당한다.

OrderedDict() : 정렬된 딕셔너리 (ordered dictionary) 자료형이며, 삽입 순서대로 요소들을 저장하는 역할을 한다. 파이썬 3.7 이상부터는 파이썬 내장 딕셔너리도 삽입 순서를 보존한다. 정렬된 딕셔너리를 효율적으로 사용할 수 있는 경우는 딕셔너리를 여러 번 순회할 때와 요소 삽입을 거의 하지 않을 때이다.

Counter() : 해시 가능한(hashable) 객체를 카운팅하는 서브클래스이다. 항목들의 발생 횟수를 갱신하고자 한다면 update() 메서드를 사용해도 되고, 직접 코드를 짜서 수행해도 된다.

  from collections import Counter
    
  seq1 = ['a', 'b', 'c', 'a', 'a', 'b', 'c', 'd', 'a', 'e']
  seq_count = Counter(seq1)
  print(seq_count)
    
  # update() 메서드로 새로 생긴 항목들의 개수 세어 포함시키기
  seq2 = ['f', 'g', 'g', 'a']
  seq_count.update(seq2)
  print(seq_count)
    
  # 직접 코드를 작성하여 새로 생긴 항목들의 개수 세어 포함시키기
  seq3 = ['h', 'i', 'q']
  for key in seq3:
      if key not in seq_count:
          seq_count[key] = 1
      else:
          seq_count[key] += 1
  print(seq_count)

  Counter({'a': 4, 'b': 2, 'c': 2, 'd': 1, 'e': 1})
  Counter({'a': 5, 'b': 2, 'c': 2, 'g': 2, 'd': 1, 'e': 1, 'f': 1})
  Counter({'a': 5, 'b': 2, 'c': 2, 'g': 2, 'd': 1, 'e': 1, 'f': 1, 'h': 1, 'i': 1, 'q': 1})

Reference

[1] 지은이: 미아 스타인, 옮긴이: 최길우, “파이썬 자료구조와 알고리즘”, (2019, 한빛미디어)

[2]

파이썬 코딩 도장: 25.1 딕셔너리 조작하기

This content is licensed under CC BY-NC 4.0

JeroCaller

[지식/이론][python] 컬렉션 자료구조

개요

셋 (set)

셋 메서드

add()

update()와 |= 연산자

union()과 | 연산자

clear()

discard(), remove(), pop()

딕셔너리 (dictionary)

딕셔너리 메서드

pop(), popitem()

clear()

딕셔너리 관련 작업 시간복잡도

딕셔너리 순회

딕셔너리 분기

collections: 파이썬 컬렉션 데이터 자료형

댓글남기기

참고

[React] Routing with React-Router

CRA 대신 리액트 프로젝트를 생성할 대체 수단 - Vite

[Roadmap][Personal Project] Spoon Suits 관련 글 로드맵

[Spoon Suits] Github Actions를 이용한 Github tag & release 자동화