Implementacja ciągu fibonacciego w Python


Poznaj aż 4 sposoby implementacji ciągu fibonacciego w Python. W tym przez rekurencję i generator.


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ń
Standardowa implementacja Rekurencja Generator Iterator
0.73671 0.73044 0.73962 0.72312
0.72498 0.74404 0.80152 0.75615
0.74109 0.75943 0.79272 0.74392
0.73426 0.74464 0.77795 0.74106

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ń
Standardowa implementacja Rekurencja Generator Iterator
11.63351 11.27311 10.88508 11.05011
11.35109 11.20124 11.45518 10.95877
10.96659 12.88256 11.90025 11.15917
11.31706 11.78564 11.41351 11.05602

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ń
Standardowa implementacja Rekurencja Generator Iterator
46.11038 45.16224 46.50528 46.55616
45.77505 45.2502 44.55859 44.55454
45.68997 46.06007 45.7632 47.76542
45.85847 45.49084 45.60902 46.29204

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.

Standardowa implementacja Rekurencja Generator 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.

Wrz 23, 2019

Najnowsze wpisy

Zobacz wszystkie