크기가 큰 배열에서의 탐색 & 캐시 히트

https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

위 문제를 풀 때 큰 배열에서 탐색을 하는 과정에서 특이한 현상을 겪어 쓰는 글.

 

위 문제는 크기가 4000인 배열 A, B, C, D의 원소의 합이 0인 경우의 수를 구하는 문제이다.

이를 단순하게 접근하면 모든 배열에서 한 개의 원소를 뽑는 경우이므로, 4000 ^ 4 = 256조.

시간복잡도를 줄이기 위해서, A와 B의 합을 AB, C와 D의 합을 CD로 놓으면, 경우의 수는 4000^2 * 2 = 3200만.

AB의 원소 * -1 의 값을 CD에서 찾으면 이분탐색으로 log(4000^2)만에 구할 수 있다.

여기에서 CD의 원소가 중복될 수 있으므로, upperBound - lowerBound를 통해 개수를 구할 수 있다.

 

이렇게 푸는 방법이 정답인데, 이 과정에서 특이한 현상을 발견했다.

모든 AB의 원소를 순회하며 CD에서만 이분탐색을 진행할 것이기 때문에, CD배열만 정렬을 해 주었다.

하지만 AB배열 또한 정렬을 했을 때, 시간이 2배 단축됐다.

분명 AB배열을 정렬하는 것은 로직상 없어도 되는 동작인데, 이를 통해 시간이 2배나 단축된 것이다.

 

이 현상의 원인으로는 캐시 히트로 인한 시간 단축으로 볼 수 있다고 한다.

https://www.acmicpc.net/board/view/74585#comment-122660

글 읽기 - upper_bound 사용시에 AB vector의 정렬에 따른 시간차이

djm03178님의 답변

캐시 히트의 차이라고 생각됩니다.

AB를 정렬할 경우 CD를 이분탐색할 때 연속적으로 이전에 봤던 위치들을 중심으로 다시 탐색하게 될 확률이 높아집니다. CD의 크기가 매우 크다는 것을 감안할 때 대부분의 위치를 매번 메모리로부터 불러오지 않고 캐시에서 찾아낼 수 있으므로 훨씬 시간이 절약됩니다. AB를 정렬하지 않으면 CD에서 찾는 위치가 매번 달라질 확률이 높아지므로 캐시 안에 들어가지 않는 수많은 페이지들을 지속적으로 갈아끼워야 할 확률이 높아져 시간이 오래 걸리게 됩니다.

이처럼 캐시의 시간지역성을 염두에 두었을 때, 알고리즘에서의 시간복잡도를 넘어선 최적화가 가능할 수도 있다는 이야기로 해석된다.