파이썬에서 기본적으로 제공하는 범용 자료구조인 리스트 (List) 튜플 (Tuple) 사전 (Dict) 에 대해서 Built-in 확장형 자료구조도 있다.
빌트인이란 (Bulit-in) 오피스텔에 가전제품 장착되어 있는 것처럼, 파이썬 프로그램 안에 기본으로 탑재되어 있다는 뜻이다. 선풍기를 기본 제공하지만 필요시 시스템에어컨도 신청해서 사용할 수 있다고 보면 되겠다. 이렇게 파이썬에서 호출해서 쓰는 추가적인 기능을 모듈 이라고 한다.
자료 구조에 대한 확장형태인 컬렉션 모듈은 대표적으로 다음과 같은 것들이 있다.
☀️️ from collections import deque
☀️️ from collections import Counter
☀️️ from collections import OrderedDict
☀️️ from collections import defaultdict
☀️️ from collections import namedtuple
위 문장은 collections 라는 모듈에서 각각의 확작형 자료구조를 호출해온다는 의미이다. 맨 오른쪽에 있는 deque, Counter, OrderedDict, defaultdict, namedtuple 이것들이 확장형 자료구조의 명칠들이 되겠다.
백문이 불여일코. 직접 코드를 보고 따라하면서 하나씩 살펴보자.
define deque list
deque는 Stack과 Queue를 지원하는 모듈이다. 스택과 큐 개념이 가물가물하면 지난 시간에 공부한 내용을 다시 복습…
스택 (Stack) : 나중에 넣은 데이터가 먼저 반환되도록 설계한 메모리 구조, 후입선출
- 큐 (Queue) : 먼저 줄 선 데이터가 먼저 반환되는 구조, 선입선출
예시를 통해 deque를 선언하고 자료를 추가하는 것을 해보자.
from collections import deque
먼저 컬렉션 모듈에서 deque를 불러오면
deque_list=deque()그 다음부터 deque 형태의 자료형을 선언할 수 있다. deque() 로 선언하면 먼저 빈 형태의 deque 자료구조가 하나 만들어진다. deque는 ([]) 괄호안에 데이터를 저장한다.
for i in range(5):
deque_list.append(i)for 반복문을 통해 range(5) 즉 0에서 4까지의 숫자에 대한 반복 수행을 지정하고, 수행할 내용은 선언한 변수 deque_list에 하나씩 append를 하는 것이다. 그리고 print를 해보면 0에서 4까지 추가된 것을 알 수 있다.
deque_list.appendleft(10)appendleft를 하면 오른쪽이 아닌 왼쪽에 데이터가 추가된다.
데큐 리스트에서 데이터를 뽑아내는 것은 pop()를 쓰면 오른쪽부터, pop(0)으로 하면 왼쪽부터 가져오는 것은 지난 시간에 학습했었다.
덱, 또는 데큐라고 읽는 deque가 Double Ended Queue의 약자임을 생각하면 특성이 쉽게 이해가 된다. 이렇게 양 끝에서 모두 삽입과 삭제가 가능하도록 되어있는 양방향 선형 자료구조이다.
Linked List
데큐 리스트의 또 다른 특징은 링크드 리스트 (Linked List) 자료구조를 가진다는 것이다.
linked list란 위와 같이 어떠한 데이터를 저장할 때 하나의 노드는 정수값과 다음 노드를 가리키는 주소값으로 구성되어 있는 형태이다. 데이터가 메모리 주소로 연결이 되어 있는 것인데 사실 지금 파이썬 초보단계에서 이해하기는 조금 어려운 개념이다.
파이썬 초급 단계에서는 함수써서 어떻게 명령어를 코딩하는지 그런 기본적인 학습을 하지만, 나중에 점점 어려워지는 실무와 관련된 수준이 되면 엄청나게 많은 데이터를 어떻게 저장하고 관리하고 보다 효율적인 시스템으로 운영하여 자원을 절약하고 속도를 높일지가 중요하게 되는 것 같다.
더블 링크드 리스트는 이렇게 양방향으로 연결되어 있는 구조이며
circular linked list는 이렇게 순환형 구조를 가져서 rotate를 시켜줄 수가 있다. 실제로 예제 학습을 통해서 이게 대체 뭔소린지 감을 잡아보자.
이렇게 함수로 변수명.rotate(몇칸) 형태로 입력해주면 리스트가 우측으로 지정한 칸수만큼 rotating shift 되어 갱신된다. 반대 방향으로 움직이고 싶다면 칸수를 -1 -2 이런식으로 해주면 된다.
또 deque(reversed(변수명)) 형태로 입력해주면 역순으로 정렬을 바꾼 리스트를 반환시킬 수 있다.
이 때 deque() 형태로 입력한 것은 괄호안에 있는 것을 deque list화 했다는 의미이므로, 여기서 지정한 변수명 d에 대해서 데이터가 변한것이 아니다.
궁금해서 이렇게 변수 d를 리버스 시키고 deque 리스트화 한 녀석을 출력한 뒤, 다시 원래의 변수 d를 확인해 보았더니 변하지 않은 상태로 나왔다. 그렇다고 rotate처럼 d.reversed() 형태로 입력하면 에러가 난다.
리버스 시켜서 원래 변수에 덮어씌우고 싶다면 d=deque(reversed(d)) 이렇게 해주면 된다.
위와 같이 변수명.extend() 또는 변수명.extendleft() 형태로 추가할 수도 있다.
이 때 extend에는 iterable argument가 들어가야 한다. iterable이란 사전적 의미와 같이 반복 가능한 객체를 말한다. 파이썬에서는 list, dictionary, set, string, tuple, bytes, range 등이 iterable한 타입이다.
단순한 정수형인 (int) 원소는 iterable에 해당되지 않기 때문에 extend(5) 이런 식으로 입력하면 에러가 출력되는 것을 확인할 수 있다.
append와 extend의 차이점이 바로 이 부분인데,
append는 그냥 object를 뒤에 추가해 주는 것이고, extend는 iterable object의 원소를 (element) 데큐 리스트에 appending 시켜주는 기능이다.
뭔가 한가지를 공부해서 정리하다 보면 세 가지의 모르는 개념들이 추가로 생기는 느낌인데… 결국 하나하나 빠삭하게 정복해나가는 수밖에 없겠지. 다른 블로그들을 보면 iterable과 iterator에 대한 개념차이 정리만으로도 포스팅 하나가 필요한 분량이라 차차 공부하면서 또 나오면 다시 봐야겠다.
일단은 하나씩 직접 파이썬 돌려보면서 습득하는게 중요하지, 개념 이해안된다고 막히는 부분에서 낑낑대고 있는것은 프로그래밍을 공부하는데 올바른 방법은 아닌거 같다. 이런게 있구나 정도로 짚고 넘어가면서 빨리빨리 진도를 빼는게 더 중요한듯. 그러면 나중에 저절로 이해가 될 날이 올테니.
list vs deque 속도비교
파이썬 초보자가 보기엔 리스트나 데큐나 그게 그건데 굳이 왜 이걸 쓴다고 이렇게 어려운 공부를 추가로 해야하는지 잘 이해가 되지 않는다. deque를 쓰는 이유는 앞서 말한 linked list 특징 때문에 데이터를 갈무리하는 속도가 훨씬 빨라진다는 데에 있다.
리스트 변수 l과 데큐 변수 d를 선언하고 각각 5000개의 원소를 추가했다 빼는 명령을 반복한 후 걸리는 시간을 측정한 결과이다. deque가 list에 비해 걸리는 시간이 절반 이하인 것을 알 수 있다.
시간 비교는 위와같이 timeit 함수를 이용해서도 구할 수 있다. 함수를 하나 디파인하고 그 함수 동작하는데 걸리는 시간을 비교해주는 것으로 엄청 많이 반복 시행을 하고 그 평균값과 표준편차까지 나타내 준다.
deque는 double-linked list이며 이는 그림에서처럼 하나의 데이터를 저장할 때 두개 이상의 포인터를 추가로 가지고 있게 된다. 따라서 메모리가 많이 필요하지만 그만큼 속도는 향상시킬 수 있는 것이다.
수치적으로 말하면 deque의 데이터 액세스 속도는 O(1)로 나타낼 수 있다. 이는 constant time으로 어떤 경우든지 1의 시간이 필요하다는 뜻이다. 이는 O(n)으로 나타내어지는 알고리즘에 비해 속도가 빠르다. O(n)은 원소가 많을수록 인덱싱하는데 시간이 늘어나는 것을 뜻한다.
collections module에 여러가지가 있는데 그 중 deque에 대해서 알아보았다. 하나를 공부하려고 하다가 linked-list, iterable, time체크하는 함수, Big-O notation 속도표현 개념 등 새롭게 알아야 할 것들만 잔뜩 생긴 느낌이다.