파이썬에서 효율적으로 피보나치 수열 접근하기

# 500이하의 피보나치 수 중에서 홀수는 몇개인지 세는 방법
def fibonacci_naive():
	i, j = 0, 1
	cnt = 0
	while j <= 5000:
		if j % 2:
			cnt += 1
		i, j = j, i + j
	return cnt


def fibonacci():
	i, j = 0 , 1
	while True:
		yield j
		i, j = j, i + j


def fibonacci_transform():
	cnt = 0
	for f in fibonacci():
		if f > 5000:
			break
		if f % 2:
			cnt += 1
	return cnt


from itertools import islice


def fibonacci_succinct():
	is_odd = lambda x: x % 2
	first_5000 = islice(fibonacci(), 0, 5000)
	return sum(1 for x in first_5000 if is_odd(x))

 

세가지 함수 모두 5000보다 작은 피보나치 수열중에서 홀수의 개수를 구하는 함수입니다.

세가지 함수 모두 속도와 메모리 사용량이 비슷하지만 fibonacci_transform 함수가 몇 가지 면에서 더 유리합니다.

 

 

• fibonacci_succicnt 보다 더 자세히 풀어 썼기 때문에 다른 개발자가 디버깅 or 이해가 쉽다.

itertools는 이터레이터를 사용하는 단순한 작업을 아주 쉽게 해주지만 남요하면 자칫 파이썬 답지 않은 코드가 되기 쉽다.

 

fibonacci_naive는 한번에 여러 가지 작업을 해서 실제 계산을 알아보기가 힘들다.

반면 제너레이터를 사용하면 피보나치 수열을 이터레이션 한다는 점이 명확하고 복잡한 계산으로 인해 코드를 이해할 때 어려움을 겪는 일도 없다.

 

마지막으로 fibonacci_transform 함수가 일반화 하기 더쉽다.

이름을 num_odd_under_5000으로 바꾸ㅡ고 제너레이터를 인자로 받으면 어떤 수열에서도 동작한다.

 

fibonacci_transform의 또 다른 장점은 계산 과정을 데이터 생성과 변형 두단계로 구분해서 생각하도록 해준다.