일반적으로 알고리즘과 자료구조 그리고 복잡도에 대한 이야기를 개발자들 사이에서는 많이 한다. 그리고 자주 나는 결론은 그런걸 고민하는 시간에 다른 중요한 일을 하고, 그 문제에 대해서는 서버를 증설하면 된다는 식으로 그냥 해결 방법을 얼버무린다.
물론 서버를 증설하는 방법은 좋다.
하지만 서버를 증설했을시에 자동으로 그런 리소스 분배가 되는지도 확인해야되고 그런 중요한 부분과 또 다른 점들때문에 배보다 배꼽이 더 커지는 경우가 있을 수 있음을 생각해본다.
그래서 대용량을 처리하거나 대량의 트래픽이 발생할 수 있는 서비스의 경우에는 고민할 수 있을 만큼의 최적화를 할 수 있는대로 해야 한다고 생각한다.
예를 들어 하루에 한번 도는 스케줄러 같은 경우는 그런곳에 신경을 쓰기 보다는 빨리 만들고 고칠 수 있는 그런 언어나 로직으로 짜야한다고 생각이 들고, 검색엔진같은 대용량과 사용자가 많이 집중될 수있는 부분에서는 언어에서 로직 그리고 알고리즘에 까지 최적화에 최적화를 기해야 한다고 생각이 든다.(물론 확장성도 중요한 부분이라고 할 수 있겠지만….)
그럼 왜 복잡도의 개념을 쓰는것일까?
1. 알고리즘간의 비교를 위해서다.
2. 심지어는 인간의 언어로 표현을 해서도 수긍이 가야 한다. 그러니까 그 알고리즘 자체만으로 평가가 되어야 한다.(컴퓨터의 성능같은건 제하고…)
3. 대용량 문제이다.
대용량의 문제일때 복잡도는 정말 중요하다. 몇개 되지 않는 데이터일 경우에는 차이가 미비하겠지만 대용량의 경우에는 그것이 지수승으로 증가될 가능성이 있을 수 있기 때문이다.
예를 들어 두가지 정렬 알고리즘을 비교해 보자.
첫번째 알고리즘으로 BottomUpMerge Sort
두번째 알고리즘으로 Selection Sort
알다시피
BottomUpMerge Sort의 최대 비교 횟수는 nlogn – n + 1 (n은 2^x 일때.)
Selection Sort의 최대 비교 횟수는 n(n-1)/2
평균 데이터 비교에 드는 시간은 10^-6 초라고 가정하면.
데이터가 128개라면
BottomUpMerge Sort는 10^-6(128 * 7 – 128 + 1) = 0.0008초의 결과가 나오고
Selection Sort는 10^-6(128 * 127)/2 = 0.008 초가 된다.
128개의 데이터로는 수치상으로는 차이가 있겠지만 피부로 느낄 수 있는 속도 차이가 나오지 않는다.
하지만 데이터의 갯수가 2^20(1,048,576) 개라고 하면 이야기가 달라질 것이다.
BottomUpMergeSort는 10^6(2^20 * 20 – 2^20 + 1) = 20 초
Selection Sort는 10^-6(2^20 * (2^20 – 1)) / 2 = 6.4 일
어느 알고리즘 책에나 나올만한 내용이지만 실제 이런 부분을 계산 해보지 않고서는 그 중요성을 실감할 수 없다.
요즘같이 서버값이 싸져버리고, 데이터를 만들기가 쉬운 이때에 대용량에 대한 이슈를 개발자들이 마음속에 가지고 있어야 되지 않을까 한다.
알고리즘이 첫번째 문제라면… 두번째는 무엇일까?
두번째는 언어의 문제라고 본다.
언어를 얼마나 효율적으로 쓰느냐라고 생각이 든다.
얼마전에 Glade님이 메신저로 보내주신 opmization C 라는 문서를 보고 느낀점이 많았다.
예를 들어 String 연산의 부하, malloc 남용의 문제점, 언어 내부에서 쓰는 Stack문제 등등
물론 C언어에 대한 문서였지만, 아마도 다른 언어도 이런 문서가 반드시 있을것이라고 생각이 든다.
이런 부분에 대한 최적화의 고민은 끝이 없겠지만 처음 개발시부터 이런 부분에 대한 어느정도 부담감을 가지고 개발하는것과 아닌것은 나중에 큰 차이가 있을 거라는 생각이 든다.
그냥 저번에 하얀눈길님과 만나서 이야기한 것들이 갑작스럽게 생각이 나서 써봤다.
위와같은 개념을 가지지 않은 개발자들이 생각 밖으로 너무 많다는 이야기에….
구글이나, 야후, 이베이, MS 같은 기업들이 알고리즘과 복잡도에 대해서 인터뷰시 물어보는게 당연한 이야기 일수도 있다. 지금과 같은 대용량 시대에 말이다.
알고리즘 복잡도(complexity)와 언어(language) by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.