러시안 페인트공 알고리듬

 오래전 조엘 스폴스키 의 책을 보면서 여러 가지를 배웠습니다. 그중 하나가 러시안 페인트공 알고리듬이었습니다. 지금은 아마도 누군가에게 책을 빌려 준거 같고, 개요만 머릿속에 남아 있습니다. 기억을 더듬어 알고리듬을 설명하고, 해결 방법과 함께 짧은 포스팅을 하려고 합니다.

러시안 페인트공 알고리듬(정확한 내용이 필요하시면 책을 보시거나, 조엘의 블로그를 보거나, 다른 분들의 포스팅을 보세요. )

 어떤 건설 업자가 도로를 만들었습니다. 긴 도로가 완성되고, 이제 남은 일은 도로에 차선을 그리는 일입니다. 마침 도로의 시작위치에 러시안 페인트공이 운영하는 페인트 가게가 있습니다. 업자는 러시안 페인트공에게 차선을 그리는 일을 맡겼습니다.

 첫째날 러시안 페인트공은 300미터의 차선을 그립니다. 업자는 결과에 만족해서 원래 책정한 임금보다 많은 임금을 줍니다.

 둘째날 러시안 페인트공은 150미터의 차선을 그립니다. 업자는 실망스러웠으나, 그래도 첫날 주었던 임금을 줍니다.

 셋째날 러시안 페인트공은 30미터의 차선을 그립니다. 업자는 분노했습니다.

 업자는 페인트공에게 항의합니다.

 " 난 첫째 날 당신의 실적을 보고 당신에게 많은 임금을 주었으며, 둘째 날은 실망스러웠지만 임금을 삭감하지 않았는데, 오늘은 심지어 첫째 날의 1/10밖에 못 그리다니, 어떻게 된 것이냐? "

 러시안 페인트공은 울먹이며, 이야기 합니다.

 " 저도 어쩔 수 없습니다. 제가 그런 차선이 길어질수록 제가 가게에 페인트를 가지러 가는 시간이 길어집니다."

 

 이게 러시안 페인트공 알고리듬입니다. 이전 작업의 정보를 무시하고, 처음부터 작업함으로써 알고리즘의 성능을 저하시키는 것이죠. 이 알고리즘은 누구나 배우는 기본 알고리즘에 들어 있습니다. 바로 strcat죠. 아래 예제를 통해 자세한 설명을 추가하겠습니다.

#include <cstring>
#include <chrono>
#include <iostream>

using namespace std;

char * solveStrCat(char * dest, char *src){
    strcat(dest, src);

    return dest + strlen(src);
}

int main(int argc, char ** argv){
    chrono::time_point<chrono::high_resolution_clock> tTime;
    chrono::time_point<chrono::high_resolution_clock> sTime;
    chrono::time_point<chrono::high_resolution_clock> eTime;

    double cTime;
    double bTime;
    double ctTime;

    char * strArr;

    char a = 'a';

    bTime = 0.;

    strArr = (char *)malloc(1024 * 1024);

    // 러시안 페인트공
    tTime = chrono::high_resolution_clock::now();
    for(int i = 0 ; 1000 >= i ; i++){
	sTime = chrono::high_resolution_clock::now();
	for(int j = 0 ; 1024 > j ; j++){
	    strcat( strArr, &a);
	}
	eTime = chrono::high_resolution_clock::now();
	cTime = static_cast<double>((chrono::duration_cast<chrono::milliseconds>(eTime - sTime)).count());
	ctTime = static_cast<double>((chrono::duration_cast<chrono::milliseconds>(eTime - tTime)).count());

	if(0 == i%100){
	    cout << i << " : " << cTime << " msec\t" << ctTime - bTime << " msec\t" << ctTime << " msec"<< endl;
	    bTime = ctTime;
	}
    }

    memset(strArr, 0, 1024 * 1024);

    char * strPtr = strArr;
    bTime = 0.;

    // 러시안 페인트공 해결
    tTime = chrono::high_resolution_clock::now();
    for(int i = 0 ; 1000 >= i ; i++){
	sTime = chrono::high_resolution_clock::now();
	for(int j = 0 ; 1024 > j ; j++){
	    strPtr = solveStrCat( strPtr, &a);
	}
	eTime = chrono::high_resolution_clock::now();
	cTime = static_cast<double>((chrono::duration_cast<chrono::milliseconds>(eTime - sTime)).count());
	ctTime = static_cast<double>((chrono::duration_cast<chrono::milliseconds>(eTime - tTime)).count());

	if(0 == i%100){
	    cout << i << " : " << cTime << " msec\t" << ctTime - bTime << " msec\t" << ctTime << " msec"<< endl;
	    bTime = ctTime;
	}
    }

    return 0;
}

 코드의 대부분은 시간을 측정하기 위한 코드이고, 실제 구동 코드는 복잡하지 않습니다. 그저 strArr이라는 배열에 'a'를 strcat으로 추가합니다. 1024번씩 1000회 추가하는데 1회마다 시간을 측정합니다. 전부 출력하면 결과를 보기 어려우니, 100회마다 1회 구동 시간, 100회 구동 시간 그리고 누적 구동 시간을 출력합니다.

 strcat 함수는 두 문자열을 합쳐 주는 함수입니다. 첫 문자열의 끝을 찾은 뒤, 두 번째 문자열을 붙여줍니다. 길이가 10인 문자열과 100,000인 문자열을 다룰 때, 구동 시간은 당연히 달라집니다. 첫 문자열의 끝을 찾는 작업이 러시안 페인트공 알고리듬이 되는 거죠. 

 상기 알고리즘을 해결하기 위해 solveStrCat함수를 만들어 줍니다. 이 함수는 결과 문자열의 끝 위치를 반환합니다. 이 위치를 이용하면, 러시안 페인트공 알고리즘을 해결하게 되죠. 효과는 아래 스냅숏과 같습니다.

 위는 strcat을 쓰는 경우이고, 아래는 solveStrCat을 쓰는 경우입니다. strcat을 이용한 경우 처음부터 100회까지는 134 msec가 소요되지만 900에서 1000회 까지는 2,862 msec가 소요되었습니다. 러시안 페인트공 알고리듬은 이렇게 같은 연산을 하는 코드임에도 입력 변수의 상태에 따라 구동 시간이 길어지게 됩니다.

 solveStrCat은 문자열의 끝을 알고 있기 때문에 끝을 찾기 위한 연산이 없어지고, 문자열을 붙이는 연산만 수행하게 됩니다. 결과적으로 문자열의 길이가 길어져도 문제는 발생하지 않게 되죠.

 러시안 페인트공 알고리듬은 개념적으론 간단한 알고리듬입니다. 이게 뭐야? 하는 생각이 들 수도 있죠. 하지만 제가 이 개념을 배울 때 조엘 스폴스키에게서 배운 것은 소프트웨어 엔지니어의 자세입니다. 소프트웨어 엔지니어는 코드를 만들 때, 항상 코드의 구동 시간을 정확히 알아야 합니다. 러시안 페인트공 같은 성능 저하 알고리듬은 어디에든 숨어 있을 수 있죠. 항상 코드의 효율성을 생각하고, 문제가 될만한 부분은 미리 해결해 두는 자세를 기릅시다.