[대규모 서비스를 지탱하는 기술] 알고리즘 실용화

대규모 서비스를 지탱하는 기술

알고리즘 실용화

---

알고리즘과 평가

속도를 중시하는 프로그램을 작성할 경우에 알고리즘과 데이터 구조의 선택은 중요하다. 이때 대상이 되는 데이터가 크면 클수록 선택에 따른 차이가 현저해진다.

• 예를 들어서 데이터 내에서 필요한 데이터를 처음부터 순차적으로 찾아가는 선형 탐색(Linear Search)은 1,000건의 데이터가 있을 때 원하는 데이터를 찾기까지 탐색을 반복하면서 최대 1,000번을 탐색하는 알고리즘이다. n건에 대해 n번의 탐색이 필요하므로 O(n)의 알고리즘이라고 한다.
• 반면에 이분탐색은 (Binary Search)은 n건의 데이터에서 log n번 만에 목적 데이터를 찾는 알고리즘으로, O(log n)이다. 이분 탐색에서는 1,000건에 대해 최대 10번 만에 탐색이 완료된다.
• 이는 데이터의 크기가 커지면 커질수록 더욱 중요하다. 예를 들어 데이터 100만건에 대해 O(n)은 100만 번 걸리는 반면, O(log n)은 20번 만에 끝난다. 이처럼 목적 데이터를 찾는 처리를 할 때 선형탐색을 사용하는 부분에서 데이터 건수가 1000건, 100만 건, 1000만 건으로 늘어난다면 당연히 그 지점이 병목이 될 것이다. 그러므로 그 지점을 해소하려면 탐색 알고리즘을 계산량이 보다 적은 것으로 변경해야 하는 게 자명하다.

이때 최대 탐색횟수는 계산 횟수의 기준이 되는 수로 계산량이라고 한다. 일반적으로는 계산량이 적을수록 속도가 빠르다고 할 수 있다.

 

좁은 의미의 알고리즘, 넓은 의미의 알고리즘

알고리즘이라는 용어는 좁은 의미, 넓은 의미로 다양하게 사용되는 듯하다.
넓게는 처리(도메인 로직)의 흐름, 좁은 의미의 알고리즘은 명확하게 정의된 계산문제에 대해 정의된 계산절차를 수행하는 것이라고 할 수 있다.
이 책에서 이야기 하는 알고리즘은 좁은 의미의 알고리즘이라고 할 수 있다.

알고리즘을 배우는 의의

• CPU나 메모리 등 컴퓨터 자원은 유한하므로 알고리즘에 대해 배우는 것은 중요하다.
• 또한 알고리즘은 디자인패턴과 마찬가지로 엔지니어에게 공통 언어이다. 커뮤니케이션을 완료하기 위해서는 서로 해당 알고리즘이 무엇인지를 올바르게 이해해둘 필요가 있다.
• 알고리즘을 알아둠으로써 새로운 문제에도 대처할 수 있다.

알고리즘의 평가

알고리즘의 계산량은 대개의 경우 정량적으로 평가할 수 있다. 알고리즘의 평가에는 Order 표기를 사용하는 것이 일반적이다.

Order 표기는 대상이 되는 알고리즘이 입력 크기가 n일 때 대략적으로 이 정도 계산량이 소요된다는 것을 표기하는 기법이다.

알고리즘과 데이터 구조

알고리즘 서적을 보면 알고리즘과 데이터 구조는 세트로 다루어지는 경우가 자주 있다.

데이터 구조는 배열, 리스트, 트리 구조와 같이 대상이 되는 데이터를 저장 또는 표현하기 위한 구조를 말한다.

데이터 구조와 알고리즘이 세트로 논의되는 것은 알고리즘에서 자주 사용하는 조작에 맞춰 데이터 구조를 선택할 필요가 있기 때문이다.

예를 들어 사전에 적절한 트리 구조로 데이터를 저장해두면, 대개의 경우 탐색 처리를 단순화할 수 있어 계산량을 줄일 수 있다.