[python] Queue vs deque

때는 백준 2573번 문제인 "빙산"을 풀고있을 때였습니다.
(문제링크: https://www.acmicpc.net/problem/2573)

해당 문제는 결국 풀긴 했지만 수차례 시간초과를 받으며 정신이 아찔해졌다.

사실 다른 사람들의 풀이를 보면서 내가 짠 알고리즘과 같거나 더 비효율적이라는 생각을 했다. 그런데 그 사람은 통과를 했고 나는 왜인지 시간초과가 나니까 화가 슬슬 나기 시작했다.

그러다가
https://programming119.tistory.com/184
해당 블로그 글에서 답을 찾을 수 있었다.

핵심은, Queue 모듈은 멀티쓰레드 환경을 지원하기 때문에 deque보다 느리다.
(생각해보니, Queue 모듈 속 기능들을 멀티쓰레딩 할 때 사용했던 기억이 났다...)

사실 Queue나 deque나 맨 뒤에서 하나를 pop하는데 큰 시간 차이가 나지 않을 것이라 생각을 했다. 어차피 둘 다 O(1)의 복잡도를 가지기 때문이다. 그러나 python 공식 문서에서도 확인할 수 있듯, Queue모듈은 멀티쓰레드를 지원하기 때문에 deque 보다 그냥 자체적으로 느릴 수 밖에 없는 것 같다.

• 참고
  속도는 deque > list >queue 순으로 빠르다.
  따라서 코테용으로 큐를 사용해야 한다면 무조건 deque를 사용하자

• 주의
  deque가 만능은 아닌게, 중간에 있는 값을 인덱싱하여 뽑아낼 수 있다고 시간복잡도가 O(1)이 아님.
  중간에 있는 인덱스의 접근 연산은 O(N)이다.
  따라서 빠른 인덱스 접근을 원한다면 list를 사용하자
  참고: https://velog.io/@mindol/%ED%8C%8C%EC%9D%B4%EC%8D%AC-deque%EC%9D%98-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%A0%91%EA%B7%BC-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84