소개

이 기사는 주로 경기 프로그래밍의 이야기입니다.

Python에서 스택과 큐를 구현하는 방법은 여러 가지가 있습니다.

스택(stack)

list 사용하기 ( append() , pop() )

collections.deque 사용 ( append() , pop() )

큐(queue)

list 사용하기 ( append() , pop(0) )

collections.deque 사용 (append(), popleft())

queue.Queue 사용 ( put() , get() )

그런데, 이중에서 도대체 어느 것을 사용하는 것이 최적일까요.
이번은 그것을 속도면에 주목해 조사합니다.

측정 방법

각 데이터 구조에 대해 요소 추가 및 검색을 10회, 100회, 1000회, 10000회, 100000회 수행합니다.

모든 코드는 다음 import 부분을 생략합니다.

import 부분

from collections import deque
from queue import Queue
import time

스택

list 사용

# stack(list)
stack_list_append = []
stack_list_pop = []
for i in range(1, 6):
    start = time.time()

    stack_list = []
    for j in range(10 ** i):
        stack_list.append(j)

    stack_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_list.pop()

    stack_list_pop.append(time.time() - start)

deque 사용

# stack(deque)
stack_deque_append = []
stack_deque_pop = []
for i in range(1, 6):
    start = time.time()

    stack_deque = deque([])
    for j in range(10 ** i):
        stack_deque.append(j)

    stack_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_deque.pop()

    stack_deque_pop.append(time.time() - start)

큐

list 사용

# queue(list)
queue_list_append = []
queue_list_pop = []
for i in range(1, 6):
    start = time.time()

    queue_list = []
    for j in range(10 ** i):
        queue_list.append(j)

    queue_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_list.pop(0)

    queue_list_pop.append(time.time() - start)

deque 사용

# queue(deque)
queue_deque_append = []
queue_deque_pop = []
for i in range(1, 6):
    start = time.time()

    queue_deque = deque([])
    for j in range(10 ** i):
        queue_deque.append(j)

    queue_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_deque.popleft()

    queue_deque_pop.append(time.time() - start)

Queue 사용

# queue(Queue)
queue_Queue_append = []
queue_Queue_pop = []

for i in range(1, 6):
    start = time.time()

    queue_Queue = Queue()
    for j in range(10 ** i):
        queue_Queue.put(j)

    queue_Queue_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_Queue.get()

    queue_Queue_pop.append(time.time() - start)

측정 결과

측정 결과를 그래프로 한 결과, 다음과 같이 되었습니다.



왼쪽 상단에서 순서대로 살펴 보겠습니다.

스택 결과

요소 추가

왼쪽 상단의 그래프입니다.

약간 deque 쪽이 빠르지만 거의 같습니다.

요소 꺼내기

오른쪽 상단의 그래프입니다.

이쪽도 약간 deque 쪽이 빠릅니다만, 거의 같습니다.

대기열 결과

요소 추가

왼쪽 하단의 그래프입니다.

요소 수가 많아지면 Queue가 다른 것보다 10배 이상 느립니다.

요소 꺼내기

오른쪽 하단 그래프입니다.

Queue는 요소를 추가할 때와 동일하지만 list가 분명히 쉽습니다. 가장 빠른 deque와 비교하면 100배 이상 느려지고 있습니다.

결론

스택과 큐 모두 collections.deque를 사용하는 것이 가장 좋습니다.

모처럼이므로, 간단한 사용법도 써 둡니다.

스택

from collections import deque

s = deque([])
s.append(1)  # [1]
s.append(2)  # [1, 2]
s.append(3)  # [1, 2, 3]
s.pop()      # 一番上から取り除く [1, 2, 3] -> [1, 2]
s.pop()      # [1, 2] -> [1]
s.pop()      # [1] -> []

큐

스택에서는 제거할 때 pop이었던 것이, 큐라고 popleft 가 되어 있을 뿐입니다.

from collections import deque

q = deque([])
q.append(1)  # [1]
q.append(2)  # [1, 2]
q.append(3)  # [1, 2, 3]
q.popleft()  # 一番下から取り除く [1, 2, 3] -> [2, 3]
q.popleft()  # [2, 3] -> [3]
q.popleft()  # [3] -> []