마지막 장에서는 코드 최적화 기법 몇 가지를 소개한다. 다음의 사고 전력 (mental strategy)은 지난 몇 년간 코드를 더 효율적으로 바꾸는 데 큰 역활을 했다.
최적화 기법으로 들어가기 전에 알고리즘 최적화에 앞서 반드시 해야 할 일은 현재 코드의 효율성을 파악하는 것이다. 즉, 현재 얼마나 빠른지 알아야 알고리즘을 더 빠르게 만들 수 있기 때문이다.
“상상할 수 있는 최상의 빅 오”(가능한 최상의 실행 시간)를 생각하는 것은 모든 알고리즘에 유용하며, 반드시 최적화 프로세스의 첫 단계여야 한다.
배열의 각 항목을 출력하는 함수라면 항목 N개를 각각 처리해야 하므로 최상의 빅 오는 O(N)이다.
알고리즘을 최적화하려면 두 가지 빅 오를 밝혀내야 한다.
현재 빅 오와 최상의 빅 오가 다르다면 최적화할 여지가 있다는 뜻이므로 두 빅 오 간 차이는 최적화로 얻을 잠재적 이익을 나타낸다.
상상할 수 있는 최상의 빅 오를 항상 달성할 수는 없다. 최상의 빅 오는 최적화를 이뤄낼 수 있는 목표를 제시하는 도구다. 그래서 보통은 현재 빅 오와 최상의 빅 오 사이쯤으로 최적화를 한다.
최적화로 달성할 목표를 제시해준다는 점을 최대한 활용하려면, 상상의 나래를 펼쳐 아주 놀라운 상상할 수 있는 최상의 빅 오를 생각해내는 것이 좋다.
누군가 그 빅 오로 문제를 해결할 수 있다고 말했을 때, 그 말을 믿을 수 있다면 그것을 최상의 빅 오로 삼는다.
“O(1) 안에 원하는 정보를 찾을 수 있다면 알고리즘을 더 빠르게 바꿀 수 있을까?” 라는 질문에 대한 답이 “예”라면, 해시 테이블 같은 자료 구조를 통해 마법을 부릴 수 있다.
도서관 소프트웨어를 개발하며 책과 저자 데이터를 두 개의 배열에 넣었다고 하자.