재미있는 놀이: C, Python, Erlang으로 50000! 해보기 #2

지난 글을 쓰고 댓글에 python도 gmp를 쓰면 빠르다라는 댓글이 있었다. 뭐 그런 댓글이야 당연히 달릴 수 있다고 생각한다. 난 파이썬은 빅넘버를 지원하니까, gmp가 라이브러리로 따로 있으리라고 생각 자체를 안했으니까.

그런데 그 댓글의 말투(어투? 글투?)가 아주 기분 나빴다. 아니 기분 나쁜 정도를 떠나서 예의가 없었다. 아무리 우리가 전산쟁이고, 실력이 중요한 사람들이라지만 실력에 앞서 예의가 가장 중요하다. 욕을 한바가지 하고 싶었으나 참았다. 나도 같은 수준이 되기 싫어서.

그래서 아예 그냥 이 글을 때려 치우고 말아버릴까 싶었지만, 이왕 시작한 글이고, 또 재미있게 봐 주시는 분들도 있으니 느리긴 하지만 끝까지 써보려 한다.

제가 쓰는 글이 완전할 수는 당연히 없습니다. 전 아는 것도 없고 실력도 없는 하수니까요. 댓글에 본문의 부족한 부분을 지적하고 채워 주시는 것은 아주 좋습니다. 그렇게 하여 글이 더 풍부하고 완전해 지니까요. 하지만 글을 쓸 때 최소한의 예의는 지켜주시길 부탁드립니다.

#2. 리컬시브
리컬시브라는 것을 처음 접했을 때에 어디선가 읽은 글 중에 이런 내용이 있다.

"리컬시브는 인간이 생각하는 방식에 가깝게 프로그래밍하는 기법이다."

음... 그때나 지금이나 나는 저 주장에 동의하지 못한다. 어떻게 리컬시브가 인간이 생각하는 방식에 가까운거지? 그게 맞다면 인간인 나는 시쿼셜 프로그래밍보다 리컬시브 프로그래밍을 더 쉽게 이해해야 하면 더 쉽고 당연하게 리컬시브 코드를 작성해야 하는데, 적어도 나는 그렇지 못하다. 나한텐 시퀀셜이 더 쉽다. 아니면, 내가 이상한 것일 수도 있다. 다른 사람한테 리컬시브에 대해서 물어본적이 없으니까. 나는 어쩌면 인간보다는 컴퓨터의 동작에 더 맞게끔 사고 방식이 바뀌어 버린걸까...

내가 이 글을 쓰게된 동기를 만들어준 삽질에서 팩토리얼을 선택한 이유중 하나가 바로 리컬시브를 만들기 쉽다였다. N!이면 1부터 N까지 하나씩 늘려가면서 리컬시브 콜하거나 N부터 1까지 하나씩 줄여가면서 리컬시브 콜하면 되기 때문이다.

-C언어 리컬시브-
나는 C언어를 좋아하지만, 좋아하는 것과 어려운것은 별개다. 처음에 나는 아주 단순하게 libgmp이 mpz_t 타입의 변수를 그냥 리턴하는 코드로 리컬시브를 작성했다.

뭐 예를 들면 이런식...

mpt_t factorial(unsigned int N)
{
  if(N == 1){
    return 1;
  }else{
    return mpz_mul(N, factorial(N-1));
  }
}

그러나 C언어에서 구조체 리턴은 그렇게 호락호락하지 않다. 더구나 단순 구조체가 아니라 별도의 initialize를 해줘야만 동작하는 핸들러 형식의 구조체라면 문제는 더 복잡해 진다.

항상 말하지만 나는 실력이 없다. 코딩을 잘 못한다.그런 놈이 이런 글은 왜 쓰고 앉아 있는 건데!! 그래서 어떤 문제에 부딧히면 가장 쉬운 방법을 택한다.

나는 그냥 단순하게 초기화가 완료된 mpz_t 타입의 구조체 포인터를 리컬시브를 도는 내내 계속 가지고 다니도록 했다. 뭔가 코드가 좀 없어보이지만 어쩔 수 없다. 내 실력의 한계다.

#include <stdio.h>
#include <gmp.h>
 
void factorial(mpz_t* f, unsigned int n)
{
    if(n == 1){
        mpz_mul_si(*f, *f, 1);
    }else{
        mpz_mul_si(*f, *f, n);
        factorial(f, n-1);
    }
}
 
int main(int argc, char **argv)
{
    mpz_t facN;
    unsigned int n = 50000;
    clock_t start, end;
    double runtime;
 
    mpz_init(facN);
    mpz_set_ui(facN, 1L);
 
    start = clock();
    factorial(&facN, n);
    end = clock();
 
    printf("fac %u is\n", n);
    //mpz_out_str(stdout, 10, facN);
 
    runtime = (double)(end-start) / CLOCKS_PER_SEC;
    printf ("runtime is %f\n", runtime);
    mpz_clear(facN);
}

코드 실행 결과는 다음과 같다.

fac 50000 is
runtime is 1.510000
 
real	0m1.525s
user	0m1.508s
sys	0m0.012s
 
====
 
fac 100000 is
runtime is 6.450000
 
real	0m6.518s
user	0m6.456s
sys	0m0.012s
 
====
 
fac 150000 is
runtime is 15.070000
 
real	0m15.281s
user	0m15.013s
sys	0m0.064s
 
====
 
fac 200000 is
runtime is 27.460000
 
real	0m27.806s
user	0m27.414s
sys	0m0.068s

지난 시퀀셜 프로그래밍에서의 결과와 비교해서 조금씩 더 느리다. 흠.. 원래 리컬시브가 더 느린가? 아무래도 스택에 쭉 쌓였다가 풀리면서 계산이 들어가니까 느린것 같기도 하고.. 아니면 요상하게 포인터로 결과값을 들고다니는 코딩때문인것 같기도 하고.. 아무튼 결과는 위와 같다.

-파이썬 리컬시브-
파이썬 리컬시브는 내가 최초에 상상했던 그 코드 그대로이다. 더 개선할 것도 없고 더 변할 것도 없어 보인다. 그리고 난 계속 파이썬에서 gmp를 사용하지 않을 것이다. 언어에서 빅넘버를 지원하지 않으면 모를까, 언어에서 지원하는 기능을 굳이 라이브러리를 사용해서 강화할 필요는 없다고 생각한다. 그럴꺼면 언어 자체에서 기본으로 지원하는 기능의 성능을 올리든가!

또한 코딩 스타일 역시 파이썬 스타일로 작성하지 않고 C, python, erlang 세 언어의 스타일이 비슷해 지도록 일부러 작성할 것이다. 해당 언어별로 최적화된 코드를 작성하면 비교의 의미가 없다고 생각한다.

def factorial(N):
    if N == 1:
        return 1
    else:
        return N * factorial(N-1)
 
n = 50000
facN = factorial(n)
 
print "fac %d is %d"%(n, facN)

내가 최초에 리컬시브로 팩토리얼 프로그램을 만들어야지~하면서 다짐하며 머릿속에 그렸던 그 코드 코드 자체이다. 뭘 더 바꾼단 말인가? 시퀀셜 프로그램을 작성할 때도 그랬지만, 역시 파이썬은 개발자의 스트레스를 많이 줄여준다. 정말 좋은 언어이다. 이제 실행해 보자.

     :
     :  
File "./python_factorial_recu.py", line 5, in factorial
    return N * factorial(N-1)
  File "./python_factorial_recu.py", line 5, in factorial
    return N * factorial(N-1)
RuntimeError: maximum recursion depth exceeded

응? 예상치 못한 에러 메시지를 뱉어낸다. 하지만 본적있는 오류이다. 파이썬은 프로그램이 무한 리컬시브에 들어가서 시스템 자원을 한 없이 잡아먹으면서 뻗어버리는 사태를방지하기 위해 언어 자체적으로 일정 개수 이상의 리컬시브가 돌면 오류를 뱉으며 프로그램 동작을 중단한다. 거의 99%의 상황에서 이 오류는 매우 유용하다. 많은 경우에 프로그래머의 실수를 방지해 주고 오류를 수정하는 데에 도움을 준다. 하지만, 지금은 아니다. 지금은 프로그래머가 의도적으로 리컬시브를 원하고 있고 그 리컬시브의 개수가 파이썬에서 설정한 것보다 클 뿐이지 반드시 끝난다. 따라서 되게 만들어야 한다.

다시 구글이 필요한 시점이다. 사랑해요! 구글! 네이버에도 나올꺼야 아마..

깔끔하게 구글에서 한 번에 찾았다. 정말 구글이 없었더라면.. 개발자는(...)

C언어는 빅넘버를 처리하지 못하더니 파이썬은 리컬시브 횟수의 제한이 있다. 뭐 어쩌겠는가. 언어에서 자체적으로 가지는 제한은 회피해야지. 다시 말하지만 난 이럴때만 외부 라이브러리를 쓸 생각을 한다.gmp 따위는 파이썬에서 필요없어!

sys라이브러리의 getrecursionlimit() 함수로 현재 설정되어 있는 리컬시브 깊이의 값을 읽어오고, setrecursionlimit(limit)함수로 리컬시브 깊의 값을 재 설정할 수 있다고 한다.

궁금해서 디폴트 리컬시브 깊이 값을 출력해 봤다.

>>> import sys
>>> sys.getrecursionlimit()
1000

헐.. 1000이다. 일반적으로 리컬시브를 사용하는 것을 생각하면 충분할 것 같은데, 지금 막 50000!, 200000!을 하고 있으니 숫자가 터무니 없이 적어 보인다.

팩토리얼의 리컬시브 횟수는 팩토리얼의 인자 수 만큼이다. 다시 말해서 50000!이라면 50000번 리컬시브를 돈다. (50000-1이던가..-_-) N!이 N번 리컬시브를 돌든 (N-1)번 돌든 중요한건 아니다. 난 N번으로 설정할거니까..^^;

수정된 코드는 다음과 같다.

import sys
import time
 
def factorial(N):
    if N == 1:
        return 1
    else:
        return N * factorial(N-1)
 
n = 50000 
sys.setrecursionlimit(n)
start = time.time()
facN = factorial(n)
 
 
print "fac %d is"%(n)
print "runtime is %s"%(time.time() - start)

sys.setrecursionlimit() 함수에 리컬시브 깊이를 N으로 설정했다. 실행을 해 보면...

$ python ./python_factorial_recu.py 
세그멘테이션 오류

헐.. 이 무슨..-_-;; 이런 개같은 결과가 다 있어!!! 검색해 봤더니 무슨 스택 프레임이 깨지고 어쩌구.. 그런데 C는 잘 됐잖아!!!

조금 짜증이 밀려온다. 그래서 실험을 해 봤다.

import sys
import time
 
def factorial(N):
    if N == 1:
        return 1
    else:
        return N * factorial(N-1)
 
n = 5000 
sys.setrecursionlimit(n)
start = time.time()
facN = factorial(n)
 
 
print "fac %d is"%(n)
print "runtime is %s"%(time.time() - start)

리컬시브 깊이를 5000으로 줄였다.

  File "./python_factorial_recu.py", line 8, in factorial
    return N * factorial(N-1)
  File "./python_factorial_recu.py", line 8, in factorial
    return N * factorial(N-1)
  File "./python_factorial_recu.py", line 8, in factorial
    return N * factorial(N-1)
  File "./python_factorial_recu.py", line 8, in factorial
    return N * factorial(N-1)
  File "./python_factorial_recu.py", line 8, in factorial
    return N * factorial(N-1)
RuntimeError: maximum recursion depth exceeded

윙? setrecursionlimit()가 안먹은건가?

아.. 짜증나.. 안할래!

-얼랭 리컬시브-
얼랭은 리컬시브로 작성하는 것이 너무 자연스럽다. 언어의 특성이란 이런것일까. 오히려 코드 자체는 전편에 억지로 만들었던 시퀀셜보다 더 단순하다. 그리고 왠지 속도도 빠를것 같다는 느낌이 든다. 리스트를 별도로 만들 필요 없이 리컬시브 돌면서 리턴 값을바로 곱하는데 사용하기 때문이다.

-module(erlang_factorial_time).
-export([start/0]).
 
start()->
    N = 200000,
    Start = now(),
    F = factorial(N),
    End = now(),
    Runtime = timer:now_diff(End, Start) / 1000,
    io:format("fac ~w~n", [N]),
    io:format("runtime is ~w~n", [Runtime]).
 
factorial(1)->1;
factorial(N)->N * factorial(N-1).       

얼랭은 함수에 매개변수가 전달되는 순간 해당 매개변수가 유효한지 판단한다. 얼랭에서는 이를 패턴매칭이라고 한다. 그래서 C언어나 파이썬과 달리 if 조건문 없이 리컬시브 종료 조건을 코딩할 수 있다.

결과는 다음과 같다.

fac 50000
runtime is 8550.361
 
real	0m9.771s
user	0m8.573s
sys	0m0.024s
 
====
 
fac 100000
runtime is 35193.671
 
real	0m36.405s
user	0m34.014s
sys	0m0.116s
 
====
 
fac 150000
runtime is 96230.144
 
real	1m37.459s
user	1m34.274s
sys	0m0.360s
 
====
 
fac 200000
runtime is 160798.681
 
real	2m42.019s
user	2m37.202s
sys	0m0.604s

역시 지난 시간 측정했던 시퀀셜보다 리컬시브의 결과가 얼랭에서도 조금씩 더 느렸다.

-결론-
전체적으로 리컬시브는 시퀀셜보다 느렸다. 그리고 파이썬에서 리컬시브를 쓰기는 굉장히 빡친다. 다음에 디바이드앤 컨커를 할 때에나 파이썬으로 제대로된 결과를 뽑아낼 수 있을 것 같다.

CPU 사용량은 전체적인 추세가 지난번 시퀀셜 프로그래밍 때와 다르지 않았다. 따라서 따로 그림을 넣진 않겠다. 절대 귀찮아서 이러는거 아니다.

-다음 시간 예고-
오늘 작성한 C언어, 파이썬, 얼랭 버전의 리컬시브 팩토리얼 코드를 디바이드 앤 퀀커 스타일로 바꿔서 실행 시간을 측정하고 비교해 본다. 디바이드 앤 퀀커로 어떻게 바꾸는지에 대한 전략은 뻔하다.

N!을 1부터 K, K+1부터 P, P+1부터 Y, Y+1부터...... 이런식으로 N!을 일정 크기의 구간으로 나눈 다음 각 구간의 팩토리얼을 계산한다. 각 구간의 팩토리얼 계산이 완료되고나면 모든 결과를 곱해서 최종 결과를 계산해 낸다.

여기서 나는 한 가지 실험을 추가로 더 해 볼것이다. N!에서 N의 크기를 바꿔가면서 시간을 측정했던 기존 측정에 더해서 각 구간의 크기 P를 바꿔가면서 시간을 측정해 볼 예정이다. 어떤 결과가 나올지는 아직 모른다.