한빛출판네트워크

저자: 김대곤(private @ roadtohome.com)

7월에는 한빛에서 출간하는 알고리즘 관련도서를 한 권 만날 수 있을 것으로 생각된다. 그 책에 대한 따근따근한 기사도 올라와 있다. 이 기사에서는 다른 알고리즘 관련 도서와 마찬가지로 알고리즘(설계)가 중요하다고 말한다. 전적으로 동의하는 바이다. 알고리즘은 중요하다.

하지만, 전산 경력이 6년이 넘어가도록 알고리즘이 문제가 되었던 적은 알고리즘 관련 수업에서 나오는 과제와 소프트웨어 엔지니어링 수업에서 나온 이상한 과제를 할 때 뿐이었다. 그렇게 중요한 것이라면, 경력의 대부분을 차지하는 현장 경험에서는 왜 알고리즘이 중요하는 사실을 몰랐을까? 적어도 알고리즘을 사용하지 않았을리는 없고, 그렇다면 남들이 해서 숨겨 놓은 알고리즘을 나도 모르게 사용한 것이 아닐까 생각된다. 이런 일들이 가장 잘 일어나는 곳은 데이터베이스와 자바 패키지가 아닐까 생각된다. 데이터베이스는 정렬과 Search를 단 몇 단어로 가능하게 만들지만, 정렬과 Search는 알고리즘에서 가장 중요한 분야 중에 하나이며, 아직도 연구가 끝나지 않은 분야이다. 자바에서 제공하는 표준 API중에도 알고리즘을 제공하는 것이 많다.

자바 표준 API 중에서 java.util 패키지는 알고리즘과 항상 단짝이 되어 나오는 자료 구조(Data Structure)의 Implementation들을 제공하는데, 그 중에 하나가 Vector이다. 실제 얘기에 들어가기 전에 몇 가지 재미난 데이터를 살펴보자.



위 그래프는 VectorTest.java의 실행결과를 보여주고 있다. 아래 데이터는 VectorInd.java의 실행결과를 보여주고 있다.

mmgt; java VectorInd 1000000
Insert Time [749] : 11
Insert Time [61480] : 6
Insert Time [122880] : 48
Insert Time [245760] : 70
Insert Time [491520] : 113
Insert Time [983040] : 215
Insert Time [983917] : 18

소스에서도 알 수 있듯이, 그래프는 각 데이터 크기만큼 Vector에 add를 한 것이고, 변화 폭이 큰 것은 입력되는 위치가 Vector의 처음이고, 아래 그래프는 입력되는 위치가 Vector의 마지막이다. 똑같은 데이터를 입력하지만, 실행 속도는 엄청나게 차이가 난다. 이것을 알고리즘에서 사용하는 용어로 표현하면, 전자의 수행속도는 O(n*n), 후자는 O(n)로 표현된다. 루프를 제외하면, 각각 add에 걸리는 시간은 O(n), O(1)이다. 아래 두 그림은 그 차이를 보여준다.



위의 그림은 마지막에 입력되는 경우를 보여주고, 아래 그림은 첫번째 위치에 입력되는 경우이다. 아래의 경우에는 입력되어 있는 데이터의 수만큼 데이터가 이동해야 한다. 만약, 10번의 입력이 일어나면, 실제로는 10 + 9 + 8 + … + 2 + 1 = 10 * 9 / 2 번의 시간이 걸니는 것이다. 데이터가 커지면 커질수록 치루어야 하는 대가는 급속하게 커진다.

정말 모든 addLast가 일정한 시간이 들어가는지를 보여주는 것이 VectorInd.java이다. 데이터 입력 시간이 3 millisecond 이상 들어가는 경우에 소요된 시간을 프린트한 것이다. 백만번 중에 7번 발생했다. 처음과 마지막 데이터를 제외하면, 데이터가 두 배가 되어질 때 시간이 많이 걸리는 현상이 발생했다. 그 이유를 그림으로 설명하면 다음과 같다.



사용자에게 보이지는 않지만, Vector는 데이터를 저장하기 위해 Array를 만들었다. 만든 Array의 사이즈는 무한하지 않기 때문에 데이터를 계속 입력하면, 공간이 부족하게 되고, Vector는 이 때 원래 사이즈의 두 배의 크기의 Array를 만들고, 가지고 있던 데이터를 새로운 Array로 이동시킨다. 즉, Array에 데이터가 입력될 때, Array가 부족하면 기존에 저장된 데이터의 크기(Array 사이즈) 만큼의 데이터 이동이 일어나게 된다. 위 자료에서 보듯이, 데이터 사이즈가 두 배에 도달할 때마다 약 2 배 가량의 시간이 더 걸리는 것을 볼 수 있다.

이때가지의 관찰결과에 따르면, Vector의 인덱스가 작은 쪽에는 입력하는 것도, 삭제하는 것도 좋지 못하다. 그만큼의 댓가(실제 데이터 사이즈 - Index만큼의 데이터 이동)를 치루어야 하기 때문이다. 그리고, 데이터가 입력되는데 걸리는 시간을 반드시 일정한 시간이하로 낮추어야 하는 경우에는 일반적인 Vector를 사용할 수 없다.

실제로 Vector는 인덱스 관리가 편리한 Array에 불과한 것을 알 수 있다. 하지만 Array 작업시 문제가 되는 것들은 여전히 Vector에서도 문제가 된다. 그러므로 처음 넣은 데이터를 가장 먼저 지워야 되는 일에는 Vector를 사용하지 않는 것이 좋다. 이 작은 사실 하나가 위 그래프에서 볼 수 있듯이 데이터가 많은 경우, 실제 프로그램의 실행속도에는 엄청난 영향을 미치게 된다.

Note : VectorInd의 작업결과는 리눅스에서 실행한 것이다. 필자의 윈도우에서는 다른 실행결과가 나왔다. 출력되는 데이터의 모든 시간은 10이였다.

Appendix A

[VectorTest.java]

import java.util.Vector;
import java.util.Calendar;

public class VectorTest {

    public static void main(String[] args) {

         Vector target      = new Vector();
         String obj          = new String("Vector Data");
         Calendar   start, end;
         long    interval   = 0;
         long    LIMIT       = 0;
         int      index       = 0;

         long    MAX = Long.parseLong(args[0]);
         
         for ( LIMIT = MAX / 10 ; LIMIT <= MAX ; LIMIT = LIMIT + MAX/10 ) {
             start = Calendar.getInstance();
             for ( index=0 ; index < LIMIT ; index++) {
                  target.add(index, obj);
             }
             end    = Calendar.getInstance();

             interval = end.getTimeInMillis() - start.getTimeInMillis();
             System.out.println(index + " " + interval);
             target = new Vector();
         }

         System.out.println("===========================");

         for ( LIMIT = MAX / 10 ; LIMIT <= MAX ; LIMIT = LIMIT + MAX/10 ) {
             start = Calendar.getInstance();
             for ( index=0 ; index < LIMIT ; index++) {
                  target.add(0, obj);
             }
             end    = Calendar.getInstance();

             interval = end.getTimeInMillis() - start.getTimeInMillis();
             System.out.println(index + " " + interval);
             target = new Vector();
         }
    }

   
}


[VectorInd.java]

import java.util.Vector;
import java.util.Calendar;

public class VectorInd {

    public static void main(String[] args) {
   
         Vector target = new Vector(30);
         Object obj      = new Object();

         Calendar   start, end;
         long         interval = 0;

         int LIMIT = Integer.parseInt(args[0]);

         for ( int index = 0 ; index <= LIMIT ; index++ ) {
             start = Calendar.getInstance();
             target.add(obj);
             end    = Calendar.getInstance();
             interval = end.getTimeInMillis() - start.getTimeInMillis();
             if ( interval > 3 ) {
                  System.out.println("Insert Time : " + interval);
             }
         }

    }
}