20장 코드 최적화 기법

• 이따금 알고리즘을 개선할 방법이 잘 보이지 않는다.
• 다음의 사고 전략은 지난 몇 년간 코드를 더 효율적으로 바꾸는 데 큰 역할을 했다.

1. 전체 조건: 현재 빅 오 파악하기

• 최적화 기법으로 들어가기 전에, 알고리즘 최적화에 앞서 반드시 해야 할 일이 있다.
• 최적화의 전제 조건(prerequisite)은 현재 코드의 효율성을 파악하는 것이다.
• 현재 얼마나 빠른지 알아야 알고리즘을 더 빠르게 만들 수 있기 때문이다.
• 이제부터 현재 알고리즘의 빅 오를 알아내는 단계를 전제 조건(prereq)이라 부르겠다.

2. 시작점: 상상할 수 있는 최상의 빅 오

• 이 장에서 소개할 기법이 모두 유용하지만 어떤 기법은 특정 시나리오에 도움이 되고, 또 어떤 기법은 다른 시나리오에 효과적이다.
• 하지만 이 첫 번째 기법만은 모든 알고리즘에 유용하며, 반드시 최적화 프로세스의 첫 단계여야 한다.
• 현재 알고리즘의 효율성을 파악했으면, “상상할 수 있는 최상의 빅 오”라 부를 만한 빅 오를 생각해내자.
  • 속도 관점에서는 “가능한 최상의 실행 시간”이라 부르기도 한다.
  • 상상할 수 있는 최상의 빅 오란 본질적으로 당면한 문제에 기대할 수 있는 정말 최상의 빅 오다.
  • 절대 달성할 수 없다고 믿는 빅 오다.
• 배열의 각 항목을 출력하는 함수를 작성할 때 상상할 수 있는 최상의 빅 오는 아마 O(N)일 것이다.
• 배열 내 항목 N개를 각각 출력하려면 항목 N개를 각각 처리하는 수밖에 없다.
• 출력하려면 각 항목에 “접근해야” 하니 달리 방법이 없다.
• 따라서 이 시나리오에서 상상할 수 있는 최상의 빅 오는 O(N)이다.
• 즉, 알고리즘을 최적화하려면 두 가지 빅 오를 밝혀내야 한다:
  1. 알고리즘의 현재 빅 오(전제 조건)
  2. 작업에 걸릴, 상상할 수 있는 최상의 빅 오
• 두 빅 오가 다르면 최적화할 여지가 있다는 뜻이다.
• 현재 알고리즘의 실행 시간이 O(N^2)이고 상상할 수 있는 최상의 빅 오가 O(N)이면 노력해 볼 개선점이 생긴 것이다.
• 빅 오간 차이는 최적화로 얻을 잠재적 이익을 나타낸다.
• 단계를 요약해 보자.
  1. 현재 알고리즘의 빅 오 카테고리 알아내기(전제 조건)
  2. 당면한 문제에 기대할 수 있는 상상할 수 있는 최상의 빅 오 알아내기
  3. 상상할 수 있는 최상의 빅 오가 현재 빅 오보다 빠르면 알고리즘을 최대한 최상의 빅 오에 가깝게 만들겠다는 목표로 코드 최적화를 위해 노력할 수 있다.
• 당연하게도, 상상할 수 있는 최상의 빅 오를 항상 달성할 수는 없다.
• 그래도 상상할 수 있는 최상의 빅 오는 최적화로 이뤄낼 수 있는 목표를 제시하는 도구다.

3. 룩업 마법

• 즐겨 쓰는 최적화 기법 중 하나는 “O(1) 시간 안에 마법처럼 원하는 정보를 찾을 수 있다면, 알고리즘을 더 빠르게 바꿀 수 있을까?” 하고 자문하는 방법이다.
• 대답이 “예”라면 자료구조를 사용해 볼 여지가 있다.
• 이 기법을 “룩업 마법”이라 부르겠다.
• 룩업 마법을 실현할 수 있는 가장 쉬운 방법 중 하나는 코드에 자료 구조를 추가하는 것이다.
• 이 자료구조는 데이터를 빠르게 룩업할 수 있는 방식으로 데이터를 저장하는 데 쓰인다.
• 대개 해시 테이블이 가장 적합한 자료 구조인데, 8장 해시 테이블로 매우 빠른 룩업에서 배웠듯이 O(1)만에 룩업하기 때문이다.
• 단 기존의 알고리즘이 추가 공간을 필요로 하지 않았다면 해시 테이블의 용량만큼 공간을 더 사용할 수 있다.
• 그래도 속도를 위해 메모리를 기꺼이 희생할 수 있다면 대단한 최적화다.

4. 패턴 인식

• 코드 최적화와 알고리즘 개발에 전반적으로 쓰이는 가장 유용한 전략 중 하나가 문제에서 패턴을 찾는 방법이다.
• 대개 패턴을 발견하면 문제의 모든 복잡도를 해소하고 실제로 꽤 간단한 알고리즘을 개발할 수 있다.
• 흔히 알고리즘 분류 중 수학으로 분류되는 문제들이 이러한 패턴을 갖고 있을 수 있다.

5. 탐욕 알고리즘

• 다음은 가장 다루기 힘든 알고리즘의 속도를 올리는 전략이다.
• 모든 상황에서 통하지는 않지만, 일단 통하면 상황이 반전된다.
• 탐욕 알고리즘은 매 단계마다 그 순간에 최선처럼 보이는 방법을 고른다.
• 탐욕스러운 방식이 항상 통하지는 않는다. 하지만 알고리즘을 최적화할 때 시도할 수 있는 또 하나의 도구다.

6. 자료 구조 변경

• 데이터를 다른 자료구조에 저장했을 때 어떻게 될 지 상상해보는 것도 유용한 최적화 기법 중 하나다.
• 가령 데이터가 배열 형태로 제공된 문제를 해결하는 중이라고 하자.
• 같은 데이터를 해시 테이블이나 트리, 그 외 다른 자료구조에 저장한다고 상상해 보면 이따금 기발한 최적화 기회가 생기기도 한다.
• 어떤 자료구조를 사용해야 하는지 항상 분명한 것은 아니므로 현재 데이터를 다양한 형식으로 변환한 모습을 상상해 보고 최적화가 가능한지 판단해 보자.
• 그래도 대부분 해시 테이블이 탁월한 선택이니 해시 테이블부터 시작하면 좋다.

7. 요약

• 20장에서 소개한 기법은 코드를 최적화하는 데 유용하다.
• 다시 말하지만 항상 현재 빅 오와 상상할 수 있는 최상의 빅 오를 알아내는 것이 먼저다.

8. 작별 인사

• 지금까지 많은 내용을 배웠다.
• 알고리즘 디자인과 자료 구조의 올바른 선택이 코드 성능에 중대한 영향을 줄 수 있음을 배웠다.
• 코드 효율성을 알아내는 법을 배웠다.
• 코드를 더 빠르고 메모리 효율적이면서 간결하게 최적화하는 법도 배웠다.
• 각 기법의 장단점을 파악해 현재 문제에서 최선의 선택을 내릴 수 있는 능력을 키웠다.
• 또한 처음에는 명확하지 않았던 새로운 방법을 구상할 수 있는 능력도 갖췄다.