Extremely Agile

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

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

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