Ten post użyje liczb Fibonacciego jako narzędzia do budowania wyjaśniania przydatności generatorów Pythona .
Ten post będzie zawierał zarówno C ++, jak i kod Pythona.
Liczby Fibonacciego są zdefiniowane jako sekwencja: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ....
Lub ogólnie:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2
Można to bardzo łatwo przenieść do funkcji C ++:
size_t Fib(size_t n)
{
//Fib(0) = 0
if(n == 0)
return 0;
//Fib(1) = 1
if(n == 1)
return 1;
//Fib(N) = Fib(N-2) + Fib(N-1)
return Fib(n-2) + Fib(n-1);
}
Ale jeśli chcesz wydrukować pierwsze sześć liczb Fibonacciego, ponownie obliczysz wiele wartości za pomocą powyższej funkcji.
Na przykład :, Fib(3) = Fib(2) + Fib(1)
ale Fib(2)
także ponownie oblicza Fib(1)
. Im wyższa wartość, którą chcesz obliczyć, tym gorzej.
Można więc pokusić się o przepisanie powyższego poprzez śledzenie stanu main
.
// Not supported for the first two elements of Fib
size_t GetNextFib(size_t &pp, size_t &p)
{
int result = pp + p;
pp = p;
p = result;
return result;
}
int main(int argc, char *argv[])
{
size_t pp = 0;
size_t p = 1;
std::cout << "0 " << "1 ";
for(size_t i = 0; i <= 4; ++i)
{
size_t fibI = GetNextFib(pp, p);
std::cout << fibI << " ";
}
return 0;
}
Ale to jest bardzo brzydkie i komplikuje naszą logikę main
. Lepiej byłoby nie martwić się o stan w naszej main
funkcji.
Możemy zwrócić a vector
wartości i użyć iterator
iteracji po tym zestawie wartości, ale wymaga to dużej ilości pamięci naraz dla dużej liczby zwracanych wartości.
Wracając do naszego starego podejścia, co się stanie, jeśli chcemy zrobić coś innego niż wydrukować liczby? Musielibyśmy skopiować i wkleić cały blok kodu main
i zmienić instrukcje wyjściowe na cokolwiek innego, co chcielibyśmy zrobić. A jeśli skopiujesz i wkleisz kod, powinieneś zostać zastrzelony. Nie chcesz zostać postrzelony, prawda?
Aby rozwiązać te problemy i uniknąć postrzelenia, możemy przepisać ten blok kodu za pomocą funkcji wywołania zwrotnego. Za każdym razem, gdy napotkamy nowy numer Fibonacciego, wywołalibyśmy funkcję wywołania zwrotnego.
void GetFibNumbers(size_t max, void(*FoundNewFibCallback)(size_t))
{
if(max-- == 0) return;
FoundNewFibCallback(0);
if(max-- == 0) return;
FoundNewFibCallback(1);
size_t pp = 0;
size_t p = 1;
for(;;)
{
if(max-- == 0) return;
int result = pp + p;
pp = p;
p = result;
FoundNewFibCallback(result);
}
}
void foundNewFib(size_t fibI)
{
std::cout << fibI << " ";
}
int main(int argc, char *argv[])
{
GetFibNumbers(6, foundNewFib);
return 0;
}
Jest to wyraźna poprawa, twoja logika main
nie jest tak zagracona, i możesz zrobić wszystko, co chcesz z liczbami Fibonacciego, po prostu zdefiniuj nowe wywołania zwrotne.
Ale to wciąż nie jest idealne. Co jeśli chcesz uzyskać tylko dwie pierwsze liczby Fibonacciego, a następnie zrobić coś, a następnie zdobyć więcej, a następnie zrobić coś innego?
Cóż, moglibyśmy kontynuować tak, jak byliśmy, i moglibyśmy zacząć dodawać stan ponownie main
, pozwalając GetFibNumbers na rozpoczęcie od dowolnego punktu. Spowoduje to jednak dalszy rozwój naszego kodu, który już wydaje się zbyt duży, aby wykonać proste zadanie, takie jak drukowanie liczb Fibonacciego.
Możemy wdrożyć model producenta i konsumenta za pomocą kilku wątków. Ale to jeszcze bardziej komplikuje kod.
Zamiast tego porozmawiajmy o generatorach.
Python ma bardzo fajną funkcję językową, która rozwiązuje problemy takie jak te zwane generatorami.
Generator umożliwia wykonanie funkcji, zatrzymanie w dowolnym punkcie, a następnie kontynuowanie od momentu przerwania. Za każdym razem zwracana jest wartość.
Rozważ następujący kod, który używa generatora:
def fib():
pp, p = 0, 1
while 1:
yield pp
pp, p = p, pp+p
g = fib()
for i in range(6):
g.next()
Co daje nam wyniki:
0 1 1 2 3 5
yield
Oświadczenie jest używany w połączeniu z generatorów Pythona. Zapisuje stan funkcji i zwraca pożądaną wartość. Następnym razem, gdy wywołasz funkcję next () w generatorze, będzie ona kontynuowana tam, gdzie została przerwana wydajność.
Jest to zdecydowanie czystsze niż kod funkcji zwrotnej. Mamy czystszy kod, mniejszy kod i nie wspominając o dużo bardziej funkcjonalnym kodzie (Python zezwala na dowolnie duże liczby całkowite).
Źródło
send
przesyłanie danych do generatora. Kiedy to zrobisz, będziesz mieć „koroutynę”. Bardzo łatwo jest wdrożyć wzorce, takie jak wspomniany Konsument / Producent, z coroutines, ponieważ nie potrzebują oneLock
s, a zatem nie mogą się zakleszczyć. Trudno opisać coroutine bez zwijania nici, więc powiem tylko, że coroutines są bardzo elegancką alternatywą dla wątków.