제 9장은, 코드 튜닝에 관한 부분입니다. 이 책에 실린 내용은 전반적으로 까다롭습니다만, (물론 제가 머리가 나빠서 그럴지도 모릅니다) 특히 9장에 실린 내용은 더 까다로운 편입니다. 하지만 그 까다로움을 넘어서면, 이거다 싶어서 무릎을 치게 되는 일이 생기죠.

9장을 보면 이진 탐색이라는 문제에 대한 초기 해법을 어떻게 가다듬어 보다 좋은 성능을 내는 알고리즘으로 변모시킬 수 있는 지가 나옵니다. 저정도면 나도 할 수 있겠다 싶은 대목도 있습니다만, 그렇지 않은 부분도 많습니다. 아래의 알고리즘을 한 번 보죠. 179페이지부터 180페이지에 걸쳐 나오는 알고리즘입니다. 이진 탐색을 할 대상 수 집합의 크기가 1000이라는 점을 이용하는 코드입니다. 같은 수가 여러 개 있는 상황을 허용하고, 그 중 첫 번째 수의 위치를 찾는 것을 목표로 하고 있기 때문에, 흔히 보던 이진 탐색 알고리즘과는 좀 다를 수 있습니다.

i = 512
l = -1

if x[511] < t
    l = 1000 - 512
while i != 1
    /* invariant : x[l] < t && x[l+i] >= t && i = 2^j */
   
nexti = i / 2
    if x[l+nexti] < t
        l = l + nexti
        i = nexti
    else
        i = nexti
/* assert i == 1 && x[l] < t && x[l+i] >= t */
p = l + 1
if p > 1000 || x[p] != t
    p = -1

여기서 저자는 빨간 색으로 표시된 부분의 코드를 똑똑한 컴파일러라면 어떻게 최적화할지를 묻고, 그에 대한 답을 보여줍니다. (컴파일러가 최적화하는 순서를 보이지는 않습니다.) 사람이라면 어떻게 최적화할까요?

(1)
nexti = i / 2
if [l + nexti] < t
    l = l + nexti
i = nexti

i = nexti를 하는 부분은 if 블럭과 else 블럭에 공통적이니까 굳이 if-else 블럭 안에 둘 필요는 없습니다. 밖으로 끄집어 내면 되죠.

(2)
i = i / 2
if [l + i] < t
    l = l + i

if 블럭 안에서 nexti에 대해 side-effect를 발생시키는 부분이 없으므로, i에 nexti를 대입하는 부분은 if 문 위쪽으로 끌어올릴 수 있습니다.

이 정도는 뭐 나도 쉽게 할 수 있겠다, 싶습니다만, 막상 코드를 작성하다 보면 그렇지 않은 경우도 많습니다. 알고리즘을 차근차근 뜯어볼 시간적 여유가 주어지지 않는 경우도 많거든요. 이 책이 갖는 강점은, 독자에게 그런 류의 사고를 할 수 있는 드문 기회를 제공한다는 점입니다.

이 코드의 마지막 버전은 더 재미있습니다. 저자는 "심장이 약한 사람은 보지 말 것"을 권하고 있기도 합니다. 이 코드는, 루프 선체를 펼쳐서 루프를 도는 데 드는 오버헤드와, i를 2로 나누는 연산을 제거해버렸습니다.

l = -1
if ( x[511] < t ) l = 1000 - 512
    /* assert x[l] < t && x[l+512] >= t */
if ( x[l+256] < t ) l += 256
    /* assert x[l] < t && x[l+512] >= t */
if ( x[l+128] < t ) l += 128
if ( x[l+64] < t ) l += 64
if ( x[l+32] < t ) l += 32
if ( x[l+16] < t ) l += 16
if ( x[l+8] < t ) l += 8
if ( x[l+4] < t ) l += 4
if ( x[l+2] < t ) l += 2
    /* assert x[l] < t && x[l+2] >= t */
if ( x[l+1] < t ) l += 1
    /* assert x[l] < t && x[l+1] >= t */

p = l + 1
if p > 1000 || x[p] != t
    p = -1

이런 코드 튜닝은, 코드 튜닝이 어떤 일을 할 수 있는지를 보여주는 '극한의' 사례라고 할 만 합니다. 이렇게 튜닝된 코드는 원래 버전의 이진 탐색에 비해 36% 향상된 속도를 보여준다고 합니다.

이 정도로 코드를 다듬는 것이 항상 가능하지는 않고, 그럴 필요가 없을 때도 있습니다만, 속도가 문제가 되는 상황은 생각보다 자주 발생합니다. 그럴 때에는 가능한 옵션을 찾아 이리저리 프로파일링을 해 보게 마련인데요. 프로파일링을 하면 병목구간을 찾아낼 수는 있는데, 발견된 병목구간을 어떻게 해소할 지는 분명하지 않은 경우가 많습니다. 병목구간을 해소하는 방법으로 많은 경우 구조적인 해결방법(architectural solution)을 최우선으로 고려하게 되는데, 그런 해결 방법은 의외로 높은 비용을 요구할 때도 있죠.

그러므로 정말 속도가 문제가 된다면, 이런 해법이라도 모색해보는 편이 좋겠습니다. 물론, 이런 코드 튜닝은 굉장히 많은 경험을 요구합니다.

가령, 이 9장의 8번 연습문제를 보면, 추가의 메모리를 사용해서 삼각함수 계산비용을 낮추는 사례가 소개되어 있습니다. 이 사례는 "본 프로그램은, 5도 배수의 인자에 대해서만 삼각함수 계산을 요구한다"는 단순한 사실에서 출발해서, "테이블 형태의 메모리 테이블을 구성하고, 그 테이블을 조회하는 함수"를 구현하여, 삼각함수 계산 비용을 낮추었습니다. 즉, "알고리즘의 실행 환경"을 면밀히 분석한 다음, "그 실행 환경이 갖는 특이성"을 적극적으로 이용하여 성능을 개선한 것입니다. 이런 일이 가능하려면, 프로파일링을 공격적으로 하는 것 뿐 아니라, 사실(fact)을 적극적으로 공략하는 마음가짐이 중요합니다.

수학적인 사고도 요구될 때가 있습니다. 가령 연습문제 12의 경우,

y_{0} = a_{n}
y_{1} = x * a_{n} + a_{n-1}
        = x * y_{0} + a_{n-1}
...
y_{m} = x * y_{m-1} + a_{n-m}

을 유도할 수 있으면 2n이 아닌 n짜리 알고리즘을 만들어 실행시간을 반으로 줄일 수 있습니다. 대부분의 프로그래머는 이정도는 하실 수 있겠습니다만, 저처럼 머리가 나빠서 앉은 자리에서 생각을 해 낼 수가 없다면 실행시간의 반을 까먹는 일이 생기게 되겠죠.

그러니 결국 좋은 알고리즘을 위해서는 Fact에서 출발해 Context에 대한 Assumption을 만들고, 거기에 Experience를 섞어서 Solution을 찾아야 하는 셈입니다. 약자를 다 모으면 FACES로군요. ㅋㅋ 세상 문제들의 다양한 측면들(Faces)을 두루 볼 수 있어야 그 문제에 대한 좋은 알고리즘이 나온다는 뻔한 결론이랄까요.

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

생각하는 프로그래밍(Programming Pearls)의 8장을 보면, 최대 부분합을 구하는 알고리즘을 고안하는 절차가 기술되어 있습니다. 이 책의 다른 부분도 멋집니다만, 저는 특히 이 8장이 굉장히 멋지다고 생각합니다. (아직도 이해가 잘 안되는 부분이 있긴 하지만 말입니다.)

Network Algorithmics라는 책이 있습니다. 이 책은 인터넷을 아우르는 네트워크 장비들이 오늘날같이 발전되어 오기까지 수많은 연구자들이 알고리즘을 어떤 식으로 개선시켜왔는지를 보여주는 멋진 책입니다. 그런 면에서 보면, Programming Pearls와 지향하는 바가 같다고 볼 수도 있겠습니다.

이런 책을 읽다보면 느끼는 것입니다만, 알고리즘의 개선은 알고리즘이 실제로 적용될 데이터와, 알고리즘이 돌아갈 시스템에 대한 깊은 이해가 없이는 성취하기 힘든 것이 아닌가 하는 생각이 듭니다. 그런 것들을 이해한 뒤에야, 결국 "문제 그 자체"를 제대로 이해했다고 말할 수 있다는 것이죠. 결국 우리가 알고리즘을 통해 풀어야 하는 문제는, 알고리즘과 데이터, 그리고 시스템에 걸쳐 퍼져 있음을 이해해야 한다는 뜻이 되겠군요.

각설하고.

이 책의 8장 4절을 보면 O(n)의 복잡도를 갖는 scanning 알고리즘이 나와 있습니다. 이 부분을 보기 전에 저도 같은 문제를 (아무 생각없이) Ruby로 한 번 풀어봤습니다. 제가 알고리즘을 구현할 때 착안한 점은 다음과 같습니다.

부분합이 음수가 되면, 그 때 까지 계산한 부분합은 버려도 된다
그 아이디어를 대락 십분 정도 걸려서 구현하고, 정확성을 검증한 다음에, 책에 나온 알고리즘과 성능 비교를 한 번 해봤습니다. 소스 코드는 다음과 같습니다. 원래 책에 나온 대로 구현한 알고리즘이 first_version이고, 제가 구현한 형태의 알고리즘이 second_version입니다.

def make_array(size)
  array = []
  size.times do
    array << rand(10000) - 5000
  end
  return array
end

def max(l, r)
  return (l>r)?l:r
end

def first_version(array)
  maxsofar = 0
  maxendinghere = 0
  for i in (0..array.length-1)
    maxendinghere = max(maxendinghere + array[i], 0)
    maxsofar = max(maxsofar, maxendinghere)
  end
  return maxsofar
end

def second_version(array)
  sum = 0
  left = 0
 
  max_sum = 0
  max_left = 0
  max_right = 0
 
  for i in 0 .. array.length - 1
    sum  = sum + array[i]
    if ( sum < 0 )
      sum = 0
      left = i+1
    elsif ( sum > max_sum )
      max_sum = sum
      max_left = left
      max_right = i
    end
  end

  return array.length, max_sum, max_left, max_right
end

def print_values(*value_array)
  (0..value_array.length-1).step(1) do |i|
    print value_array[i]
    if ( i != value_array.length-1 )
      print ", "
    end
  end
  puts ""
end

#
# main starts
#

(10000..150000).step(10000) do |i|
 
  test_array = make_array(i);
 
  start_time = Time.now.to_i
  max = first_version(test_array)
  end_time = Time.now.to_i
 
  print_values("f", test_array.length, max, (end_time - start_time))
 
  start_time = Time.now.to_i
  len, max, left, right = second_version(test_array)
  end_time = Time.now.to_i
 
  print_values("s", len, max, left, right, (end_time - start_time))
end

성능 비교 결과는 다음과 같습니다. 원래 알고리즘의 실행 결과는 그 줄 앞에 "f"가 붙어 출력되고, 제가 만든 알고리즘의 실행 결과는 그 줄 앞에 "s"가 붙어 출력되므로 확인하기 어렵지는 않습니다.

f, 10000, 671773, 0
s, 10000, 671773, 884, 6580, 0
f, 20000, 572515, 0
s, 20000, 572515, 1839, 13202, 0
f, 30000, 540911, 0
s, 30000, 540911, 9561, 25188, 0
f, 40000, 1074401, 0
s, 40000, 1074401, 11395, 35425, 0
f, 50000, 1138364, 0
s, 50000, 1138364, 27126, 34215, 0
f, 60000, 539056, 1
s, 60000, 539056, 19715, 29205, 0
f, 70000, 560118, 0
s, 70000, 560118, 59001, 69944, 0
f, 80000, 1785579, 0
s, 80000, 1785579, 11987, 79133, 0
f, 90000, 961688, 1
s, 90000, 961688, 57476, 82005, 0
f, 100000, 1058398, 0
s, 100000, 1058398, 38817, 73416, 0
f, 110000, 1226686, 1
s, 110000, 1226686, 62664, 107244, 0
f, 120000, 1368168, 0
s, 120000, 1368168, 77202, 119980, 0
f, 130000, 1585253, 0
s, 130000, 1585253, 30075, 100395, 0
f, 140000, 1203882, 1
s, 140000, 1203882, 43789, 99896, 0
f, 150000, 653564, 0
s, 150000, 653564, 16504, 41747, 1

그 결과, 원래 알고리즘보다 이해하기도 훨씬 낫고 (정말로?) 원래 알고리즘보다 더 많은 정보를 제공하는 알고리즘을 만들 수 있었습니다. 조금 깊이 들여다보면 알수 있는 일입니다만, 제가 구현한 알고리즘은 원래 알고리즘과 똑같은 알고리즘입니다. 소스 코드의 양만 많을 뿐이죠.

사실 제가 만든 알고리즘은 원래 이중 루프를 사용하고 있었습니다(부분합이 음수가 되면 버리는 로직이 있어서 이중 루프를 쓰더라도 선형적으로 수행될 것으로 기대했었습니다. 하지만 그렇게 하니까 최악 수행 시간이 굉장히 나빠지는 문제가 있더군요). 그런데 오늘 이 글을 적으면서 안쪽 루프가 필요 없다는 사실을 깨달았고, 결국 코드를 고쳤죠.

이 글을 적기 위해 샘플 프로그램을 만들면서 느낀 것이지만, 역시 가장 중요한 것은 알고리즘을 어떻게 만들어 나갈 것이냐 하는 문제입니다. 원래 제가 만들었던 second_version 함수의 성능은 오늘 뜯어고친 버전에 비해 그 성능이 굉장히 좋지 못했습니다. 그런 알고리즘이 누군가에게 팔릴 소프트웨어의 핵심적인 부분에 들어가 있었다면, 누구도 그 소프트웨어를 사지 않았을 것입니다.

그리고 한편으로는 이런 생각도 듭니다. 책에 나오는 O(n) 알고리즘은 사실 이해하기가 여간 어려운 것이 아닙니다. 하지만 그 알고리즘을 조금 다른 각도로 바꿔서 생각해 보면, 결국 제가 마지막으로 구현한 알고리즘과 동일한 일을 하는 알고리즘임을 깨달을 수 있습니다. 제가 알고리즘을 만들기 시작하면서 착안했던 지점과 책의 저자가 착안했던 지점은 조금 다릅니다만, 결국 알고리즘을 다듬고 다듬고 다듬어 얻은 결과물은 똑같아진 것이죠.

결국, 알고리즘을 만드는 데 있어서 중요한 것은 "문제를 끊임없이 개선해 나가려는 노력"이라는 소리가 되겠군요. 그런데 실무에서 프로그래밍을 하다 보면, 이런 사소한 진리를 망각하게 되는 일이 아주 빈번히 벌어집니다. 적당히 돌아가게 만들어 둔 알고리즘을 프로그램 안에 넣어놓고 연동시험이 끝나는 순간 그에 대해 잊어버리는 것이죠. (물론 그런 부분이 존재한다는 사실은 나중에 프로파일링 과정에서 드러나기는 하겠습니다만...)

위의 예제를 구현하면서, 새삼 제가 예전에 저질렀던 수많은 게으름의 흔적들이 떠올라 부끄러워졌습니다. 앞으로는 좀 더 열심히 해야겠어요. :-)




신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. 아.. 저두 스캐닝 알고리즘을 한참 동안 봤습니다. ^^

    2008.10.09 14:46 신고 [ ADDR : EDIT/ DEL : REPLY ]