[03] Python data structure

Python에는 다른 언어와 마찬가지로 다양한 자료구조들이 있습니다.

기본적인 자료구조와 Python에 특화된 Collection 모듈에 대해 알아보겠습니다.

 

1️⃣ 기본 data structure

 

1) 스택과 큐 (stack & queue)

 

스택은 나중에 나온 데이터를 먼저 반환하도록 설계된 메모리 구조입니다.

Last In First Out (LIFO) 구조라고 하며, 알고리즘에서 괄호가 닫아졌는지 체크하는 문제 등에 사용됩니다.

 

Python에서는 스택의 구현은 리스트로 가능합니다.

 

 

큐는 먼저 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조입니다.

First In First Out (FIFO)구조라고 하며, 알고리즘에서 은행 창구 문제 등에 사용됩니다.

 

Python에서는 큐 구현도 스택과 마찬가지로 리스트로 가능합니다.

이때 a.pop(0) (리스트의 0번 인덱스를 pop)를 사용해서 구현할 수 있습니다. 

 

 

2) 튜플 (tuple)

 

튜플은 값의 변경이 불가능한 리스트라고 생각하면 됩니다.

선언 시 "[ ]"를 사용하는 것이 아닌 "( )"를 사용하며 리스트의 연산, 인덱싱, 슬라이싱 등을 동일하게 사용할 수 있습니다.

 

튜플의 사용목적은 값의 immutable입니다.

따라서 프로그램을 구동하는 동안 알파벳 순서, 학번 등에 사용합니다. 튜플을 사용하면 다른 사용자가 값을 변경하려는 것을 막을 수 있습니다.

 

튜플은 하나를 사용하면 일반 정수로 인식하고, 만약 값이 하나인 Tuple로 인식하고 싶다 할 때는 반드시 ", "를 붙여야 합니다.

>>> t = (1) # 일반 정수로 인식
1

>>> t = (1, ) # 값이 하나인 Tuple은 반드시 ","를 붙여야 함
(1, )

 

 

3) 집합 (set)

 

집합은 값을 순서없이 저장하면서 중복을 불허하는 자료형입니다.

중복을 제거해주어야하는 문제에서 쓸모 있는 자료형입니다.

 

또한, set의 장점은 수학에서 활용하는 다양한 집합 연산이 가능합니다.

s1, s2를 set 객체로 생성해주고,

>>> s1 = set([1,2,3,4,5])

>>> s2 = set([3,4,5,6,7])

합집합 s1 ∪ s2를 해주면

>>> s1.union(s2)    # s1과 s2의 합집합
{1, 2, 3, 4, 5, 6, 7}

>>> s1 | s2    # 이 것도 가능
{1, 2, 3, 4, 5, 6, 7}

 

교집합 s1 ∩ s2를 해주면

>>> set.intersection(s2)    # s1와 s2의 교집합
{3, 4, 5}

>>> s1 & s2   # 이 것도 가능
{3, 4, 5}

 

차집합 s1 - s2를 해주면

>>> s1.difference(s2)    # s1과 s2의 차집합
{1, 2}

>>> s1 - s2    # 이 것도 가능
{1, 2}

set은 이러한 집합 연산이 가능합니다.

 

 

 

4) 사전 (dict)

 

사전은 데이터의 Key (고유 값)과 Value (값)을 함께 저장한 자료구조입니다.

dict은 key와 value를 매칭하여 key로 value를 찾을 수 있고, 다른 언어에서는 Hash Table이라는 용어로 사용됩니다.

>>> country_code
{＇America＇: 1, ＇China＇: 86, ＇Korea＇: 82, ＇Japan＇: 81}

>>> country_code.items() # Dict 데이터 출력
Dict_items([(＇America＇, 1), (＇China＇, 86), (＇Korea＇, 82), (＇Japan＇, 81)])

>>> country_code.keys() # Dict 키 값만 출력
Dict_keys(["America", "China", "Korea", "Japan"])

>>> country_code["German"]= 49 # Dict 추가

>>> country_code
{'America': 1, 'German': 49, 'China': 86, 'Korea': 82, 'Japan': 81}

>>> country_code.values() # Dict Value만 출력
dict_values([1, 49, 86, 82, 81]

 

for문에서 dict을 사용할 떄 items() 함수를 사용하면 k, v를 둘 다 사용 가능합니다.

>>> for k,v in country_code.items():
... print ("Key : ", k)
... print ("Value : ", v)
...
Key : America
Value : 1
Key : Gernman
Value : 49
Key : China
Value : 86
Key : Korea
Value : 82
Key : Japan
Value : 81

 

또한 in 연산자를 사용하면 key나 value에 해당 값이 있는지 확인 가능합니다.

>>> "Korea" in country_code.keys() # Key값에 "Korea"가 있는지 확인
True

>>> 82 in country_code.values() # Value값에 82가 있는지 확인
True

 

dict을 sort할 때 sorted의 두 번쨰 매개변수에 value값을 기준(item [1] => value)으로 잡고 reverse를 true로 하면 value의 큰 값부터 내림 차수로 정렬됩니다. 

def getKey(item):   #item의 2번째(Value)값을 반환
    return item[1]

>>> sorted_dict = sorted(dictlist, key=getKey, reverse=True) #list를 입력 줄 수로 정렬

 

 

2️⃣ Collections 모듈

Collections 모듈에는 위에 있는 기본 자료구조에 편리함을 더한 확장 자료구조들이 존재합니다.

기본 자료구조보다 편의성이 증대와 함께 실행 효율도 좋아진 자료구조들이 있습니다.

 

1) deque

 

deque는 stack과 queue를 합친 자료구조라고 생각하면 됩니다.

List에 비해 효율적이고 빠른 자료 저장 방식을 지원합니다.

 

또한 Linked List의 특징을 지원해서 삽입 삭제가 빠르게 수행됩니다.

그 중 rotate() 함수는 list의 값을 회전시켜서 보여줍니다.

from collections import deque

deque_list = deque()
for i in range(5):
	deque_list.append(i)    # {0,1,2,3,4}

>>> deque_list.rotate(2)    # 값이 양수면 오른쪽으로 회전합니다.
{3,4,0,1,2}

>>> deque_list.rotate(-2)    # 값이 음수면 왼쪽으로 회전합니다.
{0,1,2,3,4}

 

앞에서 설명했듯이 기존 list보다 효율적인 자료구조라서 아래와 같은 방법으로 코드를 돌리면 list의 평균 수행 속도보다 훨씬 빠르다는 것을 알 수 있습니다.

def deque_list():
    deque_list = deque()
    for i in range(100):
        for i in range(100):
            deque_list.append(i)
            deque_list.pop()

%timeit general_list()  #timeit을 하면 juptyer notebook에서 여러 번을 돌려서 평균값을 산출해줍니다.

 

2) OrderedDict

 

OrderedDict는 key값이 데이터를 입력한 순서대로 반환합니다.

하지만 dict도 Python 3.6부터 입력한 순서를 보장하여 많이 사용하지 않습니다.

 

 

3) defaultDict

 

defaultDict는 default값을 지정하여 만약 dict안에 찾는 key값이 없어도 오류가 나지 않는 자료형입니다.

원래 일반 dict에서는 key값이 없을 때 in 연산자를 사용해 추가적인 코드를 작성했는데

그에 반해 defaultDict을 사용하면 훨씬 코드가 간결해지는 것 같습니다.

from collections import defaultdict

d = defaultdict(object) # Default dictionary를 생성
d = defaultdict(lambda: 0) # Default 값을 0으로 설정 (함수가 들어가야함)

>>> print(d["first"])
0

 

4) Counter

 

Counter는 문자열, list와 같은 Sequence type의 데이터 요소들의 개수를 세서 dict으로 반환합니다.

사용하면 정말 편리한 모듈 중 하나입니다.

from collections import Counter

c = Counter()		# a new, empty counter
c = Counter('gallahad')		# iterable이 가능한 타입을 Counter에 넣어주기만 하면 됩니다.

>>> print(c)
Counter({'a':3, 'l':2, 'g':1, 'd':1, 'h':1})

또한 elements()를 사용하면 요소를 나타낼 수 있습니다.

c = Counter({'red':4, 'blue':2})

>>> print(list(c.elements()))
['blue', 'blue', 'red', 'red', 'red', 'red']


c = Counter(cats=4, dogs=8)

>>> print(list(c.elements()))
['dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'dogs', 'cats', 'cats', 'cats', 'cats']

또한, Counter는 set 연산을 지원해서 합집합, 교집합, 차집합을 사용할 수 있습니다.

 

5) namedtuple

 

namedtuple는 Tuple형태로 Data 구조체를 저장하는 방법입니다.

C언어의 struct라고 생각하시면 됩니다.

from collections import namedtuple

>>> Point = namedtuple('Point', ['x', 'y'])				# Point라는 구조체에 요소는 x,y 입니다.

>>> p = Point(11, y=22)							# 11은 x에 22는 y에 삽입됩니다.

>>> print(p[0] + p[1])							# 인덱스로 표현이 가능합니다.
33

>>> x, y = p								# 언패킹을 통해 다른 변수에 넣을 수 있습니다.

>>> print(p.x + p.y)							# 구조체이므로 p의 x와 p의 y를 출력할 수 있습니다.
33

>>> print(Point(x=11, y=22))

하지만 Python에서는 namedtuple보다는 Class를 많이 사용한다고 합니다.