제너레이터와 yield (2) - 피보나치, 무한급수

제너레이터와 yield (1)

---

이번 포스트에서는 피보나치 수를 계산하는 함수를 리스트를 채워 넣는 방식과 제너레이터를 사용하는 방식으로 구현해 보겠습니다. 0부터 시작하는 피보나치 수를 계산합니다.

def fibonacci_list(num_iters):
    numbers = []
    a, b = 0, 1
    while len(numbers) < num_iters:
    	numbers.append(a)
        a, b = b, a+b
  	return numbers
    
def fibonacci_gen(num_iters):
    a, b = 0, 1
    count = 0
    while True:
        yield a
        a, b = b, a+b
        count += 1
        if count > num_iters:
            break

• fibonacci_list 함수는 원하는 개수의 피보나치 수를 모두 담는 리스트를 생성합니다.
• fibonacci_gen 함수는 yield 를 이용해 다음 피보나치 값을 반복적으로 생성하는 제너레이터가 됩니다. yileld 를 실행하면 값을 방출하고 다른 값 요청이 들어오면 이전 상태를 유지한 채로 실행을 재개하여 새로운 값을 방출하게 됩니다.

두 함수는 물론 똑같은 연산을 수행합니다. 하지만 fibonacci_list 함수는 모든 피보나치 수를 리스트에 담기에 메모리를 fibonacci_gen 에 비해 num_iters 만큼 더 사용하게 됩니다.

for 루프 재구성

파이썬의 for 루프에는 반복할 수 있는 객체, 이터레이터가 필요합니다. 대부분의 객체에서 이터레이터를 생성하려면 파이썬 내장 함수는 iter를 사용하면 되고, 클래스와 같은 복잡한 객체라면 __iter__ 프로퍼티를 정의하면 됩니다. 따라서 다음과 같이 재구성할 수 있습니다.

object_iterator = iter(object)
while True:
    try:
        i = next(object_iterator)
    except StopIteration:
        break
    else:
        do_something(i)

 fibonacci_gen 함수는 이미 이터레이터를 반환했으므로 fibonacci_gen 에 대해서는 iter를 따로 호출할 필요가 없습니다. (type(fibonacci_gen(10)) == type(iter(fibonacci_gen(10))) 이기에 fibonacci_gen 함수는 이터레이터로 변형되는 제너레이터라고 볼 수 있습니다) 하지만 fibonacci_list 함수는 리스트를 반환하므로 리스트의 모든 값을 순회하는 리스트 이터레이터를 새로 만들어야 합니다. 이터레이터를 생성하면 그 이터레이터에 next 함수를 호출하면 StopIteration 예외가 발생하기 전가지 새로운 값을 얻어올 수 있습니다. 

fibonacci_list vs fibonacci_gen

여기서 알아야 할 점은 한 번에 값이 하나만 필요하더라도 fibonacci_list 함수를 사용한다면 전체 데이터를 저장할 수 있는 공간을 할당하고 리스트 각 요소에 값을 넣어줘야 한다는 점입니다. 따라서 fibonacci_list 함수를 사용한다면 사용할 수 있는 용량보다 더 많은 메모리 할당을 시도해서 루프 자체를 실행하지 못하게 할 수 있습니다. 실제로 소요 시간을 비교해보면 그 차이가 더 명확합니다.

def test_fibonacci_list():
    for i in fibonacci_list(100000):
        pass

def test_fibonacci_gen():
    for i in fibonacci_gen(100000):
        pass
        
>>> %timeit test_fibonacci_list()
324 ms ± 15.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit test_fibonacci_gen()
89.3 ms ± 867 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

결과를 보면 제너레이터 버전이 훨씬 빠르고 메모리 사용량도 낮습니다. 그렇다면 항상 제너레이터를 사용해야 할까요? 예를 들어 피보나치 수 리스트를 여러 번 참조해야 한다면 어떨까요? fibonacci_list 함수를 사용한다면 미리 만들어 둔 리스트를 사용하면 될 테지만 제너레이터는 데이터를 두 번 이상 참조하지 않으므로 알고리즘을 제너레이터에 맞게 수정해주어야 합니다. 따라서 추가 메모리를 사용해서 미리 값을 계산해두고 나중에 값을 사용하는 것이 전체 속도를 높일 수 있지만 메모리 제약이 심하다면 매번 값을 계산하는 것이 유일한 해법이 될 수도 있습니다.

예를 들어 다음과 같이 피보나치 수열 중 3으로 나뉘는 수의 개수를 알고 싶다고 합시다. 

divisible_by_three = len([n for n in fibonacci_gen(100000) if n % 3 == 0])

 

피보나치 수열을 사용하기 위해 fibonacci_gen 을 사용하지만 3으로 나뉘는 값을 배열에 저장하고 해당 배열에서 길이만 알아낸 다음 데이터를 버립니다. 이 과정에서 의미 없는 배열의 메모리만큼을 낭비하게 되겠죠. 따라서 이런 작업은 매우 간단하더라도 메모리가 부족해지게 됩니다.

이런 경우에는 지난 포스트에서 제너레이터 comprehension 을 사용할 수 있습니다. 다만 제너레이터에는 length 속성이 없으므로 다음과 같이 구성할 수 있습니다. 이 제너레이터가 생산한 모든 항목을 더하면 리스트 내포를 사용한 버전과 같은 결과를 만들어 내면서 메모리를 거의 사용하지 않습니다.

divisible_by_three = sum(1 for n in fibonacci_gen(100000) if n % 3 == 0)

 

파이썬 내장 함수

시퀀스에 적용할 수 있는 파이썬 내장 함수는 보통 그 자체가 제너레이터입니다. 예를 들어 range 함수는 지정한 범위 안에 속한 수로 이뤄진 실제 리스트 대신 제너레이터를 반환하죠. 이와 비슷하게 map, filter, zip, reversed, enumerate_ll 등은 모두 전체 결과를 저장하지 않고 필요에 따라 연산을 수행합니다. 예를 들어 zip(range(100000), range(100000)) 이라는 연산은 전체 범위에 대한 결과를 미리 계산하지 않고 항상 요청에 해당하는 두 값만 메모리에 있게 됩니다. 

무한급수 예시

모든 피보나치 수를 계산하려면 다음과 같이 할 수 있습니다. 이 작업은 당연히 fibonacci_list로는 할 수 없겠죠. 밑의 함수를 사용한다면 무한급수 각 항의 항목을 캡슐화할 수 있어 스트림에서 원하는 값을 가져오고 충분히 처리가 끝나면 프로그램을 종료할 수 있습니다.

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

 

위 함수를 사용해 5000 이하의 피보나치 수 중에서 홀수는 몇 개인지 구할 수 있습니다.

def fibonacci_naive():
    i, j = 0, 1
    count = 0
    while j < 5000:
        if j % 2 == 0:
            count += 1
        i, j = j, i+j  # do fibonacci
    return count
    
def fibonacci_transform():
    count = 0
    for f in fibonacci():
        if f > 5000:
            break
        if f % 2 == 0:
            count += 1
    return count
    
from itertools import takewhile
def fibonacci_succinct():
    first_5000 = takewhile(lambda x: x <= 5000, fiboancci())
    return sum(1 for x in first_5000 if x % 2)

• itertools.takewhile 함수는 주어진 조건이 참인 요소들로 이루어진 제너레이터를 리턴합니다.

fibonacci_naive 함수는 피보나치 수를 계산하면서 5000 이하의 피보나치 수 중 홀수의 개수를 세는 2 가지 작업을 모두 진행합니다. fiboancci_transform 함수는 fibonacci() 함수를 통해 피보나치 수를 계속 받으면서 홀수의 개수만 세는 작업만을 진행하죠. fibonacci_succint 함수는 itertools.takewhile 함수를 사용해 코드가 굉장히 짧지만 한 눈에 알아보기 힘듭니다.

여기서 알 수 있는 점은 fibonacci_transform 함수가 다른 계산에 영향을 받지 않는 fibonacci 제너레이터를 이용하므로 다른 제너레이터를 함수의 인자로 받는 등의 일반화가 더 쉽다는 점입니다. 또한, 데이터의 생성/변경을 확실히 구분해서 fibonacci_naive 함수에 비해 기능성 측면에서도 더 낫습니다. 다른 데이터를 처리하게 위해 데이터를 변경하는 함수만 재사용하거나 기존 데이터에 추가 작업을 해주는 다른 함수를 더할 수도 있습니다. 즉, 제너레이터를 데이터를 생성하는 목적으로만 사용하고 생성된 데이터는 일반 함수가 처리하도록 분명히 구분함으로써 이런 이점을 얻을 수 있는 것이죠.

 

---

제너레이터와 yield (3) - 지연 계산