메뉴 바로가기 검색 및 카테고리 바로가기 본문 바로가기

한빛출판네트워크

IT/모바일

펄(Perl)의 최적화

한빛미디어

|

2002-02-28

|

by HANBIT

8,201

저자: (Robert Spier), 역 이호재

당신이 만든 펄 프로그램 수행 시간이 너무 길다면, 이는 대부분 수행 시간이 오래 걸리는 데이터 구조나 알고리즘을 사용했기 때문이다. 여러분은 함수 구현 방법에 대해 다시 한번 생각해 봄으로써, 속도 향상에 큰 도움을 얻을 수 있을 것이다.

간단해 보이지만 복잡한 이론

속도 향상에 대해 말하기 전에, 어떤 것에 얼마의 시간이 걸리는지를 표현할 수 있어야 한다. 알고리즘을 사용에는 입력값이 다양하기 때문에, 어떤 일을 하는데 걸리는 실제 시간 측정이 불가능할 때도 있다. 때때로 컴퓨터 과학자나 수학자들은 어떤 일의 수행 시간 양의 차수를 측정하는데 있어 big-O라고 부르는 시스템을 사용한다. 하지만 Big-O 표기법은 가장 좋지 않은 분석법이다. 최소한의 수행시간과 실제 수행 시간을 측정할 수 있는 여러 가지 방법이 있기 때문이다.

Big-O를 이해하는데 있어 컴퓨터 학자나 수학자들의 말에 두려워 할 필요는 없다. 이제부터 초, 분, 시, 일(日) 또는 1, 10, 100, 1000 등의 수행 차수의 차이를 표현하는 방법에 대해서 논할 것이기 때문이다. 그리고 이것을 이해하기 위해 이해하기 어려운 수학을 알 필요는 없다.

Perl in a Nutshell
이는 아주 간단하다! 함수 수행시간이 상수라면, 이는 O(1)로 표현된다(알파벳 대문자 O). 여기서 상수라는 것은 아무리 많은 데이터나 입력을 처리한다 하더라도 수행 시간이 변하지 않는다는 것을 의미한다.

수행시간이 입력 양과 직접적으로 관계가 있다면(선형적이라면) 이는 O(n)이라 표현한다. 입력이 두 배만큼 증가하면 수행 시간도 두 배만큼 증가한다. O(n^2) 이거나 O(n^3), 또는 이 이상인 함수들도 있다.

우리는 지금 양의 차수에 대해 알아보고 있다. 왜냐하면 차수가 수행시간에 큰 영향을 미치기 때문이다. 그래서 상수항이나 작은 차수는 무시 할 수 있다. O(2n)O(n)은 같은 표현이다. 물론 O(n+1)O(n)도 같고 O(n^2+n)O(n^2)도 같은 것을 표현한 것이다. 작은 차수는 큰 차수에 비해 중요하지 않다.

코드를 분석해서 big-O를 알아낼 수도 있지만 big-O를 알아내는 가장 간단한 방법은 데이터에 대해 얼마나 많이 반복(iterate) 처리하는가를 살펴보는 것이다. 데이터를 반복해서 처리하지 않는다면 이는 O(1)이다. 데이터에 대해 한번 반복 수행한다면 이는 O(n)이다. 만약 두개의 중첩된 반복문이 있다면 이는 아마도 O(n^2)일 것이다.

예제 1: 그래핑

필자는 프로젝트를 위해 새로운 그래프 모듈을 개발했다. 기존의 모듈은 너무 비효율적이었고 또한 꼭 필요한 기능은 지원하지 않았기 때문이다. 모듈 구현은 아주 쉬웠고 잘 작동했다. 하지만 그래프가 너무 커질 경우 사정은 달라진다. 서브그래프의 의존성 검사를 해야 했는데 1,000개의 노드를 가진 그래프를 P3 1Ghz 컴퓨터에서 계산하는데 2분이 넘게 걸렸다. 그때 필자는 계산 속도가 더 빨라지기를 바랬고, 만약 속도가 더 빨라지지 않는다면 사용자들이 짜증이 날 것도 분명했다.

첫 그래프 모듈은 아래와 같다.(중요한 부분만 보여주기 위해 실제보다 간단하게 하였다.)

 package Graph; # for Directed Graphs
 use strict;
 sub new {
  my $this = { edges => [],
               vertices => {} };
  bless $this, "Graph";
 }
 sub add_edge { # from x to y
  my ($this,$x,$y) = @_;
  $this->{vertices}{$x}++;
  $this->{vertices}{$y}++;
  push @{$this->{edges}},[$x=>$y];
 }
 sub in_edges {
  my ($this,$v) = @_;
  grep { $_->[1] eq $v } @{$this->{edges}};
 }
add_edge 함수는 노드(node)나 에지(edge)의 양에 상관없이 같은 수행 시간이 걸리기 때문에 O(1)이다. in_edges 함수는 그래프 안의 각 에지를 반복(iterate)하기 때문에 O(n)이다. (반복은 그래프 "내부"에 있다.)

코드에서 문제가 있는 부분은 다음과 같다.

 sub flat_subgraph {
    my ($graph,$start) = @_;
    my %seen;
    my @worklist = ($start);
    while (@worklist) {
      my $x = shift @worklist;
      $seen{$x}++;
      push @worklist, $graph->in_edges($x) unless $seen{$x};
    }
    return keys %seen;
 }
 
그리고 많은 꼭지점(vertex)을 위해 다음과 같이 해야 했다.

  my %dependencies;
  for (keys %{$graph->{vertices}}) {
   $dependencies{$_} = [ flat_subgraph( $graph, $_ ) ];
  }
 
이 코드는 간단한 동작을 O(n^3)으로 만들어 버린다. (의존성 반복문은 O(n)이고, flat_subgraph는 O(n)이고, in_edges는 O(n)이다.) 이는 그래프가 커지면 커질수록 계산하는데 훨씬 더 많은 시간이 걸린다는 것을 의미한다(1,8,27,64와 같은 값을 가지고 있는 곡선을 상상해보라. 기하급수적으로 커지는 것을 알 수 있을 것이다.).

캐싱하기

사용자들이 즉각적인 피드백을 기대하듯이, 어떤 조치든지 취해져야 한다. 필자가 시도한 첫번째 방법은 in_edges 계산을 캐싱하는 것이었다.

 sub in_edges {
  my ($this,$v) = @_;
  if (exists $this->{cache}{in_edges}{$v}) {
      return @{$this->{cache}{in_edges}{$v}};
  } else {
    my @t = grep { $_->[1] eq $v } @{$this->{edges}};
    $this->{cache}{in_edges}{$v} = [@t];
    return @t;
   }
 } 
이는 도움은 되었지만, 기대했던 것 만큼은 아니었다. in_edges 계산의 경우 캐싱되지 않을 때는 여전히 수행시간이 오래 걸렸다. 최악의 경우에는 여전히 O(n)이고 캐쉬되었을 때는 O(1)이다. 여기에서 전체 동작 시간은 평균적으로 O(n^2)O(n^3) 사이라는 것을 알 수 있다. 하지만 아직도 느리다.

동일 함수를 동일 인자로 호출할 때에는 캐싱이 유용하다. 마크-제이슨 도미누스(Mark-Jason Dominus)라는 분이 Memoize라고 불리는 모듈을 개발했는데, 이는 캐싱 함수 작성이 쉽도록 해준다. 더 많은 정보를 원한다면 http://perl.plover.com/MiniMemoize/에서 알 수 있다.

구조 바꾸기

필자가 시도한 다음 방법은 그래프 자료 구조를 바꾸는 것이었다. 처음에 이것을 디자인했을 때 필자의 목표는 빠른 속도가 아니라 단순함이었다. 하지만 지금 와서는 속도가 중요하게 되었고 따라서 무언가를 바꿔야만 한다.

필자는 새로운 에지(edge)가 추가될 때마다 in_edges가 수행되도록 그래프를 수정하였다.

 package Graph; # for Directed Graphs
 use strict;
 sub new {
  my $this = { edges => [],
               vertices => {},
               in_edges => {} };
  bless $this, "Graph";
 }
 sub add_edge { # from x to y
  my ($this,$x,$y) = @_;
  $this->{vertices}{$x}++;
  $this->{vertices}{$y}++;
  push @{$this->{in_edges}{$y}}, $x;
  push @{$this->{edges}},[$x=>$y];
 }
 sub in_edges {
  my ($this,$v) = @_;
  return @{$this->{in_edges}{$v}};
 }
add_edge는 전과 마찬가지로 O(1)이다. in_edges는 지금은 O(1)이 되었다. 이제 수행시간이 에지(edge)의 수에 따라 변하지 않는다.

이것이야 말로 필자가 필요로 하는 솔루션으로 4분이 걸리는 일을 단지 6초 만에 끝낼 수 있게 하였다.

훌륭한 인터페이스의 중요성

이러한 속도향상을 간단히 이룰 수 있는 이유 중 하나는 그래프 모듈 인터페이스를 잘 디자인했기 때문이다. 인터페이스는 내부의 세부적인 사항을 감추었고, 이로 인해 다른 구현을 끼워넣을 수 있었다. (이는 필자가 실제로 테스트하는 방법이다. 필자는 일반적인 그래프인 Graph::Cached와 빠른 Graph::Fast를 가지고 있다. 일단 Graph::Fast가 가장 좋다고 생각되면, 이를 Graph로 이름만 바꾸면 된다.)

필자는 지금까지 해왔던 방법으로 그래프를 디자인할 수 있어서 좋았다. 그래서 간단함과 디자인을 우선하여 그래프를 디자인했다. 다음과 같은 구절을 들은 적이 있을 것이다. "시기상조의 최적화는 가장 나쁜 것을 낳는 근본이 된다." 만약 필자가 먼저 그래프 모듈을 최적화하려 했다면, 모든 경우에 동작하지 않는 좀 더 복잡한 코드를 만드는 것으로 끝났을 것이다. 첫번째 그래프에서 그 구현은 느렸지만, 동작은 확실히 했다. 최적화는 나중에 이루어졌고, 이미 이때에는 적절한 동작을 보장할 수 있는 기본을 갖게 되었다.

예제 2: 중복 메시지 필터

코드를 항상 극단적으로 최적화 해야 할 필요는 없다. 최적화된 코드는 시간과 에너지를 소비하기 때문에 항상 그럴만한 가치가 있는 것이 아닐 수도 있다. 만약 프로그램 수행시간 2초를 줄이기 위해 이틀을 소비한다면 이 또한 바보같은 짓임에 틀림없다. (물론 하루에 수 백번씩 돌리는 프로그램이 아니라면 말이다.) 이미 충분히 빠른 프로그램을 더 빠르게 만드는 일이 현재 가장 가치 있는 일이라고는 볼 수 없다.

두 번째 예제는 e-mail을 위한 중복 메시지 필터이다. 등록되어 있는 메일링 리스트에서 받은 메시지를 참조로 하여 중복해서 받을 경우 중복된 메시지가 발생하는데, 이 필터를 사용하면 이를 방지할 수 있다.

필터에 담겨진 일반적인 개념은 간단하다.

skip $message if seen $message->id;
$message->id가 있다면 $message를 무시해라. 여기서 관심있는 함수는 id가 있는지를 보는 함수이다. 이는 어떤 형태로 캐시된 id를 검색한다. 메일 필터의 속도는 우리가 이를 어떻게 구현하느냐에 따라 크게 좌우된다. (펄로 메일을 필터링하는 데 있어 더 자세한 정보를 원한다면 Mail::Audit를 살펴보기 바란다.)

id를 검색하는 함수를 구현하는 확실한 두 가지 방법은 간단한 선형적 검색(O(n))과 검색을 위한 영구적인 데이터베이스/해시 테이블을 사용하는 방법(O(1))이 있다. 필자는 예전의 message_id를 삭제하는 등의 데이터베이스 유지 비용은 무시하겠다.

선형적인 방법은 message_id를 어떤 종류의 구분자로 구분하면서 기록하는 것이다. 몇몇 프로그램은 널 바이트를 이용하고 어떤 것은 엔터(newline)을 이용한다.

데이터베이스/hash 메소드는 DBM이나 버클리 DB같은 이진 데이터베이스에 message_id를 저장하는 것이다. 디스크 공간은 좀 더 많이 차지하지만 검색은 보통 더 빨라진다.

하지만! 여기엔 고려해야 할 한 가지 사항이 더 있다. 바로 오버헤드(overhead)이다. 선형 검색에는 작은 오버헤드가 있지만 DB 파일에는 큰 오버헤드가 있기 때문이다(여기서 오버헤드는 파일을 열고 적당한 자료구조를 초기화 하는데 걸리는 시간을 의미).

비교표

 레코드 | 비고
 -------------------------------
   100  | 선형이 415% 더 빠르다.
   250  | 선형이 430% 더 빠르다.
   500  | hash가 350% 더 빠르다.
  1000  | hash가 690% 더 빠르다.
필자는 위의 방법들을 P2 400 컴퓨터에서 구현해서 실행하여 위와 같은 결과를 얻었다. 선형 검색에 있어 캐시에 있는 메시지의 개수가 250개를 넘어서면 속도가 갑자기 저하되지만, 해시 검색은 속도가 상수로 변하지 않고 유지된다.

큰 그림으로 다시 돌아와, 우리는 사용할 함수를 결정할 때 message_id 캐시 사이즈를 고려해야 한다. 대개 이러한 종류의 캐쉬를 구성할 때 모든 항목을 다 저장할 필요는 없다. 평균 2일이나 3일 정도의 시간이면 중복된 메시지를 찾아낼만한 가치가 있을 것이다(아마도 대부분의 경우에는 하루 정도면 적당).

이러한 문제에 있어 O(1)을 구현할 수도 있겠지만 그 수행 시간은 O(n)의 경우보다 더 오래 걸릴 것이다. 두 경우 모두를 구현하는 것도 쉽지만, 어떤 상황에서는 O(1)을 구현하는 것이 어려울 수도 있고, 또 그렇게 구현할만한 가치가 없을 수도 있다.

결론

펄은 강력한 언어이지만 프로그래머가 바보같은 결정을 내렸을 경우 자신의 발등을 찍는 행동을 막을 수는 없다. 펄을 사용하는데 있어서 발생할 수 있는 가장 큰 문제점은 잘못된 자료구조나 알고리즘을 채택하는 것이다. 약간 복잡해보이는 이론을 사용해 봄으로써 코드를 최적화하고 큰 속도 향상을 얻을 수 있다.

필자는 big-O 표기법과 복잡한 이론의 겉만 살펴보았다. 이는 수학과 컴퓨터의 매우 까다로운 면까지 탐구해야 하는 고도의 연구 분야이다. 하지만 필자는 이 기사가 여러분에게 기본적인 개념을 전달해 주었기를 바란다.

위에서 살펴 본 두 번째 예제는 최적화를 위해 많은 시간을 소비할 필요가 없는 예제이다. 최고로 최적화하는 것이 항상 가치 있는 일은 아니라는 점도 알아두기 바란다.

더 자세한 정보
검색엔진 Google
http://www.google.com/search?q=big-O+complexity

전산 이론 소개
Part Three of Sipser, Michael. "Introduction to the Theory of Computation". PWS Publishing Company. Boston, MA. 1997.

Algorithms and Complexity, Internet Edition
http://www.cis.upenn.edu/~wilf/AlgComp2.html
TAG :
댓글 입력
자료실