재미있는 놀이: C, Python, Erlang으로 50000! 해보기 #3
-분할 정복-
디바이드 앤 컨쿼를 번역해서 분할 정복이라고 책에 많이 써 있다. 디바이드앤 컨쿼라는 영어 단어를 그대로 직역한 것이다. 어떤 커다란 계산이 필요한 문제가 있을 때, 이 문제를 잘게 쪼개서 개별적으로 계산한 다음 그 계산 결과를 합쳐서 최종 결과를 만들어내는 접근 방법의 통칭이다. 쉽게 말해 각개격파하는 것이다. 한 덩어리로 계산하면 땀나고 빡센 문제를 작게 쪼개서 빨리 빨리 계산함으로써 전체적인 효율을 높인다는 전략이다. 아주 좋은 전략이고 실제로 효과도 있다. 하지만 컴퓨터 프로그램을 만들면서 마주하는 많은 문제들을 모두 디바이드앤 컨쿼 전략으로 해결할 수 없다. 디바이드앤 컨쿼가 되는 문제가 있고 안되는 문제가 있다. 다행이도 지금 계속하고 있는 팩토리얼 문제는 디바이드앤 컨쿼 전략에 아주 잘 어울린다. 사실 디바이드앤 컨쿼 하려고 일부러 팩토리얼을 골랐다. :-)
앞서 두 개의 글에서 시퀀셜과 리컬시브 프로그램을 작성했다. 둘 중 하나를 골라서 디바이드 앤 컨쿼의 기본 코드로 삼아야 한다. 나는 리컬시브 프로그램을 선택했다. 왜냐하면 이 글의 등장 인물은 C언어, 파이썬, 얼랭이고 그 중 주인공은 얼랭이기 때문이다. 얼랭은 시퀀셜이 조금 억지스럽다. 리컬시브가 자연스럽다. 그래서 디바이드 앤 컨쿼로 프로그램을 수정하게 되더라도 얼랭에 맞춰서 리컬시브 프로그램을 디바이드 앤 컨쿼로 수정하는 것이 목적에 부합하는 것이라고 생각한다.
C언어, 파이썬, 얼랭 모두 팩토리얼을 디바이드 앤 컨쿼하는 전략은 동일하다.
-C언어-
C언어는 시작이 어려운 반면 익숙하고 잘 동작하는 코드를 목적에 맞게 고칠 때에는 상당히 좋은 선택이 된다. 왠만해서는 잘 돌기 때문이다. 파이썬처럼 스택이 모자르다고 죽진 않잖아! 지난 리컬시브 버전을 토대로 디바이드 앤 컨쿼 버전으로 바꾸었다. 디바이드 앤 컨쿼를 위해서 팩토리얼 함수를 조각 조각 실행하는 중간 함수를 만들었다.
#include <stdio.h>
#include <gmp.h>
#include <time.h>
void factorial_dnc(mpz_t* f, unsigned int s, unsigned int e)
{
if(e == s){
return;
}else{
mpz_mul_ui(*f, *f, e);
factorial_dnc(f, s, e-1);
}
}
void dnc(mpz_t* f, unsigned int n)
{
const unsigned int CALC_RANGE = 500;
unsigned int divide_num = n/CALC_RANGE;
unsigned int i = 1;
mpz_t div_fac;
mpz_init(div_fac);
unsigned int start = 0;
unsigned int end = 0;
for(i = 1; i <= divide_num; i++){
start = ((i-1)*CALC_RANGE)+1;
end = (i*CALC_RANGE);
mpz_set_ui(div_fac, start);
factorial_dnc(&div_fac, start, end);
mpz_mul(*f, *f, div_fac);
}
mpz_clear(div_fac);
}
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();
dnc(&facN, n);
end = clock();
runtime = (double)(end-start) / CLOCKS_PER_SEC;
printf ("runtime is %f\n", runtime);
mpz_clear(facN);
}앞서 간단히 설명한 공식대로 시작 값과 끝 값을 계산해서 잘려진 조각 수 만큼 루프 돌며 계산을 수행한다. 간단하다.
이번 편부터는 측정 값을 하나 더 늘리겠다. 디바이드 앤 컨쿼의 한 조각 크기를 바꿔가면서 측정해 보겠다. 위 소스에서는 CALC_RANGE가 500이다. 이 CALC_RANGE를 순서대로 500, 1000, 5000, 10000으로 바꿔가면서 측정하겠다. 파이썬이 버텨낼 수 있을까..
runtime 500 by 50000 is 0.310000 real 0m0.325s user 0m0.316s sys 0m0.008s runtime 1000 by 50000 is 0.230000 real 0m0.240s user 0m0.232s sys 0m0.004s runtime 5000 by 50000 is 0.220000 real 0m0.222s user 0m0.220s sys 0m0.000s runtime 10000 by 50000 is 0.330000 real 0m0.339s user 0m0.336s sys 0m0.000s --------------------------- runtime 500 by 100000 is 1.390000 real 0m1.393s user 0m1.384s sys 0m0.012s runtime 1000 by 100000 is 0.980000 real 0m0.993s user 0m0.972s sys 0m0.012s runtime 5000 by 100000 is 0.660000 real 0m0.662s user 0m0.660s sys 0m0.000s runtime 10000 by 100000 is 0.790000 real 0m0.799s user 0m0.792s sys 0m0.004s --------------------------- runtime 500 by 150000 is 3.280000 real 0m3.292s user 0m3.248s sys 0m0.040s runtime 1000 by 150000 is 2.290000 real 0m2.298s user 0m2.276s sys 0m0.020s runtime 5000 by 150000 is 1.290000 real 0m1.303s user 0m1.292s sys 0m0.008s runtime 10000 by 150000 is 1.390000 real 0m1.406s user 0m1.396s sys 0m0.008s --------------------------- runtime 500 by 200000 is 6.020000 real 0m6.033s user 0m5.964s sys 0m0.064s runtime 1000 by 200000 is 4.180000 real 0m4.231s user 0m4.168s sys 0m0.028s runtime 5000 by 200000 is 2.150000 real 0m2.154s user 0m2.152s sys 0m0.000s runtime 10000 by 200000 is 2.100000 real 0m2.126s user 0m2.112s sys 0m0.008s runtime 20000 by 200000 is 3.060000 real 0m3.074s user 0m3.064s sys 0m0.008s
기존 50000!, 100000!, 150000!, 200000!에 각각 500, 1000, 5000, 10000씩 조각 낸 결과이다. 4개씩 4개라서 16개의 결과를 죽 늘어놓으니 보기 좀 난해하다. 오래간만에 장인 정신을 발휘해서 표를 그려 보겠다.
+-----------+-----------+-----------+ | N | CALC_RANGE| 시간(초) | +-----------+-----------+-----------+ | | 500 | 0.31 | | 50000! | 1000 | 0.23 | | | 5000 | 0.22 | | | 10000 | 0.33 | +-----------+-----------+-----------+ | | 500 | 1.39 | | 100000! | 1000 | 0.98 | | | 5000 | 0.66 | | | 10000 | 0.79 | +-----------+-----------+-----------+ | | 500 | 3.28 | | 150000! | 1000 | 2.29 | | | 5000 | 1.29 | | | 10000 | 1.39 | +-----------+-----------+-----------+ | | 500 | 6.02 | | 200000! | 1000 | 4.18 | | | 5000 | 2.15 | | | 10000 | 2.10 | | | 20000 | 3.06 | +-----------+-----------+-----------+
후아.. 생각보다 빡세다. 일단 전체적인 결과는 디바이드앤 컨커를 하지 않았을 때와 비교해서 어마어마한 속도 향상을 보였다. 이런게 알고리즘의 힘이라구! 사실 당연히 디바이드앤 컨커를 하면 하지 않았을 때 보다 빨라질 것이라 예상하긴 했지만 이렇게 엄청나게 빨라질 줄은 몰랐다. 대충 가장 빨랐을 때를 기준으로 해서 약 10배 이상 빠르다! 오오! 분할정복! 오오!!!
그리고 조각을 각각 500, 1000, 5000, 1000으로 했을 때를 비교해보면 전체적으로 비슷한 경향이 보인다. 500에서 1000을 거쳐 5000정도로 나눴을 때에 가장 빠르고 5000보다 큰 10000으로 나누니까 오히려 속도가 느려졌다. 아마 디바이드앤 컨쿼로 얻는 이득보다 스택을 깊게 사용해서 오는 오버해드가 더 커지는 시점이 아닌가 싶다. 특별히 200000!을 할 때는 10000으로 나눠도 속도가 더 빨라지기에 20000으로도 나눠봤다. 역시 예상대로 다시 속도가 느려진것을 볼 수 있었다. 팩토리얼 숫자가 클 수록 한 조각의 계산량이 어느정도 커도 스택을 깊게 사용하는 것에서 오는 오버헤드보다 이득이 크다는 것을 알 수 있다. 여기서도 놀라운 현상은 같은 N에서도 분할 단위에 따라 속도 차이가 2배 이상 난다는 것이다.
디바이드앤 컨커 기법으로 프로그래밍을 하더라도 조각의 크기를 최적화해서 결정하는 것이 성능에 아주 큰 영향을 미친다는 것을 알 수 있다.
-파이썬-
다음은 파이썬이다. 파이썬은 지난번 리컬시브에서 리컬시브 댑스 제한과 스택 프레임을 과도하게 사용해서 세스멘테이션 폴트 나는 것으로 나를 실망시켰다. 파이썬.. 네놈이!!!
댓글에 stackless python을 사용하면 된다고 여러분들께서 친절히 알려주셨으나, 그렇게 된다면 앞서 했던 실험을 전부 다시 stackless python으로 다 측정해서 측정값을 전체 업데이트해야 의미있는 실험이 된다. 그런데 그게.. 꽤나 귀찮다. 그래서 그냥 계속 하던대로 할란다. -_-; 어차피 글은 공개되어 있으니 누군가 같은 실험을 stackless python으로 해서 다른 글을 올려주시길 바란다. 이런게 오픈소스지!
또 하나 내가 실수 한것이, setrecursionlimit()의 값을 설정할 때 N!의 N으로 하면 될 줄 알았는데, 댓글을 보니 더 커야 한단다. 헐.. 난 역시 수학을 못해.. 아니.. 산수인가.. 그래서 일단 이번 실험의 리컬시브 최대값인 10000이 되는지를 먼저 테스트 해 보려 한다.
댓글로 오류를 지적해 주신 sblade님께 감사드립니다.
import sys
import time
def factorial(N):
if N == 1:
return 1
else:
return N * factorial(N-1)
n = 10000
sys.setrecursionlimit(n+10)
start = time.time()
facN = factorial(n)
print "fac %d is"%(n)
print "runtime is %s"%(time.time() - start)N!에서 setrecursionlimit()에 값을 N+10으로 줬다. 그리고 최대 리컬시브 댑스가 될 10000으로 설정했다. 과연 될 것인가!
$ python ./python_factorial_recu.py fac 10000 is runtime is 0.291229009628
된데이~~~!. 일단 이번 글에서 파이썬 실험은 가능 할 것 같다.
파이썬 코드도 리컬시브 코드를 디바이드앤 컨쿼 코드로 바꾸는 전략은 C언어와 동일하다. N!에서 N을 조각으로 나누는 중간함수를 만들고 중간함수에서 for loop을 돌면서 조각 조각 계산한 결과를 합산하여 최종 N!을 만들어내는 코드이다.
import time
import sys
def factorial_dnc(S, E):
if S == E:
return S
else:
return E * factorial_dnc(S, E-1)
CALC_RANGE = 10000
def dnc(N):
divide_num = N/CALC_RANGE
sys.setrecursionlimit(CALC_RANGE+10)
FacN = 1
for i in range(1,divide_num+1):
start = ((i-1)*CALC_RANGE)+1
end = (i*CALC_RANGE)
FacN *= factorial_dnc(start, end)
return FacN
n = 50000
startTime = time.clock()
facN = dnc(n)
endTime = time.clock()
print "runtime %d by %d is %s"%(CALC_RANGE, n, endTime - startTime)C언어 코드와 거의 유사하다. 다른 부분이라면 CALC_RANGE를 설정하고 나서 setrecursionlimit()를 CALC_RANGE+10으로 하는 부분이 있다는 것이다.
앞서와 마찬가지로 N과 디바이드앤 컨쿼의 조각 크기를 바꿔가면서 값을 출력했다.
$ python ./python_factorial_recu_dnc.py runtime 500 by 50000 is 3.68 $ python ./python_factorial_recu_dnc.py runtime 1000 by 50000 is 2.93 $ python ./python_factorial_recu_dnc.py runtime 5000 by 50000 is 2.48 $ python ./python_factorial_recu_dnc.py runtime 10000 by 50000 is 3.32 $ python ./python_factorial_recu_dnc.py runtime 500 by 100000 is 16.47 $ python ./python_factorial_recu_dnc.py runtime 1000 by 100000 is 12.82 $ python ./python_factorial_recu_dnc.py runtime 5000 by 100000 is 8.82 $ python ./python_factorial_recu_dnc.py runtime 10000 by 100000 is 10.52 $ python ./python_factorial_recu_dnc.py runtime 500 by 150000 is 37.66 $ python ./python_factorial_recu_dnc.py runtime 1000 by 150000 is 29.16 $ python ./python_factorial_recu_dnc.py runtime 5000 by 150000 is 18.84 $ python ./python_factorial_recu_dnc.py runtime 10000 by 150000 is 20.49 $ python ./python_factorial_recu_dnc.py runtime 500 by 200000 is 67.52 $ python ./python_factorial_recu_dnc.py runtime 1000 by 200000 is 52.0 $ python ./python_factorial_recu_dnc.py runtime 5000 by 200000 is 32.73 $ python ./python_factorial_recu_dnc.py runtime 10000 by 200000 is 33.43
여기까지 하고 나서, N과 CALC_RANGE를 배열에 넣고 마찬가지로 loop돌리는 큰 루프를 main에 코딩하면 일일이 숫자 바꾸고 실행해보는 저 삽질을 줄일 수 있지 않을까라는 생각이 들었다. 아놔... 그런데 왠지 이제 얼랭만 하면 되는데 얼랭에서 그 기조를 바꾸는게 더 싫었다. 그냥 하던대로 노가다 하련다.
결과를 정리하면 아래와 같다.
+-----------+-----------+-----------+ | N | CALC_RANGE| 시간(초) | +-----------+-----------+-----------+ | | 500 | 3.68 | | 50000! | 1000 | 2.93 | | | 5000 | 2.48 | | | 10000 | 3.32 | +-----------+-----------+-----------+ | | 500 | 16.47 | | 100000! | 1000 | 12.82 | | | 5000 | 8.82 | | | 10000 | 10.52 | +-----------+-----------+-----------+ | | 500 | 37.66 | | 150000! | 1000 | 29.16 | | | 5000 | 18.84 | | | 10000 | 20.49 | +-----------+-----------+-----------+ | | 500 | 67.52 | | 200000! | 1000 | 52.00 | | | 5000 | 32.73 | | | 10000 | 33.43 | +-----------+-----------+-----------+
역시나 한결같이 C언어보다 10배 정도 느리다. gmp 라이브러리를 쓰면 빨라요. 이따위 소리는 하지 말기 바란다. 나는 부득이한 경우를 제외하고는 외부 라이브러리를 사용하지 않는다는 원칙하에 이 글을 진행하고 있다.
-얼랭-
다음은 얼랭이다. 얼랭은 내가 아직 익숙하지 않아서 뭔가 코드가 지난 리컬시브 버전에 비해서 길고 복잡해 졌다.
-module(erlang_factorial_time_dnc).
-export([start/0]).
-define(CALC_RANGE, 10000).
start()->
N = 200000,
Start = now(),
F = dnc(N),
End = now(),
Runtime = timer:now_diff(End, Start) / 1000,
%%io:format("fac ~w is ~w~n", [N, F]),
io:format("runtime ~w by ~w is ~w~n",[?CALC_RANGE,N,Runtime]).
mul([]) -> 1;
mul([H|T])->H * mul(T).
dnc(N)->
Divide_num = N div ?CALC_RANGE, % N/CALC_RANGE 하면 결과가 500.0이 되어 무한루프
FL = for(1,Divide_num,fun(I,C)->dnc_for(I,C) end, ?CALC_RANGE),
mul(FL).
for(Max, Max, F, C) -> [F(Max,C)];
for(I, Max, F, C)->[F(I,C)|for(I+1, Max, F, C)].
factorial(1)->1;
factorial(N)->N * factorial(N-1).
factorial(S, S)->S;
factorial(S, E)->E * factorial(S, E-1).
dnc_for(I,C)->
Start = ((I-1)*C)+1,
End = (I*C),
%%io:format("factorial ~w to ~w~n", [Start, End]),
factorial(Start, End).길고 복잡해 졌지만 기본 구성은 C언어나 파이썬과 동일하다. dnc() 함수로 N을 던지고, N을 CALC_RANGE 크기로 쪼갠다음 dnc_for() 함수로 조각을 보내서, 시작 값과 끝 값을 계산한 다음 팩토리얼을 계산하는 것이다. 계산 완료된 값은 리스트에 모았다가 나중에 한꺼번에 곱해서 최종 답을 구한다.
실행 결과는 아래와 같다.
erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 500 by 50000 is 2042.025 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 1000 by 50000 is 2077.434 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 5000 by 50000 is 2587.877 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 10000 by 50000 is 3231.244 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 500 by 100000 is 9352.464 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 1000 by 100000 is 9279.257 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 5000 by 100000 is 10449.871 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 10000 by 100000 is 11621.357 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 500 by 150000 is 22456.056 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 1000 by 150000 is 22581.527 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 5000 by 150000 is 23967.543 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 10000 by 150000 is 25954.371 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 500 by 200000 is 42306.002 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 1000 by 200000 is 42054.1 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 5000 by 200000 is 43964.632 ---- erl -noshell -s erlang_factorial_time_dnc start -s init stop runtime 10000 by 200000 is 46694.498
실형 결과를 표로 정리하면...
+-----------+-----------+-----------+ | N | CALC_RANGE| 시간(초) | +-----------+-----------+-----------+ | | 500 | 2.04 | | 50000! | 1000 | 2.07 | | | 5000 | 2.58 | | | 10000 | 3.23 | +-----------+-----------+-----------+ | | 500 | 9.35 | | 100000! | 1000 | 9.27 | | | 5000 | 10.44 | | | 10000 | 11.62 | +-----------+-----------+-----------+ | | 500 | 22.45 | | 150000! | 1000 | 22.58 | | | 5000 | 23.96 | | | 10000 | 25.95 | +-----------+-----------+-----------+ | | 500 | 42.30 | | 200000! | 1000 | 42.05 | | | 5000 | 43.96 | | | 10000 | 46.69 | +-----------+-----------+-----------+
실험 결과는 조금 의외였다. 전체적인 경향은 디바이드앤 컨쿼의 조각을 크게 할 수록 점점 성능이 좋아지다가 나빠지는 모습으로 앞의 C언어나 파이썬과 같았다. 하지만 경향만 같을 뿐 더 자세히 보면 다른 부분이 보인다. 우선 C언어나 파이썬 모두 커맨드앤 컨쿼의 조각을 5000으로 했을 때에 성능이 가장 좋았다. 하지만 얼랭은 조각이 1000일 때 성능이 가장 좋았다. 오히려 조각이 5000일 때는 성능이 더 나빠졌다.
또한 파이썬을 시퀀셜 성능에서 발라버린것과 비교해서 디바이드앤 컨쿼에서는 파이썬에 밀리는 모습을 보였다. 디바이드앤 컨쿼의 크기가 500일 때는 전체적으로 파이썬에 비해 나은 성능을 보였다. 디바이드앤 컨쿼의 크기가 1000일 때도 그럭저럭 나은 성능을 보였으나 시퀀셜일 때 처럼 그렇게 많은 차이가 보이지 않았다. 문제는 조각의 크기가 5000일 때였다. 조각의 크기가 5000이 되자 오히려 성능이 파이썬보다 더 나쁘게 나왔다. 팩토리얼의 N의 크기가 작을 때는 성능이 조금 나쁜 정도였지만, N이 150000 이상으로 커지면서는 디바이드앤 컨쿼의 크기가 5000 이상일 때에 파이썬과 비교해서 거의 10초 정도 차이나 났다. 눈에 보일 정도로 현저하게 떨어지는 성능이 측정되었다.
이것을 어떻게 해석해 볼 수 있을까. 내가 의심할 수 있는 것은 스택의 활용 성능이다. 디바이드앤 컨쿼의 조각 크기가 크다는 것은 한 번 분할에서 사용하는 스택의 깊이가 깊다는 것을 의미한다. 조각의 크기가 커질 수록 속도가 현저하게 줄어드는 것은 스택을 깊이 사용하면 할 수록 전체 성능이 떨어진다는 것으로 해석할 수 있다. 파이썬이 스택을 깊게 사용하지는 못하는 대신 얼랭에 비해서 스택을 사용하는 성능은 더 좋은 것이다. C언어는 언급할 필요도 없이 그냥 제일 빠르다. 하지만 (아주 잘 만든)어셈블리어가 출동한다면? N이 커질 수록 성능이 나빠지는 것은 전적으로 내가 얼랭 코딩을 잘 못하기 때문인것 같다. 파이썬과 C에서는 디바이드앤 컨쿼에서 각 조각이 계산을 완료하여 리턴함과 동시에 바로 바로 곱셈을 누적해서 최종 값을 변수 한 개로 유지하고 있었지만, 얼랭에서는 이를 리스트에 쌓아 두었다가 나중에 리스트를 순회해서 리스트에 쌓여 있는 값을 다 곱하여 최종 결과를 만들어 낸다. 아무래도 리스트를 유지하기 위한 메모리 공간이 추가로 아주 많이 필요하고 이를 순회하는 코스트가 들기 때문인것 같다.
-다음 예고-
다음은 대망의 마지막 실험이다. 분산 처리 코드를 작성할 예정이다. 이번 글에서 작성한 디바이드앤 컨커의 각 조각을 분산 코어에게 맡기는 것이 목표다. 그런데 아쉽게도 내 컴퓨터는 코어가 두 개뿐이다. 어쩌겠는가. 두 개라도 빡시게 써야지.
그런데! 어떻게 해야 하지? -_-;
일단 지금 예상은 C와 파이썬은 그냥 thread programming을 할 예정이다. threading을 하면 알아서 코어 분산을 해 주리라는 믿음하에 코딩할 건데 과연 될지 안될지 모르겠다.
정말 그냥 thread 사용하면 분산되나요? 아니면 openmp 같은 라이브러리 써야 하나요?
얼랭은 뭐 언어 자체에서 분산처리 해 준다고 하니 그냥 표준 라이브러리에서 제공하는 프로세스 라이브러리를 사용할 예정이다.
잘 되어야 할 텐데...
댓글
안녕하세요? 나빌레라님의 블로그글 "재미있는 놀이:
안녕하세요?
나빌레라님의 블로그글 "재미있는 놀이: C, Python, Erlang으로 50000! 해보기"에 대해서
그동안 관심을 많이 가지고 있었는데, 바쁘다는 핑계로 정독해 보지 못하다가
오늘 마음먹고 자세히 읽어보았네요. 참 좋은 내용입니다.
읽어보면서 제가 나름대로 정리해 봤는데,(#은 나빌레라님의 글번호입니다)
#1.반복루프(for): 200000! 계산시간 약25초
#2.재귀(함수 재호출): 200000! 계산시간 약27초
#3.재귀호출 분할: 200000! 계산시간 약04초(평균)
위에서 #3에서 엄청나게 빠른 실행시간이 나왔습니다.
(시간은 C언어 기준입니다만, 다른언어도 #3에서 엄청나게 빨라지는군요)
여기서 호기심이 발동했습니다. 왜? #3에서 엄청나게 빨라지는 걸까?
단지 분할정복 때문인가요?
저는 #3을 알고리즘에서 말하는 Divide and Conquer로 보지 않습니다.
왜냐면, 알고리즘에서 효율성(비용)을 얘기할때 반복회수를 중요하게 보는데,
#1, #2, #3은 반복회수가 모두 동일하기 때문입니다.
그럼 스택의 길이(깊이) 때문인가요?
그런데, #1과 #2의 실행시간은 그닥 차이나지 않아서 스택 길이 문제로 보기에도 애매합니다.
그래서 #3을 실행하실때 시스템이 멀티코어(CPU 여러개)라면
CPU 활용도를 보셨을듯 한데, #3에는 CPU활용도가 없습니다.
나빌레라님이 #1에 실은 CPU활용도와 비슷하기 때문에 생략하신듯 한데...
그렇다면 저는 더더욱 미궁속으로 빠져듭니다.
#1, #2, #3 모두
(1)반복회수가 동일하다.
(2)스택의 길이에도 큰 영향 없다.
(3)CPU 활용도 비슷하다.
그럼, 어디에서 차이가 나는 걸까요?
제가 잘못 이해하고 있는 걸까요?
PS.저는 나빌레라님의 팬입니다. 저는 나빌레라님의 멋진 글을 지적하고자 함이 아니고,
제가 이해하고자 하는 것들이 미궁속으로 빠지는듯하여 여러분들의 긍정적인 댓글이 있었으면 합니다.
(살짝 걱정이 되네요~)
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
곱셈하는 회수는 같아도 수의 크기가 다릅니다.
간단히 얘기해서 분할해서 계산하면 한번 연산할때 계산해야 할 자리수가 줄어듭니다.
예를 들자면 한법 곱셈할때마다 자리수가 1자리씩 늘어난다고 하고 숫자를 100번 곱해야 한다고 하면
100! 을 계산할때 필요한 자리수는 100! 이 됩니다.
이때 다섯 조각으로 나눠서 계산해 보면
20! * 5 가 됩니다.
계산량에서 많은 차이가 납니다.
100!을 다섯분할하여 계산하면 20! * 5 이므로
100!을 다섯분할하여 계산하면 20! * 5 이므로 이것이 같다는 말씀인가요?
다르지 않나요?
100!은 계산하기 너무 크므로 간단히 6!을 가지고 계산해 보면,
6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 이고,
3! * 2 = 12 입니다.
6!을 두개로 분할하여 계산하는 것은,
6! = (1 * 2 * 3) * (4 * 5 * 6) = 720 이렇게 계산 됩니다.
나빌레라님의 프로그램도 이렇게 되어 있구요.
6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 이나
6! = (1 * 2 * 3) * (4 * 5 * 6) = 720 의 계산회수(반복수)는 동일하게 5입니다.
이계산은 알고리즘에서 말하는 Divide and Conquer가 아니라
단순히 계산을 분할해서 하는것이고
반복회수도 모두 동일한데 이상하게도 #3번째 결과에서 엄청빠른 실행시간을 보인다는 것입니다.
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
자리수라는 표현이 좀 부정확 했네요.
숫자를 표시한 바이트수라고 보면 이해하실 겁니다.
제 예제에서 20!을 끝내고 두번째 블록을 시작하는 부분을 비교해 보죠.
20! 을 계산하면 2432902008176640000 이고 이다음 계산은
2432902008176640000 * 21 이 됩니다.
그러나 블록을 나눈다고 보면 그냥 21 이 됩니다.
즉 블록을 나눌때 마다 앞서 계산한 값을 곱셈에서 제외 시키므로 추가적인 연산시간을
절약 할 수 있습니다.
이글을 보니 재귀호출(이전 블로그 글)이 최적화가 덜 된것이 느껴지더군요.
1~n 문제를 1~n-1 문제와 n 문제를 나누고 n 문제부터 풀어서 큰 숫자부터 곱이 시작되었는데 이를 반대로
1 문제와 2~n 문제로 나누고 작은 숫자부터 곱하면 빠를 것이라 예상하고 만들어 보니 역시나 빠르군요.
#include <stdio.h> #include <gmp.h> #include <time.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); } } void factorial2(mpz_t* f, unsigned int s, unsigned int n) { if(s == n){ mpz_mul_si(*f, *f, s); }else{ mpz_mul_si(*f, *f, s); factorial2(f, s+1, n); } } int main(int argc, char **argv) { mpz_t facN, facN2; unsigned int n = 50000; clock_t start, end; double runtime; mpz_init(facN); mpz_init(facN2); { mpz_set_ui(facN, 1L); start = clock(); factorial(&facN, n); end = clock(); runtime = (double)(end-start) / CLOCKS_PER_SEC; printf ("runtime is %f\n", runtime); } { mpz_set_ui(facN2, 1L); start = clock(); factorial2(&facN2, 1, n); end = clock(); runtime = (double)(end-start) / CLOCKS_PER_SEC; printf ("runtime is %f\n", runtime); } if(mpz_cmp (facN, facN2) == 0) { printf("result is same\n"); } else { printf("diffrent result\n"); } mpz_clear(facN); mpz_clear(facN2); }정확한 답이 될지는 모르겠지만, 어디까지나 제
정확한 답이 될지는 모르겠지만, 어디까지나 제 추측으로 답해 드리자면
컴퓨터에서 300 * 301의 계산과 223479827342893289357289347 * 223479827342893289357289348의 계산은 속도 차이가 많이 납니다.
계산 횟수로 따지면 둘 다 한 번이지만 실제 계산 시간은 차이가 아주 크지요.
분할을 하기 전에는 어느 정도 숫자 이상 넘어간 이후부터 계속해서 매우 큰 수를 계산해야 합니다.
예를 들면 200000!일 때에 중간에 153232 정도를 계산하고 있다면,
239457389754892748927348927428934792...(아무튼 엄청 큰 수. 즉, 153231!) * 153232을 해야 합니다.
그리고 153233이 되면 큰 수 계산을 또 해야 하지요. 이걸 200000까지 해야 합니다.
그런데 분할을 한다면 계산 횟수는 같을 지라도 조각 마다 다루는 숫자의 크기가 작아집니다.
199000 * 199001 = 39601199000
39601199000 * 199002 = xxxx
이런식으로 계산하게 되지요. 시퀀셜이라면 34589023748927592.....(졸라 큰 수!) * 199002를 해야 할 겁니다.
이런게 계속 누적되다 보니 속도 차이가 크게 10배 정도 나는 것으로 추정됩니다.
참고로 그냥 학교때 배운 알고리즘의 복잡도 계산하는 공식으로 분석하면,
팩토리얼의 시퀀셜과 리컬시브의 복잡도는 O(N)이고, 디바이드앤 컨쿼의 복잡도는 O(nlogn)입니다. 오히려 디바이드앤 컨쿼의 복잡도가 더 크지요. 그런데 실제로는 디바이드앤 컨쿼가 10배 이상 빠릅니다.
이론과 실전의 차이랄까요? ^^
----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라
정말 명쾌합니다. 아침에 출근해서 직장일때문에
정말 명쾌합니다.
아침에 출근해서 직장일때문에 기분이 침울했는데,
나빌레라님의 명쾌한 답변을 읽고 기분이 좋아 졌습니다.
장문의 블로그글을 작성하여 계속 연재할려면 시간과 노력이 많이 드는데,
이것을 쉽게쉽게 하시는 나빌레라님을 항상 존경하고 있습니다.
다만, 한가지 지적아닌 말씀을 드리고 싶은 것은 Divide and Conquer에 관한 부분인데,
보통 알고리즘 복잡도는 다음과 같이 비교됩니다.
O(n) --> Divide and Conquer 로 개선하면 --> O(logn)
O(n제곱) --> Divide and Conquer 로 개선하면 --> O(nlogn)
여기서, n의 개수가 충분히 클때 Divide and Conquer의 효율이 극대화 됩니다.
log 그래프를 보면 이런 특성이 확실히 나타납니다.
발제글에 있는 프로그램들의 알고리즘 복잡도는 모두 O(n)으로 동일한데,
팩토리얼 계산을 분할하여 구간 반복하면 연산대상(오퍼런드)의 데이터타입이 작아져서
연산시간이 빨라지는데에서 오는 성능개선인듯 합니다.
(이 부분은 나빌레라님이 명쾌하게 설명해 주셨습니다)
고맙습니다. 즐거운 하루 되세요~
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
음.. 그런가요?제가 배운대로라면.. 뭐 배운지도
음.. 그런가요?
제가 배운대로라면.. 뭐 배운지도 오래되어서 맞는지 모르겠지만..
통상적으로 DNC의 알고리즘 복잡도는
T(n) = aT(n/b) + f(n)
표현할 수 있습니다. T(n)은 전체 시간이고요, T(n/b)는 각 부분의 계산시간, a는 조각의 개수, f(n)은 조각을 나누고 합치는 시간입니다.
본문의 팩토리얼 코드를 예를 들면 200000!을 1000개씩 나눠서 계산할 때
N=200000
P=1000
이 됩니다.
이러면 전체 조각의 개수는 200개가 되고요. DNC 한 조각은 1000번 계산을 합니다. 즉 200000/200입니다. 그리고 조각을 나누고 합치는 횟수도 200이지요.
그래서 어떤 상수 c를 정의할 수 있습니다.
c=N/P
그러면 저 위의 수식이 아래와 같이 정리됩니다.
T(n) = cT(n/c) + cn
a = b = c 가 되고 f(n) = cn이 되어 f(n)의 복잡도는 O(n)이 됩니다.
그리고 흔히 마스터 정리라고 하는 식이 있습니다.
http://en.wikipedia.org/wiki/Master_theorem
마스터 정리에 따라 T(n) = cT(n/c) + cn 수식은 위 링크의 case2에 해당하는 식이 됩니다.
따라서 복잡도는 O(nlogn)이 됩니다.
그런데 제가 틀리고 rgb님이 맞을 수도 있어요. 저도 배운지 하도 오래되어서 맞게 한건지 아직도 의심스럽답니다.
----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라
네, 나빌레라님이 Divide and Conquer와
네, 나빌레라님이 Divide and Conquer와 이것을 수학수식으로 증명하는 Master Theorem은
그 개념을 잘 설명해 주셨습니다. 저도 집게 가서 알고리즘책을 다시 봐야 겠어요(^^)
그런데, 한가지 놓치고 계시는 부분이 있어서 다시 댓글 달아봅니다.
(지적하고자 함이 아니고, 지식을 서로 얘기하는 차원에서 받아주시길..)
Divide and Conquer 코드:
Master Theorem 증명 수식:
T(n) = aT(n/b) + f(n)
n=200000 (size of problem) 이고
b=100 (size of divided) 일때, 위 코드 흐름을 따라가 보면,
1번째호출: T(200000)
2번째호출: T(2000) <-- T(n/b)
3번째호출: T(20) <-- T(n/b)
a==3번으로 끝납니다.
즉, procedure T을 재귀 호출할때 n=n/b로 줄어든다는 것입니다.
for 루프로 표현하면,
for (i = n; i < 1; i /= b);
이런 형태입니다.
이것이 Divide and Conquer 에서 얘기하는 알고리즘인데,
나빌레라님의 발제글에서 코딩한 프로그램은,
void dnc(mpz_t* f, unsigned int n) { const unsigned int CALC_RANGE = 100; //b unsigned int divide_num = n/CALC_RANGE; //a unsigned int i = 1; mpz_t div_fac; mpz_init(div_fac); unsigned int start = 0; unsigned int end = 0; for(i = 1; i <= divide_num; i++) { start = ((i-1)*CALC_RANGE)+1; end = (i*CALC_RANGE); mpz_set_ui(div_fac, start); factorial_dnc(&div_fac, start, end); mpz_mul(*f, *f, div_fac); } mpz_clear(div_fac); }n=200000 (size of problem)
b=100 (size of divided==CALC_RANGE) 일때,
위를 for 루프로 간략해 보면,(반복 기준)
n = 200000;
b = 100;
a = n/b; //2000
for(i = 1; i <= a; i++) //for(i = 1; i <= divide_num; i++)
for(j = 1; j <= b; j++); //factorial_dnc(&div_fac, start, end);
이것의 전체 반복회수는 a * b == n 입니다.
그냥 n만큼 반복하는 것이므로
알고리즘에서 얘기하는 Divide and Conquer로 보기 어렵다는 것입니다.
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
Divide and Conquer에 대한 pseudo 코드를 보고..
재귀적으로 처리하는 것이 네빌레라님 작성 코드보다 빠를 것으로 예상되어 시작하였습니다.
예전에 하신 #2 (http://kldp.org/node/129379) 이
1~n 까지의 문제를 1~n-1과 n으로 문제로 나누어서 재귀호출했다면
저는 1~n/2와 n/2+1~n 으로 나누어서 재귀 호출하였습니다.
1. 네빌레라님의 Divide and Conquer
2. 재귀적 처리 + 분할된 숫자 갯수가 일정 갯수 이하면 계산
3. 재귀적 처리 + 분할된 숫자 갯수가 1 또는 2가 되었을 때 계산
#include <stdio.h> #include <gmp.h> #include <time.h> void factorial_dnc(mpz_t* f, unsigned int s, unsigned int e) { if(e == s){ return; }else{ mpz_mul_ui(*f, *f, e); factorial_dnc(f, s, e-1); } } void dnc(mpz_t* f, unsigned int n) { const unsigned int CALC_RANGE = 500; unsigned int divide_num = n/CALC_RANGE; unsigned int i = 1; mpz_t div_fac; mpz_init(div_fac); unsigned int start = 0; unsigned int end = 0; for(i = 1; i <= divide_num; i++){ start = ((i-1)*CALC_RANGE)+1; end = (i*CALC_RANGE); mpz_set_ui(div_fac, start); factorial_dnc(&div_fac, start, end); mpz_mul(*f, *f, div_fac); } mpz_clear(div_fac); } void dnc2(mpz_t* f, unsigned int start, unsigned int end) { mpz_t div_fac1, div_fac2; const unsigned int CALC_RANGE = 500; unsigned int middle; middle = (end-start)/2+start; if(end-start <= CALC_RANGE) { factorial_dnc(f, start, end); } else { mpz_init(div_fac1); mpz_init(div_fac2); mpz_set_ui(div_fac1, 1L); mpz_set_ui(div_fac2, 1L); dnc2(&div_fac1, start, middle); dnc2(&div_fac2, middle, end); mpz_mul(*f, div_fac1, div_fac2); mpz_clear(div_fac1); mpz_clear(div_fac2); } } void dnc3(mpz_t* f, unsigned int start, unsigned int end) { mpz_t div_fac1, div_fac2; unsigned int middle; middle = (end-start)/2+start; if(end-start == 2) { mpz_set_ui(*f, ((end-1) * end)); } else if(end-start == 1) { mpz_set_ui(*f, end); } else { mpz_init(div_fac1); mpz_init(div_fac2); mpz_set_ui(div_fac1, 1L); mpz_set_ui(div_fac2, 1L); dnc3(&div_fac1, start, middle); dnc3(&div_fac2, middle, end); mpz_mul(*f, div_fac1, div_fac2); mpz_clear(div_fac1); mpz_clear(div_fac2); } } int main(int argc, char **argv) { mpz_t facN, facN2, facN3, facN4; unsigned int n = 50000; clock_t start, end; double runtime; mpz_init(facN); mpz_init(facN2); mpz_init(facN3); { // 나빌레라 mpz_set_ui(facN, 1L); start = clock(); dnc(&facN, n); end = clock(); runtime = (double)(end-start) / CLOCKS_PER_SEC; printf ("runtime is %f\n", runtime); } { // SoftOn mpz_set_ui(facN2, 1L); start = clock(); dnc2(&facN2, 1, n); end = clock(); runtime = (double)(end-start) / CLOCKS_PER_SEC; printf ("runtime is %f\n", runtime); } { // SoftOn mpz_set_ui(facN3, 1L); start = clock(); dnc3(&facN3, 1, n); end = clock(); runtime = (double)(end-start) / CLOCKS_PER_SEC; printf ("runtime is %f\n", runtime); } if((mpz_cmp (facN, facN2) == 0) && (mpz_cmp (facN2, facN3) == 0)) { printf("result is same\n"); } else { printf("diffrent result\n"); } mpz_clear(facN); mpz_clear(facN2); mpz_clear(facN3); }결과는
예상한 것처럼 단순 분할 보다 재귀가 빠르네요.
하지만 문제를 너무 많이 분할 하는 것은 재귀 호출 overhead 때문에 더 느려지는 듯합니다.
어디서 본듯한 주제인듯 하여 찾아 봤습니다.
http://kldp.org/node/107470
제가 가지고 있는 마지막 버전의 python 파일은
#!/usr/bin/env python # -*- coding: utf8 -*- import time,sys from multiprocessing import Pool from math import log, floor # 리스트내의 곱을 리턴 한다. def multiply_iter( numlist ): return reduce( lambda x,y : x*y , numlist ) # 리스트를 slicenum 개로 분할 한다. def sliceby( numlist, slicenum ): nlc = len(numlist) listnum,restnum = divmod( nlc , slicenum ) while listnum < 2 and slicenum >1 : slicenum -=1 listnum,restnum = divmod( nlc , slicenum ) return map( lambda x : numlist[x::slicenum] ,range(slicenum) ) # 리스트를 n 개로 분할 해서 곱의 리스트를 구한다 def pool_multiply( numlist, processmun = 4 ): pool = Pool(processes=4) listnums = sliceby( numlist, processmun ) return pool.map(multiply_iter, listnums ) def calc_mtfact( numlist,st ) : print len(numlist), time.time() - st while len(numlist) > 4 : numlist = pool_multiply( numlist,max(len(numlist)/4,2)) print len(numlist), time.time() - st return multiply_iter(numlist) if __name__ == '__main__': nf = 50000 start = time.time() result= calc_mtfact( range(1,nf+1) , start ) end = time.time() exponent = floor(log(result,10)) print( 'fact %d : total(%f sec):digit %d' % (nf , end-start,exponent+1 ) )이더군요. ^^
순수하게 그대로 셀상에서 bc로 넘겼을때 터질까?라는 덕질을 해봤습니다.
http://ipc.pe.kr/27334
저는 리눅 bash명령어로 백만개의 곱샘 명령을(1000000!<-팩토리얼 계산) 순수하게 그대로 셀상에서 bc로 넘겼을때 메모리 오버 등등의, 에러 없이 완벽하게 돌아가는지가 너무 궁금해서 해본 덕후짓입니다. 8년전 컴퓨터에 vmware깔고 500매가 가상 램 상황에서 테스트 했습니다ㅎㅎㅎ
=======
http://ipc.pe.kr 흑엽
댓글 달기