[성능튜닝] 개발에서의 알고리즘

데이터 규모와 계산량 차이

대상이 되는 데이터가 크면 클수록 알고리즘이나 데이터 구조 선택이 속도에 영향을 미치게됩니다. 예를 들면, 데이터 내에서 필요한 데이터를 처음부터 순차적으로 찾아가는 '선형탐색(Linear Search)'은 n건에 대해 n번의 탐색이 필요하므로 O(n)의 알고리즘입니다. '이분탐색(Binary Search)'은 n건의 데이터에서 log n번 만에 목적 데이터를 찾는 알고리즘으로, O(log n)의 알고리즘 입니다. 1,000건에 대해 최대 10번 만에 탐색이 완료됩니다. 데이터 건수가 늘어감에 따라 알고리즘 선택의 차이가 점점 커지고, 목적 데이터를 찾는 처리를 할 때 선형탐색을 사용하는 부분에서 데이터 건수가 1,000건, 100만건, 1,000만 건으로 늘어난다면 당연히 그 지점이 병목이 됩니다. 그러므로 그 지점을 해소하려면 탐색 알고리즘 계산량이 보다 적은 것으로 변경해야 하는게 자명합니다.

적당한 값을 입력하면 명확하게 정의된 계산절차에 따라 값이 출력으로 반환되는 것이 알고리즘입니다. 탐색하고자 하는 값과 대상 데이터를 입력하면 탐색이 이뤄져서 목적 데이터의 위치가 반환되고, 이것이 곧 '탐색 알고리즘'입니다.

넓은 의미의 알고리즘: 처리(도메인 로직, Domain Logic)의 흐름

좁은 의미의 알고리즘: 명확하게 정의된 계산문제에 대해 정의된 계산절차를 수행하는 것이며, 정렬이나 탐색, 해시법과 같은 계산문제의 해법

n의 크기에 관계없이 일정한 시간에 처리가 끝날 경우, O(1)이라고 씁니다. 해시로부터 데이터를 탐색할 경우에는 해시함수의 계산을 수행할 필요가 있는데, 해시함수의 계산은 n에는 의존하지 않으므로 O(1)입니다. 해시의 탐색은 키(key)를 알면 값(value)이 고유하게 결정되므로 키로 값을 탐색하는 처리도 O(1)입니다. 따라서 해시 탐색의 계산량은 전체적으로 O(1)이 됩니다.

선형탐색은 앞서 본 것처럼 요소를 처음부터 찾아가므로 최대 n번 탐색할 필요가 있으므로 O(n)의 알고리즘입니다. 이분탐색은 O(log n)입니다. 선형탐색과 이분탐색은 O(n)과 O(log n)이므로 이분탐색이 계산량은 더 적습니다.

각종 알고리즘을 Order 표기하면 아래와 같은 계산량이 자주 나타납니다.

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) ... O(n^k) < O(2^n)

그림 출처 ( http://www.bigocheatsheet.com/ )

오른쪽으로 갈수록 계산량은 많아집니다. 이러한 계산량은 대규모 데이터를 대상으로 한 경우, 즉 n이 클 경우 실질적으로 실용성을 띄는 것은 O(n log n) 부근까지 입니다. 그 이상이 되면 n에 대해 계산량이 급격하게 커지므로 계산이 끝나지 않는 경우가 자주 있습니다.

상당히 복잡한 알고리즘을 O(n^2)으로 계산할 수 있을 경우 '이건 빠르다'라고 주장할 수도 있으므로 어디가지나 대상이 되는 계산에 따라 다를 수 있습니다. 예를 들면 일반적인 정렬 알고리즘은 아무리 잘해도 O(n log n)보다 빠를 수 없다는 것이 이론적으로 증명되어 있습니다. 따라서 정렬 알고리즘에서는 O(n log n)이면 빠르다고 할 수 있을 것입니다.

계산량 개념은 계산시간뿐만 아니라 공간적인 양에서도 사용됩니다. 즉, 실행시간이나 단계 횟수뿐만 아니라 메모리 사용량을 논할 경우에도 Order 표기가 사용됩니다.

알고리즘은 Order 표기 + 계산량 : 시간계산량(실행시간, 단계 횟수), 공간계산량(메모리 사용량)로 평가됩니다.

알고리즘에 있어서 지수적, 대수적 감각

계산량이 지수적으로 증가하는 알고리즘은 이와 같이 데이터량이 적어도 계산량이 매우 커져버립니다. 한편 지수의 역인 대수적으로만 증가하는 O(log n)인 알고리즘은 데이터량이 꽤 커져도 적은 계산량으로 문제를 해결할 수 있습니다.

예를 들면 1,000만 건 정도 되는 데이터를 대상으로 하는 경우라도 대수적인 알고리즘을 선택할 수 있다면 수십 번만 계산하면 됩니다. 반면, 알고리즘을 잘못 선택해서 O(n^2) 이나 O(2^n)인 것을 구현하게 되면 수백 건 정도의 데이터를 대상으로 하더라도 상당히 불필요한 리소스를 사용하게 되는 프로그램이 만들어 지게 됩니다.

계산량과 상수항

계산량의 Order 표기에서는 이른바 '상수항'을 무시합니다. 상수항이란 해당 알고리즘을 구현하는 중에 입력 크기에 의존하지 않지만 실행하지 않으면 안되는 처리 중 하나입니다. 예를 들면 함수호출이나 함수로부터 값을 반환하기 위한 처리는 상수항이며, 일차변수를 확보하거나 if문으로 분기시키는 등이 처리도 이에 해당합니다. 간단한 구현에서 상수항은 해당 알고리즘의 계산량에 거의 영향을 주지 않지만, 복잡한 구현이 되면 상수항을 무시할 수 없게 됩니다. 또한 구현이 복잡하지 않더라도 CPU 캐시에 올리기 쉬운지, 분기예측이 발생하지 않는지 등 계산량의 구조적인 특성에 의존하는 형태로 상수항에서 차이가 나는 경우도 있습니다.

정렬 알고리즘은 이론적으로 O(n log n)이 하한으로, 평균 계산량 O(n log n)을 달성하는 알고리즘은 여러 개 존재합니다. 그러나 같은 O(n log n)이라도 일반적으로 퀵정렬이 가장 빠르다고 합니다. 퀵정렬은 그 특성상 CPU 캐시를 사용하기 쉽다는 장점이 있어 이 점이 비교할 때 유리하게 작용합니다.

즉, 알고리즘을 비교할때 Order 표기는 편리하지만 구현을 포함해서 생각할때 그것이 전부는 아닙니다. 상수항을 어떻게 구현하느냐에 의존하는 경우가 많아 이를 줄이기 위해서는 구현하는 데 노력을 기울여야 할 필요가 있습니다.

최적화 시, 벤치마크를 하거나 프로파일링을 해서 지금 대상으로 하고 있는 프로그램에 무엇이 문제인가를 정확하게 아는 것은 굉장히 중요합니다. 지금은 알고리즘을 교체해서 개선해야 할 것인지 상수항을 줄여서 개선해야 할 것인지, 오히려 물리적으로 리소스가 부족하므로 하드웨어를 교환해서 성능을 개선해야 할지 이러한 부분을 명확히 한 후, 개선하는 것이 가장 바람직 합니다.

예측이나 측정이 중요하다는 점과 때에 따라서는 명쾌하게 단순한 구현을 시도해보는 것도 좋습니다. 대규모 데이터를 상정한 최적화라는 것도 중요하지만, 데이터 건수가 적은 경우에는 최적화의 의미가 없습니다. 데이터 건수가 '적다'는 걸 사람의 직감으로 추측하는 것도 좋지 않습니다.