Implementing Mutable PriorityQueue
내비게이션 경로탐색 알고리즘으로 가장 잘 알려져 있고 많이 이용하는 알고리즘이 Dijkstra 알고리즘이다. 알고리즘 수행 결과로 만들어진 경로는 최단거리를 제외하면 빠른경로/운전하기 편한 경로와 같이 정성적으로 판단하는 부분이 많다. 이와 같은 척도를 제외하면 경로탐색 엔진의 품질을 측정하는 중요한 척도는 경로탐색 과정에서 소요되는 시간일 것이다. Dijkstra 알고리즘을 이용하면 최적의 경로를 찾긴 하지만 탐색시간이라는 비용을 지불해야 한다. 내비게이션 품질에서 탐색시간이라는 비용을 줄이기 위해 A*와 같이 탐색공간(Search Space)을 줄이는 Heuristic 기법들을 많이 활용하고 있으며 최근에는 개념을 바꿔 전처리(Preprocessing) 단계를 이용하여 좀 더 교통공학적으로 접근하여 탐색속도를 개선하려는 시도들을 많이 하고 있다.
이 글에서는 이런 접근도 중요하지만 Dijkstra 알고리즘 내에서 활용되는 주요 자료구조인 Queue를 개선함으로써 탐색 속도를 줄이는 방법에대해 이야기 해 보고자 한다.
본 내용을 이어가기 전에 먼저 Dijkstra 알고리즘에서 Queue가 왜 중요하고 탐색시간과 어떤 관련이 있는지 간락하게 알아보자.
Dijkstra 알고리즘에서 Queue의 중요성
Dijkstra 알고리즘은 도착가능한 모든 지점에 대해 출발지로부터 최단경로를 만들어 낸다. 이때 알고리즘 내부적으로 보면 다음 단계에서 방문할 후보 지점들을 모두 가져온 다음 이들 지점 중에 가장 빨리 도달할 수 있는 지점들을 하나씩 선택해가며 출발지로부터의 거리를 비교하는 과정을 반복해 나간다. 이때 중요한 것은 가져온 지점들 중 가장 빨리 도달할 수 있는 지점을 찾아내는 것이며 만약 이 과정을 비효율적으로 구현할 경우 전체 탐색 시간을 잡아먹을 수 있다. 예를 들어 서울역에서 출발하여 부산역에 도착하는 최단경로 탐색 과정을 생각해보면 알고리즘 동작중에 약 1,000개에서 2,000개의 후보지점을 가져오고 이들 중 가장 빨리 도달할 수 있는 지점을 찾아야 한다. 이 과정을 약 3,000,000 번을 수행해야 한다고 하면 가장 빨리 도달할 수 있는 후보지점을 찾기 위해 정렬하는 연산이 알고리즘 속도에 지대한 영향을 끼치게 됨을 알 수 있다. 이를 위해 일반적으로 Dijkstra 알고리즘 구현체는 정렬 기능을 내포하는 PriorityQueue라는 Queue 자료구조로 주로 활용한다. 즉, 후보지점을 Queue에 enqueue 한 후 dequeue되는 후보지점은 내부적으로 정렬과정을 거쳐 가장 빨리 도달할 수 있는 지점이 뽑아져 나오게 되는 것이다.
PriorityQueue는 후보지점이 enqueue 될 때 효율적 정렬하기 위해 Priority Heap을 이용한다. 즉, Queue내의 항목들에 대해 Binary Tree를 이용한 Heap Sort를 적용한다. 이를 이용하면 일반적으로 
이 경우 정렬을 위해 이용할 수 있는 방법으로는
- Queue내의 변경된 지점을 remove()한 다음 다시 offer() 하는 방법
- PriorityQueue 내의 지점이 변경되면 기존의 객체를 버리고 새로운 PriorityQueue 객체를 만드는 방법
을 생각해 볼 수 있다. 이 방법을 활용하면 원하는 결과를 얻을 수는 있지만 이론적으로 볼 때 비용이 많이 발생하는 연산이라 할 수 있다. 1번의 경우 remove 연산시 내부적으로 Binary Tree의 Heap을 재구성하기 위해 swap연산이 많이 발생하며 이후 offer연산에서는 정렬을 다시 수행해야 한다. 2번의 경우는 PriorityQueue객체를 새로 만들어야 하므로 컴퓨터 입장에서 보면 메모리 확보라는 비교적 비싼 연산을 수행해야 하며 기존에 Queue가 가지고 있던 모든 지점들을 새로운 배열(queue)에 복사하는 과정도 수행되어야 한다. 또한 내부적으로는 Heap을 다시 구성해야 하는 부담까지 포함하고 있다.
만약 Queue내부에 있는 후보 지점에서 값(cost)이 변경될 경우 Heap 의 정렬만 변경할 수 있다면 앞에서 언급했던 비효율적인 부분이 사라지게 되므로 탐색속도가 개선될 수 있다는 결론에 이를 수 있다. 알고리즘 구현시 개발자들이 이런 문제점을 인지했었다면 해결을 위한 다양한 시도들이 있었을테고 이와 관련된 예제들이 인터넷에 있을 법 한데 아무리 찾아봐도 찾을 수가 없다. 하지만 실마리를 제공하는 논문과 PriorityQueue.Java 소스코드, 유용한 인터넷 자료를 바탕으로 Mutable PriorityQueue(가칭)을 설계할 수 있었고 그 구현과정을 기록으로 남겨본다.
Heapsort overview
Java에서 제공되는 PriorityQueue.java는 내부적으로 Heapsort를 활용하며 Complete Binary-Tree(완전이진트리)를 기반으로 동작하므로 먼저 Complete Binary-Tree의 특성을 이해할 필요가 있다.
Complete Binary-Tree는 이진 트리에서 아래 두 가지 조건을 더 만족해야 한다.
- 마지막 레벨(leaf)을 제외한 모든 노드가 채워져 있다.
- 모든 노드들은 왼쪽부터 채워진다.
이런 Complete Binary-Tree의 특성을 배열로 표현하면 아래 그림과 같이 루트 노드는 1번째 Index에 저장되며 부모노드보다 큰 값을 가지는 자식노드들은 왼쪽부터 순서대로 저장이 가능하다.(0-based Index일 경우는 Root가 0번째 임) 이와 같이 배열을 이용하면 특정 Index에 직접 접근할 수 있으므로 효율적인 처리가 가능해 진다.
위 그림에서 특징으로는
- 설명 용이함을 위해 위 그림의 시작 Index(root)는 1 부터 시작한다. (실제 구현은 0-based index로 구현)
- 각 노드와 대응되는 배열의 Index는 유지된다.
이런 특징을 이용하면 다음을 유추할 수 있다. [ ] 안은 0-based index로 할 경우, i: index
- 왼쪽 자식 노드 Index = Index × 2 [iLeftChild(i) = 2⋅i + 1]
- 오른쪽 자식 노드 Index = Index × 2 + 1 [iRightChild(i) = 2⋅i + 2]
- 부모 노드 Index = floor(Index / 2) [iParent(i) = floor((i−1) / 2)]
- 내부 노드(leaf가 아닌 노드)의 Index 범위는 전체 노드 개수의 1/2 미만(0-based index일 경우)
이와 같은 Complete Binary-Tree의 특징와 성질을 이용하여 Heap에 추가(offer)와 삭제(poll) 연산을 설명하면 아래와 같다.
offer() operation
offer()연산은 Queue 추가하는 enqueue 동작으로 Heap에 노드를 추가(offer)하는 과정은 아래의 그림으로 설명할 수 있다.
배열의 마지막 부분에 노드를 넣고 부모노드를 찾아가면서 부모 노드가 삽입 노드보다 작을 때 까지 요소를 교환해가면서 올라간다. 위와 같은 과정을 흔히 위로 올라가면서 선별한다고 하여 siftUp (상향 선별) 이라고 부른다. 즉, 값을 추가 할 때는 size + 1 인덱스에 새로운 값을 추가하고 siftUp 과정을 거쳐 ‘재배치’를 한다고 생각하면 된다. 여기서 주목할 부분은 Heap에 새로운 노드가 추가될 때 항상 Root는 최소값으로 유지된다는 것이다.
poll() operation
poll() 연산은 Queue에서 Head를 추출하는 dequeue 연산으로 Heap에서 Root노드를 추출하는 동작이다. dequeue 이후의 내부 동작은 공백이 된 Head 노드를 앞애서 설명한 offer() 연산과 반대의 과정으로 채워나가면 된다. 즉, 마지막에 위치한 노드를 비어있는 Root 노드로 가져온 다음 자식노드가 재배치하려는 노드보다 크거나 자식노드가 없을 때까지 위치를 재배치 해나가면 된다. 여기서 자식노드가 없을 때까지 수행한다는 것은 앞애서 Complete Binary-Tree에서 유추한 것처럼 전체 노드 개수의 1/2 미만까지 확인해 나가면 된다. 이 내용을 그림으로 표현하면 아래와 같다.
여기서 주목할 점은 왼쪽 자식 노드와 오른쪽 자식 노드 중 ‘작은 값을 가진 노드’와 재배치를 해야 한다는 것이다. 만약 반대로 된다면 위 그림의 첫번째 비교/교환 단계에서 35가 Root노드에 배치되어버리며, 이는 왼쪽 자식노드인 10보다 큰 값을 가지게 되어 최소Heap을 만족하지 못하게 된다. 이렇게 아래로 내려가면서 재배치하는 과정을 siftDown (하향 선별)이라고 한다.
mutate() operation
mutate연산는 PriorityQueue.java가 제공하지 않는 메소드로 Queue 내부에 있는 노드의 상태가 변경될 경우 offer()연산과 poll()연산을 같이 활용하면 간단하게 구현할 수 있다. 즉, 상태(값, Cost)가 변경된 노드가 부모노드보다 값이 작다면 offer()에서 했던 shiftUp연산을 수행하고, 자식노드보다 값이 크다면 poll()에서 했던 shiftDown 연산을 수행하면 된다. 이 과정을 간단하게 코드로 설명하면 아래와 같다.
MutablePriorityQueue.java
...
public boolean mutate(E e) {
final int i = indexOf(e);
if (i == -1) return false;
int child = (i << 1) + 1; // assume left child is least
int parent = (i - 1) >>> 1;
Object[] es = queue;
if (i < (size >>> 1) && ((Comparable<? super E>) e).compareTo((E) es[child]) > 0) {
siftDown(i, e, es, size); // the priority of the element is greater than the priority of child element
} else if (i > 0 && ((Comparable<? super E>) e).compareTo((E) es[parent]) < 0) {
siftUp(i, e, es);
}
return true;
}
...Java API로 제공되는 PriorityQueue.java를 확장해서 mutate기능을 추가하면 되겠지만 siftUp, siftDown과 같이 핵심 메소드들의 visibility가 private으로 설정되어 있어 클래스 외부에서는 접근이 불가능하다. 따라서 새로운 MutablePriorityQueue로 구현할 수 밖에 없으며 siftUp, siftDown 메소드는 기존의 메소드와 동일하다고 보면 된다.
MutablePriorityQueue에 추가된 유용한 Method
find() Method
앞에서 설명한 mutate()메소드 뿐만 아니라 알고리즘 동작시 PriorityQueue에 들어 있는 지점들 중 특정 지점을 찾아내는 기능을 많이 활용한다. 이를 위해 Queue 내부의 모든 지점을 배열로 변환한 다음 찾아내는 방법 또는 Stream을 활용하여 찾는 방법을 이용한다. 이 경우 개발해야 하는 코드가 길어지거나 내부적으로 배열을 복사해야하는 부담을 안고 있다. 배열 복사 없이 그리고 간결한 코드를 작성할 수 있도록 Queue 내부의 배열에 직접 접근하여 검색이 가능하도록 find() 메소드를 추가하였다.
...
/**
* Refer to the find method of MutableQueue interface
*/
public Optional<E> find(Predicate<? super E> predicate) {
E e = null;
for (int i = 0; i < size; i++) {
if (predicate.test((E) queue[i])) {
e = (E) queue[i];
break;
}
}
return Optional.ofNullable(e);
}
...이를 이용할 경우 Dijkstra알고리즘 구현시 Queue내에 특정 방문지점을 찾는 코드는 아래와 같이 간략하게 작성할 수 있다.
...
final MutableQueue<Visit> unsettled = new MutablePriorityQueue<>();
...
Visit adjacent = unsettled.find(v -> v.has(link.to())).orElseGet(() -> new Visit(link.to()));
...pick() Method
또한 Queue 내부의 배열을 검색하지 않고 Map을 이용하여 바로 접근할 수 있도록 pick() 메소드도 추가하였다. pick() 메소드는 Node를 파라미터로 받아 Map서 바로 찾기 때문에 find()보다 더 간결하게 사용할 수 있으며 더 빠른 성능을 보장한다. 아래는 pick()메소드를 활용하는 코드를 보여 준다.
...
Visit adjacent = unsettled.pick(link.to()).orElseGet(() -> new Visit(link.to()));
...Dijkstra 알고리즘 적용시 성능 테스트
테스트 시나리오
동일한 출발지 목적지(서울역 -> 강릉역) 기반으로 PriorityQueue를 아래의 시나리오로 적용하여 총 5회 연속 테스트
- Visit의 Cost 변경시 PriorityQueue 내의 우선순위를 재조정 하도록 MutablePriorityQueue 적용
- Visit의 Cost 변경시 PriorityQueue에서 해당 visit을 삭제한 후 재 삽입(offer)
- Visit의 Cost 변경시 PriorityQueue 객체를 새로 생성
테스트 환경
- OS: Ubuntu 20.04.6 LTS
- CPU: Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
- Memory: 32G
- JVM: openjdk version “17.0.10” 2024-01-16
- JVM Heap 설정: -XX:MetaspaceSize=2048m -Xms4096m -Xmx8g -XX:NewRatio=1 -XX:SurvivorRatio=2 -XX:ConcGCThreads=2
테스트 결과
- 서울역(56262748831678) → 강릉역(56285752109103) 경로탐색시 동일한 결과(경로, 거리, 비용) 기반 1초 이상 탐색시간 개선 확인
- pick() 메소드 적용시 13.15초로 MutablePriorityQueue적용시 보다 약 7초 개선(약 64%)
- 예상대로 이미 Queue에 들어있던 지점을 찾는 연산이 전체 탐색속도에 많은 영향을 주고 있었음
- indexOf()에서 특정 항목의 인덱스를 찾기 위해 사용했던 Array Scan방식을 Map을 이용한 Index 저장 방식으로 변경하였으나 뚜렷한 개선효과 찾지 못함
- siftUp/siftDown 과정에서 항목이 Swap될 경우 해당 인덱스를 Map에서 업데이트하는 추가 Operation으로 성능이 상쇄되는 것으로 추정