파이썬 알고리즘 문제를 풀던 중, 큐를 사용해야 하는 문제를 풀게 되었다.
for 루프를 돌며 자료를 추가/삭제하는 문제였는데 queue를 사용하니 모두 시간이 초과 되었다.
시도했던 방법은 다음과 같다.
1) list를 큐로 사용 - 시간 초과
2) Queue 클래스 사용 - 시간 초과
답답해서 구글링을 하다보니 queue만 사용해도 충분한 문제인데도 deque를 사용해서 해결하는 경우를 발견하였다.
결론 부터 말하자면 deque가 가장 빠르다 아래에 비교한 내용을 정리하였다.
1) list 를 통한 queue 구현
파이썬의 list는 random access에 최적화된 자료 구조이기 때문에 pop(0)또는 insert(0, x)는 성능이 좋지 않은 연산이다.
이 두 연산은 시간 복잡도는 O(N)이기에 데이터의 개수가 많아질 수록 느려진다.
느려지는 이유는 다음과 같다.
- 첫 번째 데이터를 제거한 후에는 그 뒤에 있는 모든 데이터를 앞으로 한 칸식 당겨줘야 한다.
- 맨 앞에서 데이터를 삽입하려면 그 전에 모든 데이터를 뒤로 한 칸씩 밀어줘야 한다.
2) queue 모듈의 Queue 클래스
주로 멀티 쓰레드 환경에서 사용되며, 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다. 그리고 deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리된다.
Queue의 성능은 deque와 마찬가지로 데이터 추가/삭제는 O(1), 데이터 접근은 O(N)의 시간 복잡도를 가진다.
3) deque
deque는 list에는 없는 popleft()라는 메서드를 제공하는데, 이 메서드를 사용하면 첫 번째 데이터를 제거할 수 있다.
데이터의 흐름은 list 객체의 pop(0) 메서드를 사용할 때 처럼 뒤에서 앞으로 흐르게 된다.
deque는 appendleft(x)라는 메서드도 제공데, 이 메서드를 사용하면 데이터를 맨 앞에서 삽입할 수 있다. 이 경우, 데이터의 흐름은 list 객체의 insert(0, x) 메서드를 사용할 때 처럼 앞에서 뒤로 흐르게 된다.
deque의 popleft()와 appendleft(x)메서드는 모두 O(1)의 시간 복잡도를 가지기 때문에, 위에서 살펴본 list의 pop(0)와 insert(0, x) 대비 성능 상에 큰 이점이 있다.
하지만 deque도 단점이 있다. 바로 random access의 시간 복잡도가 O(N)이라는 것이다.
내부적으로 linked list를 사용하고 있기 때문에 i 번째 데이터에 접근하려면 맨 앞/뒤부터 i 번 순회가 필요하다.
