사용자 도구

사이트 도구


ps:monotonic_priority_queue

Monotonic Priority Queue

  • 우선순위큐에서, extract-min 연산으로 추출되는 값이 항상 모노토닉할 때 사용할 수 있는 구조. 일반적인 우선순위큐보다 쓰는 데에 제약이 걸린 대신에 좀더 빠르게 동작하도록 구현할 수 있다.
  • extract-min 연산으로 추출되는 값이 항상 모노토닉하다는 조건이 성립하는 대표적인 활용 예제는 다익스트라 알고리즘이다.
  • Monotonic Priority Queue에 해당되는 데이터구조로는 Radix Heap 이 있다.

Radix Heap

  • Radix heap 를 참고
  • 모든 키가 정수여야 한다는 조건이 필요하다
  • 시간 복잡도는 버켓의 갯수 B에 영향을 받는다. B는 O(logC) 이고, C는 키의 최댓값과 최솟값의 차이이다. 32bit 정수를 대상으로 동작한다면 최대 32라고 봐도 된다.
  • 위키피디아에 의하면 insert는 O(B), extract-min은 amortized O(1), decrease-key도 amortized O(1)이라고 한다. 이대로 다익스트라 알고리즘에 적용한다면 시간복잡도가 O(|V|+|E|)가 될 것이다.
  • 하지만 보통 decrease-key 를 구현하지 않는 것 같다 (참고 구현체: https://github.com/iwiwi/radix-heap). 그렇게 insert와 extract_min으로만 다익스트라 알고리즘을 구현한다면 O(|E|*B)가 될텐데, 이것은 그냥 바이너리 힙을 썼을때의 O(|E|log|V|)보다 빠르기 힘들다.
    • 그럼에도 불구하고, https://github.com/iwiwi/radix-heap 에서는 실용적인 문제들에 대해서 std::priority_queue 보다 약 2배 빨랐다고 한다
    • https://blog.naver.com/jinhan814/222507238041 에서는 BOJ 문제에 제출했을때 시간 차이가 거의 없었다고 한다.
    • 여기서 유추할때, 파이썬에서 이걸 구현해봤자 PS용도에서 heapq보다 빨라질 가능성은 거의 없다고 생각된다. 구현도 안해보기로 했다.

토론

jinhan814, 2022/04/02 17:03
크누스 최적화 글 보다가 여기까지 왔는데 예상치도 못한 곳에서 제 링크가 나와서 놀랐네요 ㅋㅋㅋㅋ 글 정리해주신 거 잘 읽고 있습니다 ㅎㅎ 감사합니다
Teferi, 2022/04/03 13:17
평소에 진한님 블로그에서 많이 배우고 있습니다. 방문해서 댓글 남겨주셔서 영광입니다ㅎㅎ
댓글을 입력하세요:
O O K E F
 
ps/monotonic_priority_queue.txt · 마지막으로 수정됨: 2022/04/03 13:13 저자 teferi