Python에서 queue 구현할 때는, 제발 collections.deque을 쓰세요

위의 제목은 사실 본인에게 하는 말이다 😅

이 글에서는 Python에서 queue 구현 시, 반드시 collections.deque를 사용해야하는 구조적인 이유와 더불어, 왜 코드 구현 시에 '코드에 사용하는 코드의 구조'까지 찾아 정리하게 되었는지에 대한 사설이 포함되어 있다.

 

[사설] 이 글과 같은 고민이 중요하다고 느끼게 된 계기

1. list로 queue를 구현한 자의 최후

프로그래머스 2022 KAKAO TECH INTERNSHIP 두 큐 합 같게 만들기 문제에서 런타임 에러+메모리 초과로 문제를 해결하지 못한 적 있었다. (2023.11.10)

학교 선배가 보고, collection.deque를 쓰세요라는 말을 해주셨는데

'아, deque 뭐 그거 파이썬에서 list 대신 쓰는 빠른 자료형이 있었지' 라는 생각이 들면서 list를 deque로 바꾸는 것만으로 문제가 해결되었던 경험이 있다.

(아주 피상적인 수준의 이해이다. 이렇게 이해하고 코딩하면 코더가 되기 십상이다. 처음 공부할 때는 받아들여야하는 지식의 양이 많아서 이렇게 이해할 수도 있겠지만, 지속적으로 공부하여 더더더 근원적으로 풀이나 코드를 이해해야 한다.)

 

2. 그룹바이 온라인 채용 설명회에서 Corca의 인재상

또, 개인적으로 매우 존경하는 학교 선배님이 운영하는 그룹바이의 온라인 채용 설명회를 간 적이 있다. (2023.11.17)

사전 신청을 하지 않았는데도 들어갈 수 있게 해주셔서 넘 감사했다...🥹

최근 인공지능 기반의 서비스를 제공하는 기업에 들어가고 싶다는 열망이 생겨서, 기업 리스트를 보다가 Corca를 알게 되었다. 꼭 AI Researcher 직군이 아니더라도 경험 해봤던 FE에서의 데이터 수집 파이프라인을 메인으로 하면서 AI 분들과 같이 공부를 해보고 싶은 마음?!

 

그렇게 가볍게 채용 설명회를 듣게 되었는데, Corca 뿐만 아니라 스타트업들 중에서도 알짜 기업이라할까 실력있는 분들만 모여있다는 인상을 강하게 받으면서, Corca는 정말 합류하고 싶은 마음이 굴뚝처럼 생기는 멋진 기업이었다.

일단, 팀원들 모두 서울과학고나 명문대생인 것은 차치하더라도 객관적으로 세계적인 AI Cimpetition에서 좋은 결과를 많이 내고 있었고, AI field에 대한 깊은 이해 없이는 불가능한 것이었다.

 

CTO분께서 발표를 맡으셨는데 계속해서 강조하는 것이, 전 개발직군+기획직군 포함해서 '잘 갖추어진 프레임워크를 그냥 사용하지 말고, 그 원리를 충분히 이해해서 트러블 슈팅이나 성능 개선을 이룬 경험있는 분들과 일하고 싶다.'라는 것이었다.

요즘 스쳐지나갔던 나의 직업적, 능력적 전문성을 어떻게 쌓아야할까, 특히 GIST 재학생으로서 차별화될 수 있는 것은 무엇일까 생각이 다시금 들면서 수학도 더 공부함과 동시에, 기본적으로 코드를 작성하는 마음가짐을 Corca의 인재상처럼 잡자라는 생각이 들었다.

 

여기까지 앞으로 deque를 포함해서 원리적으로 이해한 상태에서 코드를 짜야겠다는 다짐이었다.

 

[본론] list vs. deque

먼저, queue라는 자료형에 대해 익히 알고 있었다.

data를 관리하는 구조인, 자료구조에서 등장하는 개념으로 stack의 후입선출과 대비되는 선입선출 구조이다.

 

queue를 실제로 코드에서 사용할 때 가장 많이 사용되는 함수는 일반 파이썬 기준 append와 pop(0)이다. queue에 새롭게 data를 입력할 때는 append로 list의 마지막 요소로 붙이고, 선입선출이므로 pop(0)으로 list의 가장 앞의 요소를 뗀다.

 

문제가 되는 점은 pop(0)인데, [링크]에 따르면 pop(last)를 제외한 pop(intermediate)는 시간 복잡도가 O(n)인 것이다. 반면 Python 기본 라이브러리 collections의 deque.popleft()는 O(1)이다.

 

이러한 차이점은, list는 dynamic array, deque는 doubled linked list인 것에서 발생한다.

list는 연속된 메모리 공간에서 element의 reference를 저장된다.

따라서 pop(0)를 시행하는 경우, 각 reference가 앞으로 한 칸씩 당겨지게되면서 n번의 시행이 필요하게 된다.

 

한편, deque의 구조인 double-linked list는 각 요소가 자신의 전, 후 요소의 메모리 주소를 가지고 있다. 따라서, popleft()를 실행하면 가장 첫 번째 요소와 두 번째 요소 간의 연결만 끊어주면 popleft() 함수 실행이 완료된다.

 

[추가] Python 내부 구조라는 새로운 세계

이 글을 작성하면서 참고한 글들의 깊이가 제각각이었는데,

특히 너무 인상깊었던 글이 CPython이라고, Python의 구현 C 코드를 분석하여 내부 구조를 이해하는 시리즈들이었다.

내 실력이 충분히 성장 궤도에 올랐을 때... 비슷한 활동을 해보고 싶다.

+ 더해서 Cython, Jython, PyPy... ㄷㄷ 점점 혼란하다.