[Python] FIFO 큐와 데크(Deque)

Introduction

프로그램을 작성하다 보면 선입선출 (First-In First-Out, FIFO) 구조를 위해 큐 (Queue) 자료구조를 활용하면 좋을 때가 있다.

 

FIFO 구조란 더 먼저 추가된 데이터를 먼저 사용하도록 하는, 말 그대로 순차적인 대기열을 떠올리면 이해가 편하다.

 

파이썬에서는 종종 이런 큐 자료구조를 이용해야 할 때, 기본적인 list 자료형에다 append와 pop(0) 메서드를 붙여서 간편하게 큐 자료구조를 흉내내 쓰곤 한다.

---

List Implementation

예를 들어, 아래와 같이 먼저 빈 리스트 오브젝트를 하나 생성한 후 append를 호출해 리스트 맨 뒤에 새로운 원소를 추가할 수 있으며, 반대로 pop(0)을 호출해 리스트 맨 앞의 원소를 제거하고, 그 값을 반환시킬 수 있다.

sample_queue = []

for i in range(5):
    sample_queue.append(i)
    print(sample_queue)

>>
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2, 3, 4]

for j in range(5):
    data = sample_queue.pop(0)
    print(data)

>>
0
1
2
3
4

기존의 리스트 자료형에서 쓰던 인터페이스를 그대로 사용할 수 있어 친숙하고, 큰 노력 없이 큐 자료구조를 이용할 수 있기에 편리하다. 하지만 이와 같은 방식은 한 번에 모아두어야 할 데이터의 갯수가 많은 상황에서는 문제가 있다. 한번 간단한 테스트를 통해 알아보자.

from time import time


print(f"[list.append]")
for num_items in range(5000, 20000, 5000):
    total_elapsed_time = 0.0
    for trial in range(num_trials):
        sample_queue = []
        start = time()
        for i in range(num_items):
            sample_queue.append(i)
        end = time()
        total_elapsed_time += end - start
    print(f"num_items: {num_items : <10} elapsed time (ms): {total_elapsed_time/num_trials*1000:.5f}")

>>
[list.append]
num_items: 5000       elapsed time (ms): 0.54049
num_items: 10000      elapsed time (ms): 1.06096
num_items: 15000      elapsed time (ms): 1.67152

print(f"[list.pop(0)]")
for num_items in range(5000, 20000, 5000):
    total_elapsed_time = 0.0
    for trial in range(num_trials):
        sample_queue = list(range(num_items))
        start = time()
        for i in range(num_items):
            sample_queue.pop(0)
        end = time()
        total_elapsed_time += end - start
    print(f"num_items: {num_items : <10} elapsed time (ms): {total_elapsed_time/num_trials*1000:.5f}")

>>
[list.pop(0)]
num_items: 5000       elapsed time (ms): 2.51228
num_items: 10000      elapsed time (ms): 9.91904
num_items: 15000      elapsed time (ms): 21.77977

첫 코드블록에서는 list 자료형을 이용한 큐에 데이터를 append 하는 작업의 시간 성능을 여러 데이터 갯수에 대해, 100번의 반복 시험을 통해 측정하고 있다. 데이터 갯수에 대해 linear 하게 총 소요 시간이 증가하는 것을 볼 수 있다. 여기까지는 큰 문제가 없어 보인다.

 

다음 코드블록에서는 큐에서 데이터를 받아오는 작업에 대해 동일한 방식으로 시간 성능을 측정하고 있다. 원소를 추가하는 데 걸리는 시간이 넣어야 할 원소의 갯수에 선형적으로 증가했던 이전 케이스와 달리, 원소 갯수의 제곱에 비례해서 시간이 소요되고 있다.

 

이 이유는.... pop(0) 오퍼레이션은 리스트에서 첫 번째 원소를 제거한 후, 남은 모든 원소의 포인터를 한칸씩 앞 자리로 복사해 넣는 작업을 거치면서 결국 N 사이즈의 리스트에 대해서 N-1번의 포인터 복사가 수행되는데 (pop(0) 한 번이 O(N)의 시간 복잡도를 가짐), 결국 N 개의 원소를 가지는 리스트에서 pop(0)를 사용해 모든 원소를 빼내려 하면 이를 다시 N번 반복해야 하므로, 결국 O(N^2)의 시간 복잡도를 보이게 되는 것이다.

 

소규모의 데이터를 다룰 때에는 큰 문제가 없지만, 대량의 데이터를 큐 자료구조로 다루어야 할 때에는 적합하지 않은 방식이다.

 

이 때 사용할 수 있는 대안이 collections 모듈의 deque 클래스이다 (보통 데크 라고 읽는 것 같다). 한번 예시와 함께 알아보자.

 

Better Way: Deque Implementation

아래는 맨 처음의 예시를 deque 클래스를 이용해 동일하게 구현한 코드이다.

from collections import deque

sample_queue = deque()

for i in range(5):
    sample_queue.append(i)
    print(sample_queue)

>>
deque([0])
deque([0, 1])
deque([0, 1, 2])
deque([0, 1, 2, 3])
deque([0, 1, 2, 3, 4])

for j in range(5):
    data = sample_queue.popleft()
    print(data)

>>
0
1
2
3
4

리스트를 이용한 구현에서와 동일하게, append를 호출해 새 원소를 추가할 수 있다. 다만 기존의 pop(0) 부분은 popleft() 함수로 변경해서 사용해야 한다. 리스트와 같이 인덱싱도 동일하게 수행할 수 있으며, 이미 가지고 있는 리스트를 이용해 deque 오브텍트를 생성하는 것도 가능하다. 아래의 예시를 참고하자.

from collections import deque

sample_queue = deque([8, 9, 10])

for i in range(5):
    sample_queue.append(i)

print(sample_queue)
print(sample_queue.popleft())
print(list(sample_queue))

>>
deque([8, 9, 10, 0, 1, 2, 3, 4])
8
[9, 10, 0, 1, 2, 3, 4]

deque 오브젝트를 바로 list로 캐스팅 해 쓸 수도 있다. 리스트 자료형과 인터페이스가 전반적으로 비슷하고, 서로 변환이 아주 간단하기 때문에 굉장히 편리하게 사용할 수 있다 (슬라이싱은 지원하지 않는다). 

 

그럼 이제 deque 클래스가 앞서 등장했던 pop 호출에서의 O(N)의 시간 복잡도 문제를 해결해 줄 수 있는지 확인해 보자.

from time import time
from collections import deque

num_trials = 100

...

print(f"\n[deque.append]")
for num_items in range(5000, 20000, 5000):
    total_elapsed_time = 0.0
    for trial in range(num_trials):
        sample_queue = deque()
        start = time()
        for i in range(num_items):
            sample_queue.append(i)
        end = time()
        total_elapsed_time += end - start
    print(f"num_items: {num_items : <10} elapsed time (ms): {total_elapsed_time/num_trials*1000:.5f}")

print(f"[deque.popleft]")
for num_items in range(5000, 20000, 5000):
    total_elapsed_time = 0.0
    for trial in range(num_trials):
        sample_queue = deque()
        start = time()
        for i in range(num_items):
            sample_queue.append(i)
        end = time()
        total_elapsed_time += end - start
    print(f"num_items: {num_items : <10} elapsed time (ms): {total_elapsed_time/num_trials*1000:.5f}")

>>
[list.append]
num_items: 5000       elapsed time (ms): 0.51046
num_items: 10000      elapsed time (ms): 1.01092
num_items: 15000      elapsed time (ms): 1.69153
[list.pop(0)]
num_items: 5000       elapsed time (ms): 2.52228
num_items: 10000      elapsed time (ms): 9.94903
num_items: 15000      elapsed time (ms): 21.78977

[deque.append]
num_items: 5000       elapsed time (ms): 0.51045
num_items: 10000      elapsed time (ms): 1.04095
num_items: 15000      elapsed time (ms): 1.58143
[deque.popleft]
num_items: 5000       elapsed time (ms): 0.52047
num_items: 10000      elapsed time (ms): 1.06096
num_items: 15000      elapsed time (ms): 1.60145

기존의 list 구현과 달리, deque의 popleft는 매 호출이 O(N) 대신 O(1)의 시간 복잡도를 가짐을 간접적으로 확인할 수 있다 (위에선 N번 호출로 인해 결과적으로는 O(N^2) 복잡도 대신 O(N) 시간 복잡도가 된다). 기존에 list를 사용한 큐 구현을 이용하고 있었다면, 위와 같이 몇 줄의 간단한 코드 수정을 통해 소요 시간을 크게 줄일 수 있다. 

 

---

사족으로, 본인도 어디서 주워들은 대로 매번 list 자료형에서 pop(0)를 호출하는 식으로 대충 큐를 만들어 사용했는데, 최근에 시간/메모리 성능을 끌어올리는 작업을 하면서 이 도구를 새로 알게 되었다. 안타깝게도 프로그램의 주요한 오버헤드 원인이 여기에 있었진 않았지만, 그래도 이 기회에 앞으로의 불필요한 시간 지연을 방지할 수 있게 되었으니 꽤 덕을 보았다고 할 수 있다.

 

그리고 사실 파이썬은 큐를 위한 빌트인 모듈로써 queue 모듈을 따로 제공하고 있다 (파이썬 3부터 지원하는 것 같다). 개인적으로는 이 모듈의 인터페이스가 그렇게 친숙하지는 않았고 (put, get), FIFO, LIFO와 같은 구조에 따라 클래스가 처음부터 나뉘어져 있어 deque 클래스에 비해 유연성이 떨어지는 점 (사실 deque는 double-ended queue의 줄임말이며 FIFO 구조 이외에 다른 구조로도 응용할 수 있다) 때문에 본인은 deque 클래스를 주로 사용하는 편이다.

 

하지만 queue 모듈과 같이 식으로 처음부터 명확한 자료구조 타입이 고정되어 있는 편이 안전성 면에서는 더 좋은 방법일 수 있다. 따라서 이것저것 모두 활용해 보고 상황에 맞는 도구를 사용해 보는 것이 가장 좋은 방법인 것 같다. 일단은 참고자료로 남겨둔다.

 

아래는 참고할 만한 사이트들이다.

References

Collections 모듈의 deque 도큐멘테이션

https://docs.python.org/3/library/collections.html#collections.deque

Queue 모듈

https://docs.python.org/ko/3.7/library/queue.html