[쉬어가기] 팩토리얼 함수 구성에 대한 고찰(?)

하도 심심해서 큰 수를 구하는 함수를 구성해서 수를 출력해봤다.

그 중에서도 팩토리얼 함수를 구성 해봤다. 총 5가지 방법으로 구성할 수 있었다.

첫번째 방법은 재귀 함수로 구성하는 방법이다.

def fac(n) :
    if n == 0 or n == 1 :
        return 1
    elif n < 0 :
        return 0
    try :
        return n * fac(n-1)
    except :
        f.write(str(n)+'\n')

함수 부분만 쓰면 위와 같은데, try - except 예외 처리를 한 이유는 재귀 함수의 제한 때문이다.

n을 990 번 까지 하게 되면 그 때부터 오류가 발생하기 시작한다. 즉, 989 번 내로 밖에 쓸 수 없다....

--------------------------------------------------------------------------------------------------

두번째 방법은 for 문으로 구성하는 방법이다.

def fac(n) :
    s = 1
    for k in xrange(1, n+1) :
        s *= k
    return s

처음에는 range() 함수를 써서 구성했다. 이때는 math 모듈에 있는 for 구문과 같은 방법이다.

math 모듈을 사용하는 방법이 세번째 방법이다.

from math import factorial

(생략)
s = factorial(n)

간단하게 써보면 위와 같다. 그런데 xrange() 함수를 쓰게 되면 리스트를 생성하지 않게 된다.

즉, xrange 객체를 생성하게 되어 리스트를 생성 하는데 필요한 메모리를 줄일 수 있게 된다.

100만 팩토리얼 정도만 되도 리스트 생성하고 인덱싱 하는데도 시간이 꽤 들 것이다.

그래서인지 range() 를 쓸 때는 math 모듈이 더 빨랐으나 xrange() 를 쓰고나니 직접 만든 것이 빨랐다.

--------------------------------------------------------------------------------------------------

네번째로 가능한 방법이 reduce 함수를 이용한 방법이다.

s = reduce(lambda x, y : x*y, xrange(1,n+1))

이 역시 xrange() 를 쓰게 되면 성능이 향상 된다.

--------------------------------------------------------------------------------------------------

마지막으로 while 구문을 이용하는 방법이다.

def fac(n) :
    s = 1
    k = 1
    while k < n :
        k += 1
        s *= k
    return s

이렇게 5가지 함수를 구성 했는데, 가장 속도가 빠른 것이 두번째 방법이고, 다음 순서로 다섯번째와 네번째 방법(서로 비슷함), 세번째 방법, 첫번째 방법이다. (재귀 함수는 똑같은 부분을 연속으로 해서 속도를 확인 했다.)

이렇게 구성한 함수를 이용해서 10만 팩토리얼과 100만 팩토리얼을 구해봤다. 시간이 상당히 걸린다.....

그런데 중요한 것은 이것을 계산하는 시간보다 text 파일로 이것을 저장하는 시간이 더 길다는 것이다.

--------------------------------------------------------------------------------------------------

팩토리얼은 계산 자체가 조금 오래 걸리지만 제곱 함수는 훨씬 빠르다.

두 가지 함수를 구성 해봤는데, 하나는 일반적으로 제곱 함수를 계산 하는 함수이다.

s = a**b

간단하긴 하지만 이것을 이용해서 2^1000000 (백만)을 계산 하는데, 0.01 초 정도(?) 밖에 걸리지 않았다.

하지만!!! 이것을 text 파일로 작성하는데 6만 초 정도가 걸렸다.......

다른 방법으로 구성한 함수는 2의 제곱 함수만 구하는 함수 이다. 비트 연산을 이용한 방법이다.

s = 1<<n

이 방법을 쓰면 제곱 함수보다 더 빠르게 계산이 가능하다. 제곱 함수로 2^100000000 (1억) 을 계산하는데, 제곱 함수를 쓰면 0.1초 정도나 걸리지만 비트 연산을 이용하면 0.01 초 밖에 안 걸린다.

즉, 비트 연산이 매우 빠르다는 것이다. 이 때문인지 2의 제곱 관련 함수를 제곱 함수로 계산 하면 시간이 적게 걸리지만 그 외의 제곱 함수를 계산 하는데는 더 오래 걸린다.

4의 백만승을 계산하는데 걸리는 시간보다 3의 백만승을 계산하는데 시간이 더 걸렸다.

(그나저나 이짓을 왜 했는지는 모르겠다......... 한 6개 정도를 계산 하고 text 파일로 저장했다.
대략 2~3 시간은 기본, 6시간, 8시간 씩 기다렸다. 그러나! 이것은 집에서 한 것이 아니라 학교에서
한 것이다.)

(ps. 참고로 집 컴퓨터 보다 학교 컴이 더 빠르다(?).... 학교는 듀얼 코어, 2GB 램 이지만 집은
800MHz, 128 MB 램 이다. ㅡㅡ;;;   램 부족해서 가상램을 896 MB 씩이나 잡아서 쓰고 있다.)