Python Data Structure

기본 데이터 구조

- 스택과 큐(Stack & quere with list)

- 튜플과 집합(Tuple & Set)

- 사전(dictionary)

- Collection 모듈

 

Stack

- 나중에 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조

- Last In First Out(LIFO) - '리포' 구조라고 읽음

- Data의 입력을 Push, 출력을 Pop이라고 함

입력은 Push, 출력은 Pop

- List(리스트)를 사용해서 스택 구조를 설계할 수 있음

- 리스트에서는 push를 append()로, pop을 pop()으로 구현

 

Quere

- 먼저 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조

- First In First Out(FIFO) - '피포' 구조라고 읽음

- Stack과 반대되는 개념

뒤에 쌓이고 앞으로 빠지는 구조

- 파이썬은 리스트를 사용하여 큐 구조를 활용

- put을 append(), get을 pop(0)로 구현함

 

Tuple

- 값의 변경이 불가능한 리스트

- 선언 시에 []가 아닌 ()으로 사용

- 리스트의 연산, 인덱싱, 슬라이싱 등을 동일하게 사용

값의 변경이 불가능하다.

- 왜 쓸까? -> 프로그램을 작동하는 동안 변경되지 않는 데이터의 저장, 함수의 반환 값 등 사용자 실수 사전 방지

- 값이 하나인 튜플은 (1, ) 등 콤마를 붙여주어야 함

 

Set

- 값을 순서없이 저장, 중복 불허하는 자료형

- Set 객체 선언을 이용하여 객체 생성

add, remove, update, discard, clear

- 수학에서 활용하는 다양한 집합 연산 가능

- .union (합집합), .intersection (교집합), .difference (차집합)

- | (합집합), & (교집합), - (차집합)

 

Dict

- 데이터를 저장할 때는 구분 지을 수 있는 값을 함께 저장

- 구분을 위한 데이터 고유값을 Identifier 또는 Key라고 함

- Key 값을 활용하여 데이터 값(Value)를 관리함

학번이 Key이고 나머지 정보를 Value로 저장하면 되겠다.

- key, value를 매칭하여 key로 value를 검색함

- 다른 언어에서는 Hash Table이라는 용어를 사용함

- {key1:value1, key2:value2, …}

- dict.item() : (key, value) 형태의 튜플로 반환됨

- dict.keys(), dict.values()

 

Collections Module

- List, Tuple, Dict에 대한 python Built-in 확장 자료 구조(모듈)

- 편의성, 실행 효율 등을 사용자에게 제공함

- deque, Counter, OrderedDict, defaultdict, namedtuple

 

deque

from collections import deque

- Stack과 Quere를 지원하는 모듈

- List에 비해 효율적인(빠른) 자료 저장 방식을 지원함

- rotate, reverse 등 Linked List의 특성을 지원함

- 기존 list 형태의 함수를 모두 지원함

deque의 강점 

- .rotate(1) : 맨뒤에 값을 떼서 맨 앞으로 붙여줌

- .appendleft() : 맨 앞에 append 해줌

- .extendleft(list) : list를 통째로 앞에 append해줌

- deque는 기존 list보다 효율적인 자료구조를 제공함

- 효율적인 메모리 구조로 처리 속도 향상

 

OrderedDict

- Dict와 달리, 데이터를 입력한 순서대로 dict를 반환함

- dict도 python 3.6부터 입력한 순서를 보장하여 출력함

- 지금은 크게 의미가 없음

 

Defaultdict

- Dict type의 값에 기본 값을 지정, 신규값 생성 시 사용하는 방법

from collections import defaultdict

(좌) 함수 만들어서 defaultdict의 인자로 넣어줄 수 있음, (우) 함수 없이 lambda로 넣어줄 수도 있음

- 하나의 지문에 각 단어들이 몇 개나 있는지 세고 싶을 경우?

- Text-mining 접근법으로써, Vector Space Model

 

Counter

- Sequence type의 Data element들의 갯수를 dict 형태로 반환

문자열을 넣어도, 각 문자의 갯수가 몇 개인지 반환해줌

- Dict type, keyword parameter 등도 모두 처리 가능

각 갯수가 담긴 dict를 Counter로 바꿔주고 elements 명령하면 위와 같은 리스트로 바꿔줌 

keyword args도 처리해줄 수 있음, 갯수 간의 뺄셈 결과도 반환 가능

- Set의 연산들을 지원함

 

Namedtuple

- Tuple 형태로, Data 구조체를 저장하는 방법

- 저장되는 data의 variable을 사전에 지정해서 저장함

Point 변수를 선언하는데, x, y가 들어갈 예정

p라는 변수에 Point(x, y)를 선언해주면, 위와 같이 들어감

 

Reference

• Boostcourse - Python Data Structure
• CS50 2020 - Lecture 5 - Data Structures