데크(Deque)
큐가 양쪽으로 연결된 형태. 따라서 양쪽에서 삽입과 삭제가 가능하다. 이미 파이썬에는 collections모듈에 deque가 구현되어 있다. c/c++로 구현되어 있으며 양쪽에서 삽입과 삭제가 가능해야 하므로 더블리 링크드 리스트로 만들어져 있다. 이로 인해 양쪽에서 삽입과 삭제가 O(1)의 시간이 걸리므로 코딩테스트 파이썬에서 스택이나 큐를 이용할 때 이 데크를 사용하기도 한다.
커스텀 데크 구현
파이썬으로 데크를 구현해 보았다.
from typing import Iterable, Optional
class Node:
"""더블리 링크드 리스트의 노드 클래스"""
def __init__(self, data) -> None:
self.data = data
self.prev = None
self.next = None
def __repr__(self) -> str:
return str(self.data)
class CustomDeque:
"""커스텀 데크 구현 클래스"""
def __init__(self, arr: Optional[Iterable] = None) -> None:
self.head = None
self.tail = None
self.size = 0
# 인스턴스 생성 시 arr가 들어올 경우
if arr:
self.extend(arr)
def append(self, __x) -> None:
"""추가 메소드"""
new_node = Node(__x)
if self.size == 0:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.size += 1
def appendleft(self, __x) -> None:
"""앞쪽 추가 메소드"""
new_node = Node(__x)
if self.size == 0:
self.head = new_node
self.tail = new_node
else:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
self.size += 1
def clear(self) -> None:
"""요소 일괄 삭제 메소드"""
# 기존 노드들간에 닫힌순환참조 발생 -> GC에서 알아서 노드들 메모리에서 제거
self.head = None
self.tail = None
def pop(self):
"""삭제 메소드"""
if self.size == 0:
raise IndexError("데크가 비어있습니다.")
__x = self.tail.data
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.clear()
self.size -= 1
return __x
def popleft(self):
"""앞쪽 삭제 메소드"""
if self.size == 0:
raise IndexError("데크가 비어있습니다.")
__x = self.head.data
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.clear()
self.size -= 1
return __x
def extend(self, arr: Iterable):
"""이터러블한 값 삽입 메소드"""
if not isinstance(arr, Iterable):
raise ValueError("이터러블한 값만 입력할 수 있습니다.")
for i in arr:
self.append(i)
def extendleft(self, arr: Iterable):
"""이터러블한 값 앞쪽 삽입 메소드"""
if not isinstance(arr, Iterable):
raise ValueError("이터러블한 값만 입력할 수 있습니다.")
for i in arr:
self.appendleft(i)
def count(self):
"""데크 사이즈 리턴 메소드"""
return self.size
def index(self, __i: int):
"""인덱스로 노드 찾기 메소드"""
if __i >= self.size:
raise IndexError("데크의 요소보다 더 큰 인덱스를 입력했습니다.")
iterator = self.head
for _ in range(__i):
iterator = iterator.next
return iterator
def insert(self, __i: int, __x) -> None:
"""삽입 메소드"""
if __i >= self.size:
raise IndexError("데크의 요소보다 더 큰 인덱스를 입력했습니다.")
if __i == 0:
self.appendleft(__x)
return
new_node = Node(__x)
node_existed = self.index(__i)
new_node.next = node_existed
new_node.prev = node_existed.prev
if node_existed.prev:
node_existed.prev.next = new_node
node_existed.prev = new_node
self.size += 1
def __repr__(self) -> str:
list_for_return = []
iterator = self.head
while iterator:
list_for_return.append(str(iterator.data))
iterator = iterator.next
return "deque([" + ", ".join(list_for_return) + "])"
코드 리뷰
노드 클래스
class Node:
"""더블리 링크드 리스트의 노드 클래스"""
def __init__(self, data) -> None:
self.data = data
self.prev = None
self.next = None
def __repr__(self) -> str:
return str(self.data)
파이썬의 deque는 내부적으로 더블리 링크드 리스트와 추가적인 알고리즘으로 만들어져 있다. 따라서 노드 클래스는 더블리 링크드 리스트 노드로 만들어 주었다.
커스텀 데크 클래스
from typing import Iterable, Optional
class CustomDeque:
"""커스텀 데크 구현 클래스"""
def __init__(self, arr: Optional[Iterable] = None) -> None:
self.head = None
self.tail = None
self.size = 0
# 인스턴스 생성 시 arr가 들어올 경우
if arr:
self.extend(arr)
더블리 링크드 리스트로 구현하기 위해 __init__ 매직 메소드에 head와 tail 그리고 구현과 카운팅을 편하게 해줄 수 있는 size 속성을 만들어 주었다. 파이썬 데크에서 인스턴스 선언과 동시에 파라미터에 이터러블한 객체를 넘겨줘도 되므로 그 부분은 아래 if arr를 통해 구현해 주었다.
이때 타입 힌트를 위해 typing 모듈의 Iterable, Optional 함수를 각각 임포트 해주었다. 옵셔널 파라미터에는 다음과 같은 방식으로 타입 힌트를 주어야 한다.
추가 메소드
def append(self, __x) -> None:
"""추가 메소드"""
new_node = Node(__x)
if self.size == 0:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.size += 1
def appendleft(self, __x) -> None:
"""앞쪽 추가 메소드"""
new_node = Node(__x)
if self.size == 0:
self.head = new_node
self.tail = new_node
else:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
self.size += 1
더블리 링크드 리스트로 구현했기 때문에 앞뒤에 노드들을 추가할 수 있다. 각각 head와 tail의 레퍼런스를 이용해 노드를 연결해주고 size를 카운트해준다.
요소 일괄 삭제 메소드
def clear(self) -> None:
"""요소 일괄 삭제 메소드"""
# 기존 노드들간에 닫힌순환참조 발생 -> GC에서 알아서 노드들 메모리에서 제거
self.head = None
self.tail = None
요소를 한번에 삭제할 때 쓰이는 메소드다. head와 tail을 둘다 None으로 설정해주면 기존의 노드들 사이의 레퍼런스는 유지되겠지만 강한 참조 없이 닫힌순환참조가 발생하므로 파이썬의 가비지 컬렉션에 의해 노드가 메모리에서 제거된다.
🔍 가비지 컬렉션 작동 확인
deque_instance = CustomDeque()
deque_instance.append(1)
deque_instance.append(2)
deque_instance.append(3)
deque_instance.append(1000)
deque_instance.append(2000)
print("clear 이전:")
print(sum(1 for obj in gc.get_objects() if isinstance(obj, Node)))
deque_instance.clear()
gc.collect() # 가비지 컬렉션 수동 실행
print("\nclear 후:")
print(sum(1 for obj in gc.get_objects() if isinstance(obj, Node)))clear 이전:
5
clear 후:
0
위와 같이 인스턴스에 5개의 노드를 담은 뒤 gc가 추적하고 있는 객체 중 Node클래스의 인스턴스를 찾았을 때 5개가 확인되었다. clear메소드를 실행하고 나서는 0이 된 것을 볼 수 있다.
수동으로 실행하지 않는다면 가비지 컬렉션의 알고리즘을 통해 세대가 넘어가면서 자연스럽게 메모리에서 제거될 것이다.
삭제 메소드
def pop(self):
"""삭제 메소드"""
if self.size == 0:
raise IndexError("데크가 비어있습니다.")
__x = self.tail.data
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.clear()
self.size -= 1
return __x
def popleft(self):
"""앞쪽 삭제 메소드"""
if self.size == 0:
raise IndexError("데크가 비어있습니다.")
__x = self.head.data
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.clear()
self.size -= 1
return __x
pop메소드와 popleft메소드를 구현할 때는 데크가 비어있는지 아닌지 확인이 필요하다. 이를 위해서 size의 크기를 계속해서 카운팅하고 있었고, 이를 통해 IndexError를 raise했다. size 속성이 없다면 self.head == None 혹은 self.tail == None을 이용해 데크 요소의 존재 유무를 알 수 있다.
각 메소드의 구현에서 head를 각각 기준 노드의 앞 혹은 뒤로 옮긴 뒤 그 노드를 기준으로 연결을 끊어준다.
마지막으로 size를 -1해주면 메소드의 구현이 완성된다.
다중값 삽입 메소드
def extend(self, arr: Iterable):
"""이터러블한 값 삽입 메소드"""
if not isinstance(arr, Iterable):
raise ValueError("이터러블한 값만 입력할 수 있습니다.")
for i in arr:
self.append(i)
def extendleft(self, arr: Iterable):
"""이터러블한 값 앞쪽 삽입 메소드"""
if not isinstance(arr, Iterable):
raise ValueError("이터러블한 값만 입력할 수 있습니다.")
for i in arr:
self.appendleft(i)
파이썬의 deque에서도 같은 메소드가 있다. 간단하게 이터러블한 arr객체만 받도록 하고 반복적으로 append메소드를 실행해 각 노드들을 추가해 주었다.
extendleft의 경우에 파이썬의 deque에서도 마찬가지로 기존의 왼쪽값이 반대로 하나씩 추가되므로 같은 방식으로 구현해 주었다.
인덱스 메소드
def index(self, __i: int):
"""인덱스로 노드 찾기 메소드"""
if __i >= self.size:
raise IndexError("데크의 요소보다 더 큰 인덱스를 입력했습니다.")
iterator = self.head
for _ in range(__i):
iterator = iterator.next
return iterator
인덱스를 이용해 노드를 리턴하는 메소드다. 이때 size 속성을 통해 예외 처리를 좀 더 간편하게 줄 수 있다. 나머지는 iterator를 통해 하나씩 순회하면서 해당되는 노드를 찾으면 노드를 리턴한다. 이 때 노드에 __repr__매직 메소드를 구현해놓았으므로 print()로 출력하면 해당 data가 출력된다.
삽입 메소드
def insert(self, __i: int, __x) -> None:
"""삽입 메소드"""
if __i >= self.size:
raise IndexError("데크의 요소보다 더 큰 인덱스를 입력했습니다.")
if __i == 0:
self.appendleft(__x)
return
new_node = Node(__x)
node_existed = self.index(__i)
new_node.next = node_existed
new_node.prev = node_existed.prev
if node_existed.prev:
node_existed.prev.next = new_node
node_existed.prev = new_node
self.size += 1
삽입 메소드도 마찬가지로 인덱스 범위에 대한 예외 처리를 해주고 인덱스가 0일 때와 아닐 때를 구분해서 구현해 주었다. 더블리 링크드 리스트로 구현되어 있으므로 그 방식으로 새로운 노드를 서로 연결해주기만 하면 된다.
테스트
deque_instance = CustomDeque()
deque_instance.append(1)
deque_instance.append(2)
deque_instance.append(3)
deque_instance.appendleft(1000)
deque_instance.appendleft(2000)
print(deque_instance)deque([2000, 1000, 1, 2, 3])
deque_instance.extend([10, 20, 30])
print(deque_instance)deque([2000, 1000, 1, 2, 3, 10, 20, 30])
print(deque_instance.pop())
print(deque_instance.pop())
print(deque_instance.popleft())
print(deque_instance.popleft())
print(deque_instance)30
20
2000
1000
deque([1, 2, 3, 10])
파이썬 deque vs 커스텀 deque
append를 10000번 실행하는 데 걸리는 시간을 1000번 반복해서 비교했다. 이건 챗지피티한테 코드를 주고 부탁했다.
import timeit
# 사용자 정의 데크를 위한 세팅 코드
setup_custom = """
from __main__ import CustomDeque
custom_deque = CustomDeque()
"""
# 내장 데크를 위한 세팅 코드
setup_python = """
from collections import deque
python_deque = deque()
"""
# 사용자 정의 데크에 10000개의 원소 추가
stmt_custom_append = """
for i in range(10000):
custom_deque.append(i)
"""
# 내장 데크에 10000개의 원소 추가
stmt_python_append = """
for i in range(10000):
python_deque.append(i)
"""
time_custom = timeit.timeit(stmt=stmt_custom_append,
setup=setup_custom, number=1000)
time_python = timeit.timeit(stmt=stmt_python_append,
setup=setup_python, number=1000)
print(f"Custom Deque append time: {time_custom}")
print(f"Python Deque append time: {time_python}")Custom Deque append time: 3.6213718
Python Deque append time: 0.34810739999999996
잘 만들어져 있는 모듈을 쓰도록 하자.
'프로그래밍 > Computer Science' 카테고리의 다른 글
| [Data Structure] Linear - (6) Queue (0) | 2023.09.13 |
|---|---|
| [Data Structure] Linear - (5) Stack (0) | 2023.09.13 |
| [Data Structure] Linear - (3) Linked List - Circular Linked List (0) | 2023.09.11 |
| [Data Structure] Linear - (2) Linked List - Doubly Linked List (0) | 2023.09.11 |
| [Data Structure] Linear - (2) Linked List - Singly Linked List (0) | 2023.08.16 |