[Python] 파이썬 Queue와 deque 속도 /

새벽 3시까지 1시간넘게 이거 하나로 고민하다가 저 같이 고생하지 않으셨음 하는 바람에 글을 씁니다.. 😥

 

 

파이썬 큐

 

저는 주로 파이썬으로 코딩테스트를 풉니다. 코테에서는 큐, 스택 모두 많이 쓰이죠. 파이썬에서 지원하는 큐 자료구조에는 Queue 가 있고, deque 라는 친구가 있죠. Queue는 단순히 put과 get으로 넣고, 가장 먼저 들어왔던 놈을 빼주는 기능만을 지원하는 반면에 deque 는 스택처럼 FIFO, 큐처럼 LILO 를 모두 구현할 수 있는 유용한 친구입니다.

 

여러분은 두 모듈중에 어떤게 빠른 것 같으시나요?

저는 당연히 좀더 복합적인 기능을 가진 deque 가 더 느릴줄 알았습니다...만!!!!!!!

 

✨ 사실은 deque 가 훨씬 빠릅니다, 코테에선 deque를 씁시다! ✨

 

www.acmicpc.net/problem/14502  

14502번: 연구소

이 문제를 브루트포스로 구현한 후, 왜 안되지 싶어서 이것저것 만져보다가 겨우 알게되었네요ㅜ

 

 

결론

 

검색을 통해 알아보니 deque 는 각 명령을 O(1)으로 지원하는데에 반해, Queue 모듈은 멀티쓰레드 환경을 지원하기 때문에 더 느리다고 하네요.. 파이썬 자체 프로그래밍을 해본적이 없다보니 몰랐네요😫 Queue 모듈을 쓸 때 , IDE에서 put_nowait, get_nowait 같은 게 보이던게 다 이런 이유였던 것 같습니다. 

 

참고로 한가지 더 팁을 드리자면, copy.deepcopy() 또한 매우 느린 작업입니다. 이 부분이 포함된 코드가 시간초과가 뜬다면, 다른 알고리즘으로 구현하셔야합니다. 🙂