Skip to content

Python Deque: collections.deque를 사용한 빠른 양방향 큐

Soren Atelier
Name
Soren Atelier

Updated on

Python 리스트를 큐나 스택으로 사용하는 것은 자연스러워 보입니다 -- 왼쪽에서 pop을 시작하기 전까지는요. list.pop(0) 호출은 O(n) 연산입니다. 나머지 모든 요소가 한 위치씩 앞으로 이동해야 하기 때문입니다. 수백만 개의 항목을 처리하는 루프에서 이 숨겨진 비용은 빠른 파이프라인을 느린 것으로 바꿉니다. 같은 문제가 list.insert(0, x)에도 영향을 미치며, 이것도 O(n)입니다. 시퀀스의 양쪽 끝을 다루는 모든 작업에서 일반 리스트는 성능 함정이 됩니다.

Python의 collections.deque(양방향 큐, "덱"으로 발음)는 양쪽 끝에서 O(1) append와 pop 연산을 제공하여 이를 해결합니다. 고정 길이 블록의 이중 연결 리스트로 구현되어 인덱스 접근도 지원하면서 각 끝에서 상수 시간 성능을 제공합니다. 이 가이드는 deque에 대해 알아야 할 모든 것을 다룹니다: 생성, 핵심 연산, 제한된 큐, 스레드 안전성, 실용적인 패턴.

📚

    Deque 생성하기

    from collections import deque
 
d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])
 
letters = deque("hello")
print(letters)  # deque(['h', 'e', 'l', 'l', 'o'])
 
d = deque()
 
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)  # 오른쪽에 추가하면 가장 왼쪽 항목이 제거됨
print(d)  # deque([2, 3, 4], maxlen=3)

    핵심 연산

    Deque는 시퀀스 양쪽 끝에 대한 대칭적인 연산을 제공합니다.

    from collections import deque
 
d = deque([2, 3, 4])
 
d.append(5)
d.appendleft(1)
print(d)  # deque([1, 2, 3, 4, 5])
 
right = d.pop()
left = d.popleft()
print(right)  # 5
print(left)   # 1
 
d = deque([3, 4, 5])
d.extend([6, 7, 8])
d.extendleft([2, 1, 0])    # 주의: 역순
print(d)  # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

    extendleft는 항목을 하나씩 처리하여 각각을 위치 0에 삽입한다는 점에 유의하세요. 결과 순서는 입력 이터러블과 비교하여 역순입니다.

    기타 유용한 메서드

    from collections import deque
 
d = deque([1, 2, 3, 2, 4, 2, 5])
 
print(d.count(2))   # 3
print(d.index(3))   # 2
d.remove(2)
d.insert(1, 99)
d.reverse()
d.clear()

    rotate()를 사용한 회전

    rotate() 메서드는 deque를 n 단계 오른쪽으로 회전합니다. 음수 n은 왼쪽으로 회전합니다.

    from collections import deque
 
d = deque([1, 2, 3, 4, 5])
 
d.rotate(2)
print(d)       # deque([4, 5, 1, 2, 3])
 
d.rotate(-3)
print(d)       # deque([2, 3, 4, 5, 1])

    maxlen을 사용한 제한된 Deque

    제한된 deque는 가장 실용적인 기능 중 하나입니다. maxlen을 설정하면 용량에 도달했을 때 가장 오래된 항목을 자동으로 제거하는 고정 크기 버퍼를 만듭니다.

    슬라이딩 윈도우 / 이동 평균

    from collections import deque
 
def moving_average(data, window_size):
    """Calculate moving average using a bounded deque."""
    window = deque(maxlen=window_size)
    averages = []
    for value in data:
        window.append(value)
        if len(window) == window_size:
            averages.append(sum(window) / window_size)
    return averages
 
prices = [100, 102, 104, 103, 105, 107, 106, 108, 110, 109]
print(moving_average(prices, 3))

    파일의 끝 (마지막 N줄)

    from collections import deque
 
def tail(filename, n=10):
    """Return the last n lines of a file."""
    with open(filename) as f:
        return deque(f, maxlen=n)

    Deque를 큐(FIFO)로 사용

    from collections import deque
 
queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")
 
print(queue.popleft())    # first
print(queue.popleft())    # second
print(queue.popleft())    # third

    여기가 deque가 리스트에 비해 진정으로 빛나는 곳입니다. 리스트에서 list.pop(0)은 O(n)이지만 deque에서 popleft()는 O(1)입니다.

    Deque를 스택(LIFO)으로 사용

    from collections import deque
 
stack = deque()
stack.append("first")
stack.append("second")
stack.append("third")
 
print(stack.pop())    # third
print(stack.pop())    # second
print(stack.pop())    # first

    성능 비교: Deque vs 리스트

    연산dequelist비고
    append(x) (오른쪽)O(1)O(1) 상각둘 다 오른쪽 추가는 빠름
    appendleft(x) / insert(0, x)O(1)O(n)Deque가 압도적으로 빠름
    pop() (오른쪽)O(1)O(1) 상각둘 다 오른쪽 제거는 빠름
    popleft() / pop(0)O(1)O(n)Deque가 압도적으로 빠름
    extend(iterable)O(k)O(k) 상각k = 이터러블의 길이
    rotate(k)O(k)N/A리스트에 해당하는 것 없음
    인덱스 접근 d[i]O(n)O(1)랜덤 접근은 리스트가 우위
    len()O(1)O(1)둘 다 내부적으로 길이 추적
    in (소속 테스트)O(n)O(n)둘 다 선형 스캔 필요

    벤치마크

    from collections import deque
import time
 
def benchmark_left_operations(n):
    """Compare popleft/appendleft performance."""
    data = list(range(n))
    start = time.perf_counter()
    while data:
        data.pop(0)
    list_time = time.perf_counter() - start
 
    data = deque(range(n))
    start = time.perf_counter()
    while data:
        data.popleft()
    deque_time = time.perf_counter() - start
 
    print(f"n={n:>8,}")
    print(f"  list.pop(0):     {list_time:.4f}s")
    print(f"  deque.popleft(): {deque_time:.4f}s")
    print(f"  Speedup: {list_time / deque_time:.1f}x")
 
benchmark_left_operations(100_000)

    스레드 안전성

    Python의 deque는 스레드 안전한 append(), appendleft(), pop(), popleft() 연산을 제공합니다. 이 메서드들은 GIL로 보호되는 단일 바이트코드 명령 내에서 실행되므로 CPython에서 원자적입니다.

    블로킹 동작이 필요한 프로덕션 시스템에는 대신 queue.Queue를 사용하세요.

    실용적인 패턴

    BFS 그래프 탐색

    from collections import deque
 
def bfs(graph, start):
    """Breadth-first search using deque as queue."""
    visited = set()
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(
                neighbor for neighbor in graph[node]
                if neighbor not in visited
            )
    return order
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

    슬라이딩 윈도우 최대값

    from collections import deque
 
def sliding_window_max(nums, k):
    """Find maximum in each sliding window of size k."""
    result = []
    window = deque()
    for i, num in enumerate(nums):
        while window and window[0] < i - k + 1:
            window.popleft()
        while window and nums[window[-1]] < num:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result
 
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))
# [3, 3, 5, 5, 6, 7]

    실행 취소 기록

    제한된 deque는 가장 오래된 작업을 자동으로 잊는 실행 취소 기록으로 훌륭합니다:

    from collections import deque
 
class TextEditor:
    def __init__(self, max_undo=50):
        self.content = ""
        self._undo_stack = deque(maxlen=max_undo)
 
    def type_text(self, text):
        self._undo_stack.append(self.content)
        self.content += text
 
    def delete_last(self, n=1):
        self._undo_stack.append(self.content)
        self.content = self.content[:-n]
 
    def undo(self):
        if self._undo_stack:
            self.content = self._undo_stack.pop()
 
editor = TextEditor(max_undo=10)
editor.type_text("Hello")
editor.type_text(" World")
print(editor.content)   # Hello World
editor.undo()
print(editor.content)   # Hello

    Jupyter에서 데이터 구조 성능 테스트

    deque와 리스트를 벤치마킹하거나 특정 워크로드에 맞게 maxlen을 조정할 때 인터랙티브 노트북은 매우 유용합니다. RunCell (opens in a new tab)은 데이터 구조 연산 프로파일링, 성능 차이 시각화, 최적화를 위한 지능적인 제안을 받을 수 있는 AI 기반 Jupyter 환경을 제공합니다.

    FAQ

    Python에서 deque란 무엇인가요?

    deque(양방향 큐)는 Python collections 모듈의 데이터 구조로, 양쪽 끝에서 O(1) append 및 pop 연산을 지원합니다. 앞쪽에서의 삽입이나 제거에 O(n) 시간이 걸리는 리스트와 달리, deque는 어느 쪽 끝에서든 상수 시간 성능을 제공합니다.

    deque와 list 중 언제 어떤 것을 사용해야 하나요?

    시퀀스의 양쪽 끝에서 빠른 삽입이나 제거가 필요할 때 deque를 사용하세요. 예를 들어 큐(FIFO) 구현, 슬라이딩 윈도우 유지, BFS 탐색 수행 등입니다. 인덱스에 의한 빠른 랜덤 접근이 필요하면 list를 사용하세요 (리스트는 O(1), deque는 O(n)).

    Python deque는 스레드 안전한가요?

    네, append(), appendleft(), pop(), popleft() 메서드는 CPython에서 스레드 안전합니다. GIL로 보호되는 단일 바이트코드 명령 내에서 완료되므로 이 연산들은 원자적입니다. 하지만 복합 연산은 원자적이지 않으므로, 블로킹 의미론이 필요한 생산자-소비자 패턴에는 queue.Queue를 사용하세요.

    deque에서 maxlen은 무엇을 하나요?

    maxlen 매개변수는 고정 최대 크기의 제한된 deque를 생성합니다. deque가 가득 찬 상태에서 새 항목이 추가되면 반대쪽의 항목이 자동으로 삭제됩니다. 롤링 윈도우, 최근 활동 로그, 실행 취소 기록 구현에 유용합니다.

    deque와 queue.Queue의 비교는?

    collections.deque는 속도를 위해 설계되었습니다. queue.Queue는 내부적으로 deque를 감싸지만 잠금과 조건 변수 같은 스레드 동기화 프리미티브를 추가합니다. 단일 스레드 코드에는 deque를 사용하세요. 멀티스레드 생산자-소비자 시나리오에서 블로킹 get()과 put() 연산이 필요하면 queue.Queue를 사용하세요.

    결론

    Python의 collections.deque는 표준 라이브러리에서 가장 유용하지만 과소평가된 데이터 구조 중 하나입니다. 리스트의 왼쪽 연산에 대한 O(n) 페널티를 제거하고, maxlen으로 내장 제한 버퍼링을 제공하며, 스레드 안전한 원자적 연산을 제공하고, 큐, 스택, 슬라이딩 윈도우, 그래프 탐색 알고리즘의 기반이 됩니다.

    핵심 결정은 명확합니다: 코드가 시퀀스의 양쪽 끝을 다루면 deque를 사용하세요. 인덱스에 의한 빠른 랜덤 접근이 필요하면 list를 사용하세요. 대부분의 큐와 스택 패턴에서는 deque가 기본 선택이어야 합니다.

    📚