Implementacja ciągu fibonacciego w Python

Pisząc wpis dotyczący importowania odniosłem się do modułów z różnymi implementacjami ciągu fibonaciego. Podawanie kodu źródłowego było tam nieistotne i wydłużyłoby tylko niepotrzebnie wpis. Jednak tak się złożyło, że ostatnio przypomniał mi się ciekawy film Mirosława Zelenta właśnie dotyczący tego ciekawego ciągu. Przypomniało mi to również, że podczas jednej z rozmów o pracę również miałem za zadanie napisanie właśnie programu do wypisania takiego ciągu. Dlatego poniżej prezentuję aż 4 możliwe implementacje takiego ciągu.

Ciąg Fibonacciego

Zanim przejdziemy do implementacji opiszemy krótko ten ciąg. Ma on bardzo ciekawą właściwość. Pierwsze dwa elementy to dwie jedynki, a każdy kolejny element jest sumą dwóch poprzednich. Zatem kolejne liczby w ciągu prezentują się następująco

fibb = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... ]

Standardowa implementacja ciągu fibonacciego

Skoro już wiemy jak prezentuje się dany ciąg spróbujmy napisać funkcję, która zwróci taki wynik. Zróbmy to w najprostszy możliwy sposób

def fibb(n):
    result = [1, 1]
    for i in range(n-2):
        result.append(result[i] + result[(i + 1)])

    return result

Implementacja ciągu fibonacciego przez generator

def fibb(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
        yield a

Wcześniejsze rozwiązanie przechowuje w pamięci całą listę. Spróbujmy to nieco zoptymalizować. Dobrym rozwiązaniem wydaje się zwrócenie generatora.

Implementacja ciągu fibonacciego rekurencyjnie

Generatory można tworzyć nie tylko przez yield. Ci dociekliwi pewnie wiedzą, a Ci mniej dociekliwi mają okazję dowiedzieć się ciekawostki. Jeśli w list comprehension zmienimy nawiasy z kwadratowych na okrągłe, to zamiast listy zwrócony zostanie generator. Spróbujmy zatem napisać trzecie już rozwiązanie z wykorzystaniem generatora i rekurencji.

def rec_fib(n):
    if n < 2:
        return 1
    else:
        return rec_fib(n-1) + rec_fib(n-2)


def fibb(n):
    return (rec_fib(a) for a in range(n))

Implementacja ciągu fibonacciego przez iterator

O iteratorach i generatorach można pisać wiele. Myślę, że samo porównanie iteratora do generatora jest na tyle ciekawym zagadnieniem, że można o tym zrobić oddzielny wpis. Iteratory już wcześniej opisałem. Przypomnijmy zatem przykładową implementację ciągu fibonacciego przez iterator.

class FibIterator:

    def __init__(self, n):
        self.n = n
        self.i = 0
        self.a, self.b = 0, 1

    def __iter__(self):
        return self

    def __next__(self):
        if self.n == self.i:
            raise StopIteration

        self.i += 1
        self.a, self.b = self.b, self.a + self.b
        return self.a

Porównanie implementacji

Porównajmy czasy wykonania wypisanych wcześniej implementacji. Dla każdej implementacji wykonałem 3 próby. W ostatnim wierzu zaprezentowana jest średnia.

262144 powtórzeń

Jak widać 262144 to nie jest dużo iteracji, bo we wszystkich przypadkach przejście po wszystkich obiektach zajęło poniżej sekundy. Ciekawe jest, że najszybsza okazała się standardowa implementacja a najwolniejsza ta z generatorem przy użyciu słowa kluczowego yield .

1048576 powtórzeń

Przy czterokrotnym zwiększeniu ilości iteracji, bo do 1048576 czas we wszystkich przypadkach oscylował w okolicy 11 sekund. Tu najlepiej wypadł iterator a najgorzej rekurencja.

2097152 powtórzeń

Tylko dwukrotne zwiększenie ilości iteracji w stosunku do poprzedniego badania zwiększyło czas aż czterokrotnie. Tu najlepiej wypadła rekurencja a najgorzej iterator.

Podsumowanie

Wyżej przedstawiłem Wam aż 4 różne sposoby implementacji ciągu fibonacciego. Sprawdziłem również czas wykonywania poszczególnych sposobów. Ku mojemu zdziwieniu wszystkie z nich wykonywały się w podobnym czasie. Nie sprawdziłem jak ma wygląda to od strony pamięci. To są przykładowe rozwiązania. Jestem niemal pewien, że każdy jest  w stanie wymyślić przynajmniej jedno, inne. Być może część z nich byłaby nawet szybsza od tych zaproponowanych przeze mnie. W każdym razie, teraz nie będziesz zaskoczony jeśli ktoś poprosi Cię o implementację tego ciekawego ciągu.

Największą lekcją z tego wpisu niech będzie fakt, że nie ma jednego, idealnego rozwiązania problemu. Każde zagadnienie można zaimplementować na wiele sposobów i każdy z nich może być równie dobry.