오랜만에 백준에서 문제를 풀고있던 중 덱 문제를 발견했다. 개인적으로 좋은 문제는 아니라고 보고 난이도는 크게 어렵지 않았다.
Python에는 Collections 모듈엔 deque가 있다. 그래서 deque를 이용해 문제를 풀어나가면 쉽게 풀 수 있다. 다른사람들의 풀이를 보던 중, 대부분의 사람들이 list를 이용해 deque처럼 작동하게 하여 문제를 푼걸 보고 난 deque와 list중 둘 중 누가 빠른지 궁금해졌다.
Deque란 ?
덱이라고 읽는다는데 나는 디큐라고 발음할 줄 알았다.
Double-ended-queue의 약어로 양 방향으로 데이터를 집어넣을수도 뺄수도있는 구조를 말하는데, 사실 python의 list도 둘다 가능하다.
그럼 왜 Deque를 쓸까?
비교해보면 Deque는 데이터를 왼쪽에서 넣을 수 있는 함수를 제공한다는것 이외에는 maxlen과 rotate함수만이 존재한다.
maxlen
- Maximum size of a deque or None if unbounded.
rotate
- Rotate the deque n steps to the right. If n is negative, rotate to the left.
https://docs.python.org/ko/3.8/library/collections.html#collections.deque
list로도 다 구현이 가능한데?
appendleft는 insert(0, data)와 같고, popleft는 pop(0)과 같다. 과연 완전 똑같다고 할 수 있을까?
속도 비교
📢 데이터는 100만부터 0까지 거꾸로 저장되거나 되어있다.
pop
여러번 측정 결과 Deque가 약간 더 빠르다.
popleft
Deque가 압도적으로 빠르다.
list의 경우 pop(0)으로 구현하였는데, pop()은 O(1)이지만, pop(0)은 O(n)이다. 그래서 100만개의 데이터를 계속해서 빼낼 경우 Deque에 비해 압도적으로 느려지게 되는 것이다.
append
여러번 측정 결과 Deque가 약간 더 빠르다.
appendleft
Deque가 압도적으로 빠르다. (뭐이리 느려 ㅡㅡ)
list의 경우 insert(0, data)으로 구현하였다. 이 경우에도 O(n)의 시간이 걸리게 되고 100만개의 데이터를 계속해서 삽입할 경우 Deque에 비해 압도적으로 느려지게 되는 것이다.
결론
예상대로 left관련 함수는 deque가 훨씬 빨랐다. 심지어 오른쪽에서 데이터를 넣고 빼는 것 조차도 미세하게나마 더 빨랐다. 백준의 덱 문제는 좋은 문제가 아니라고 돌려말했지만 사실 쓰레기같은 문제다. 시간 제한이 0.5초라서 Deque를 상속하는 class를 만들어서 풀었는데 시간 초과로 실패했다. 그 이유는 입력을 input 함수로 받아서 인데, 똑같은 소스에 입력만 sys.stdin.readline()로 받으면 성공한다. 게다가 앞서 설명한것처럼 list를 이용해 풀어도 성공한다. input 함수가 보다 느린건 알고 있었지만 이런 문제는 좀 아니라고 생각한다.
