알고리즘 개선이란게

예전에 애리조나대 문 교수님께서, 컴퓨터공학은 응용학문이다 보니 실제로 중요한 법칙 같은 것은 몇 개가 안되는 것 같다.
라는 말씀을 하셨는데, 문득 옳은 지적이신 것 같다는 생각이 요새 많이 든다.
대부분의 SW 개발 업무라는 것이 어떤 문제가 주어졌을 때 그 문제를 푸는 방법(알고리즘)과 그의 구현(프로그램)이라고 한다면, 대부분의 개발 업무라는게 이런 식인 것 같다.

1) 문제가 주어진다.
2) 한 문제를 여러 작은 문제들로 나눈다.
3) 각 문제에 대한 기존 해결책이 있는지 조사한다.
4) 있으면, 가장 낫다는 놈을 가져다 쓰고 없으면 만든다.
5) 합쳐보고 테스트하고, 추가로 최적화시켜 본다.

그리고 이렇게 해서 잘 쓰다가 요구하는 성능치가 더 높아지면, HW를 추가로 공급하거나, 또는 알고리즘을 개선하는 방법을 써야 한다. 많은 경우 기존 알고리즘을 개선하는 방법은 크게 다음과 같은 것같다.

1) 입력 데이터 크기 줄이기
 - 같은 알고리즘이라도 처리에 필요하지 않는 데이터는 읽지 않음으로써 성능 향상을 꾀할 수 있다.
 - 사실 불필요한 데이터 읽기를 피하기 위한 가장 잘 알려진 데이터 구조는 인덱스이다.
 - 최근의 컬럼-기반 DBMS도 요구되는 데이터만 읽기 위해 데이터를 행-기반에서 열-기반으로 옮긴걸로 간소화할 수 있겠다.

2) 알고리즘 자체의 성능 개선
  - 대개는 최악 복잡도를 개선하는 것을 목적으로 하는데, 실제로는  최악 복잡도는 낮아도 평균 복잡도가 우수한 알고리즘들도 많이 선택되는 듯.

3) 시스템 구조에 좀더 적합한 알고리즘
  - 같은 복잡도라도 시스템 구조를 좀더 잘 활용하는 알고리즘들이 효과적이다. 대표적인 것이 메모리 계층에서 데이터 이동이 많지 않도록 cache-aware한 알고리즘들이다. 복잡도는 더 높은 cuckoo hash가 실제로는 더 빠른 것을 보면 메모리 계층에 대한 고려는 매우 중요.

4) 분산/병렬 처리
  - 알고리즘을 병렬화해서 shared-nothing 또는 shared-memory 구조에서 분산 병렬처리하는 방식으로변경(scale-out)
 
5) 추가 자원 투입
  - 더나은 컴퓨팅 성능을 갖는 HW를 투입(scale-up)

대충 이게 다일 듯.
쓰고나면 별로 하는 일 없어보이는데 왜 이쪽 일이라는 것은 언제나 복잡해 보이는지 모르겠다.