개요
에이스타 알고리즘과 JPS 알고리즘의 성능을 비교해보자
에이스타 알고리즘과 JPS 알고리즘이 각 상황에서 어떤 성능을 보이고 어떤 차이가 있는지 알아보자
테스트 조건
가로 세로 100 x 100, 200 x 200 타일에 여러개의 장애물을 랜덤하게 설치한다.
각각의 길찾기 알고리즘으로 길을 찾은다음, 목적지를 찾는다.
길찾기에 성공한 경우, 길찾기 탐색을하며 발생한 시간을 모두 더하고 길찾기를 한 수만큼 나눠 평균속도를 계산하였다.
성능을 테스트할 기기 : 맥북 M1 Air 기본형
테스트 횟수는 기기의 한계로 인해 각각 1000번, 100번 수행되었다. 정확한 결과를 알기 위해선 더 많이 테스트해봐야겠지만,
100 x 100 타일에서의 테스트 (1000번 테스트)
| 장애물의 수 | 에이스타 알고리즘 | JPS 알고리즘 |
|---|---|---|
| 100개 | 8ms | 1ms |
| 500개 | 26ms | 1ms |
| 1000개 | 41ms | 2ms |
| 2000개 | 63ms | 2ms |
에이스타 알고리즘은 장애물의 수가 증가하는만큼 어느정도 눈에 띄게 비례하여 상승하였지만, JPS 알고리즘은 장애물의 개수가 증가하여도 크게 변화하지 않았다.
무엇보다 연산 속도가 JPS 알고리즘이 압도적으로 빠른것이 눈에 띈다.
차이를 더 명확히 보기 위해 맵의 크기를 늘렸다.
200 x 200 타일에서의 테스트 (100번 테스트)
| 장애물의 수 | 에이스타 알고리즘 | JPS 알고리즘 |
|---|---|---|
| 100개 | 47ms | 10ms |
| 500개 | 121ms | 14ms |
| 1000개 | 202ms | 15ms |
| 2000개 | 353ms | 15ms |
| 5000개 | 695ms | 17ms |
맵의 크기를 늘리자 정말 놀라운 결과가 나왔다. 장애물이 얼마나 늘어나든 JPS 알고리즘의 탐색 속도가 크게 변화하지 않았다. 특히 장애물이 500개일때와 2000개일때의 결과가 크게 차이나지 않는다는점이 놀라웠다.
마치며
예전에 JPS(B) 알고리즘을 도입해서 포트폴리오를 만든적이 있었다.
그 땐 R&D를 제대로 하지 않고 사용했기 때문에 면접에서 ‘얼마나 차이나는가?’라는 질문에서 모른다고 대답했었다.
그때가 생각나서 시작한 포스팅이었는데, 이렇게 하나하나 눈으로 보니 R&D가 얼마나 중요한지 알게 되었다. 앞으로 무언가 새로운 시도를 할때 명확하게 분석하고 사용하는 습관을 들여야겠다.