Zrozumienie generatorów w Pythonie

218

W tej chwili czytam książkę kucharską Pythona i obecnie patrzę na generatory. Trudno mi się odwrócić.

Skoro pochodzę z języka Java, czy istnieje odpowiednik języka Java? Książka mówiła o „producencie / konsumentie”, ale kiedy słyszę, że myślę o wątkach.

Co to jest generator i dlaczego miałbyś go używać? Oczywiście bez cytowania żadnych książek (chyba że można znaleźć przyzwoitą, uproszczoną odpowiedź bezpośrednio z książki). Być może z przykładami, jeśli czujesz się hojny!

Federer
źródło

Odpowiedzi:

402

Uwaga: ten post zakłada składnię Python 3.x.

Generator jest po prostu funkcją, która zwraca obiekt, na którym można połączyć nexttak, że za każdym wywołaniu zwraca jakąś wartość, aż zgłosi StopIterationwyjątek, sygnalizując, że wszystkie wartości zostały wygenerowane. Taki obiekt nazywa się iteratorem .

Normalne funkcje zwracają pojedynczą wartość return, podobnie jak w Javie. W Pythonie istnieje jednak alternatywa o nazwie yield. Użycie yielddowolnego miejsca w funkcji czyni go generatorem. Przestrzegaj tego kodu:

>>> def myGen(n):
...     yield n
...     yield n + 1
... 
>>> g = myGen(6)
>>> next(g)
6
>>> next(g)
7
>>> next(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Jak widać, myGen(n)jest funkcją, która daje ni n + 1. Każde wywołanie nextzwraca jedną wartość, dopóki wszystkie wartości nie zostaną wygenerowane. forpętle wywołują nextw tle, a zatem:

>>> for n in myGen(6):
...     print(n)
... 
6
7

Istnieją również wyrażenia generatora , które umożliwiają zwięzłe opisanie niektórych popularnych typów generatorów:

>>> g = (n for n in range(3, 5))
>>> next(g)
3
>>> next(g)
4
>>> next(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Zauważ, że wyrażenia generatora są bardzo podobne do list :

>>> lc = [n for n in range(3, 5)]
>>> lc
[3, 4]

Zauważ, że obiekt generatora jest generowany raz , ale jego kod nie jest uruchamiany od razu. Tylko wywołania w celu nextrzeczywistego wykonania (części) kodu. Wykonanie kodu w generatorze zatrzymuje się po osiągnięciu yieldinstrukcji, po której zwraca wartość. Następne wywołanie nextpowoduje, że wykonywanie będzie kontynuowane w stanie, w którym generator został pozostawiony po ostatnim yield. Jest to podstawowa różnica w stosunku do zwykłych funkcji: te zawsze zaczynają wykonywanie na „górze” i odrzucają swój stan po zwróceniu wartości.

Jest więcej rzeczy do powiedzenia na ten temat. Możliwe jest np. Przesyłanie senddanych z powrotem do generatora ( odniesienie ). Ale to jest coś, co sugeruję, abyś nie zaglądał, dopóki nie zrozumiesz podstawowej koncepcji generatora.

Teraz możesz zapytać: po co korzystać z generatorów? Istnieje kilka dobrych powodów:

  • Niektóre koncepcje można opisać znacznie bardziej zwięźle za pomocą generatorów.
  • Zamiast tworzyć funkcję, która zwraca listę wartości, można napisać generator, który generuje wartości w locie. Oznacza to, że nie trzeba budować żadnej listy, co oznacza, że ​​wynikowy kod jest bardziej wydajny pod względem pamięci. W ten sposób można nawet opisać strumienie danych, które byłyby po prostu zbyt duże, aby zmieściły się w pamięci.
  • Generatory umożliwiają naturalny sposób opisu nieskończonych strumieni. Weźmy na przykład liczby Fibonacciego :

    >>> def fib():
    ...     a, b = 0, 1
    ...     while True:
    ...         yield a
    ...         a, b = b, a + b
    ... 
    >>> import itertools
    >>> list(itertools.islice(fib(), 10))
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    

    Ten kod wykorzystuje itertools.islicedo pobierania skończonej liczby elementów z nieskończonego strumienia. Zaleca się przyjrzenie się funkcjom itertoolsmodułu, ponieważ są one niezbędnymi narzędziami do pisania zaawansowanych generatorów z wielką łatwością.


   O Pythonie <= 2.6: w powyższych przykładach nextjest funkcja, która wywołuje metodę __next__na danym obiekcie. W Pythonie <= 2.6 używa się nieco innej techniki, a mianowicie o.next()zamiast next(o). Python 2.7 ma next()wywołanie, .nextwięc nie musisz używać następujących w 2.7:

>>> g = (n for n in range(3, 5))
>>> g.next()
3
Stephan202
źródło
9
Wspominasz, że możliwe jest sendprzesył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ą one Locks, 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.
Jochen Ritzel
Czy generatory Python są w zasadzie maszynami Turinga pod względem ich działania?
Fiery Phoenix,
48

Generator jest faktycznie funkcją, która zwraca (dane) przed zakończeniem, ale zatrzymuje się w tym momencie i możesz wznowić funkcję w tym punkcie.

>>> def myGenerator():
...     yield 'These'
...     yield 'words'
...     yield 'come'
...     yield 'one'
...     yield 'at'
...     yield 'a'
...     yield 'time'

>>> myGeneratorInstance = myGenerator()
>>> next(myGeneratorInstance)
These
>>> next(myGeneratorInstance)
words

i tak dalej. (Lub jedną) zaletą generatorów jest to, że ponieważ zajmują się danymi pojedynczo, możesz poradzić sobie z dużymi ilościami danych; w przypadku list nadmierne wymagania dotyczące pamięci mogą stać się problemem. Generatory, podobnie jak listy, są iterowalne, więc można ich używać w ten sam sposób:

>>> for word in myGeneratorInstance:
...     print word
These
words
come
one
at 
a 
time

Zauważ, że generatory zapewniają na przykład inny sposób radzenia sobie z nieskończonością

>>> from time import gmtime, strftime
>>> def myGen():
...     while True:
...         yield strftime("%a, %d %b %Y %H:%M:%S +0000", gmtime())    
>>> myGeneratorInstance = myGen()
>>> next(myGeneratorInstance)
Thu, 28 Jun 2001 14:17:15 +0000
>>> next(myGeneratorInstance)
Thu, 28 Jun 2001 14:18:02 +0000   

Generator zawiera nieskończoną pętlę, ale nie stanowi to problemu, ponieważ każdą odpowiedź otrzymujesz tylko za każdym razem, gdy o nią poprosisz.

Caleb Hattingh
źródło
30

Po pierwsze, termin generator był początkowo źle zdefiniowany w Pythonie, co prowadziło do wielu nieporozumień. Prawdopodobnie średnie iteratory i iterables (patrz tutaj ). Następnie w Pythonie są również funkcje generatora (które zwracają obiekt generatora), obiekty generatora (które są iteratorami) i wyrażenia generatora (które są przetwarzane na obiekt generatora).

Zgodnie z glosariuszem dotyczącym generatora wydaje się, że oficjalna terminologia mówi teraz, że generator jest skrótem od „funkcji generatora”. W przeszłości dokumentacja definiowała warunki niekonsekwentnie, ale na szczęście zostało to naprawione.

Dobrym pomysłem może być precyzja i unikanie terminu „generator” bez dalszej specyfikacji.

nikow
źródło
2
Hmm, myślę, że masz rację, przynajmniej według testu kilku linii w Pythonie 2.6. Wyrażenie generatora zwraca iterator (inaczej „obiekt generatora”), a nie generator.
Craig McQueen,
22

Generatory można uznać za skrót do stworzenia iteratora. Zachowują się jak iterator Java. Przykład:

>>> g = (x for x in range(10))
>>> g
<generator object <genexpr> at 0x7fac1c1e6aa0>
>>> g.next()
0
>>> g.next()
1
>>> g.next()
2
>>> list(g)   # force iterating the rest
[3, 4, 5, 6, 7, 8, 9]
>>> g.next()  # iterator is at the end; calling next again will throw
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Mam nadzieję, że to pomaga / jest tym, czego szukasz.

Aktualizacja:

Jak pokazuje wiele innych odpowiedzi, istnieją różne sposoby tworzenia generatora. Możesz użyć składni w nawiasach jak w moim przykładzie powyżej lub możesz użyć dochodu. Inną ciekawą funkcją jest to, że generatory mogą być „nieskończone” - iteratory, które się nie zatrzymują:

>>> def infinite_gen():
...     n = 0
...     while True:
...         yield n
...         n = n + 1
... 
>>> g = infinite_gen()
>>> g.next()
0
>>> g.next()
1
>>> g.next()
2
>>> g.next()
3
...
przemyśleć
źródło
1
Teraz Java ma Streams, które są znacznie bardziej podobne do generatorów, z tym wyjątkiem, że najwyraźniej nie możesz po prostu zdobyć następnego elementu bez zaskakującej ilości problemów.
Pozew Fund Moniki w dniu
12

Nie ma odpowiednika Java.

Oto wymyślony przykład:

#! /usr/bin/python
def  mygen(n):
    x = 0
    while x < n:
        x = x + 1
        if x % 3 == 0:
            yield x

for a in mygen(100):
    print a

W generatorze jest pętla, która biegnie od 0 do n, a jeśli zmienna pętli jest wielokrotnością 3, to daje zmienną.

Podczas każdej iteracji forpętli generowany jest generator. Jeśli generator uruchamia się po raz pierwszy, uruchamia się na początku, w przeciwnym razie kontynuuje działanie od czasu poprzedniego wygenerowania.

Wernsey
źródło
2
Ostatni akapit jest bardzo ważny: stan funkcji generatora jest „zamrożony” za każdym razem, gdy daje coś, i zachowuje się dokładnie w tym samym stanie, gdy jest wywoływany następnym razem.
Johannes Charra,
W Javie nie ma syntaktycznego odpowiednika „wyrażenia generatora”, ale generatory - gdy już je masz - są w zasadzie tylko iteratorem (te same podstawowe cechy, co iterator Java).
przemyśleć
@ overthink: Cóż, generatory mogą mieć inne skutki uboczne, których nie mogą mieć iteratory Java. Gdybym położył się print "hello"za x=x+1przykładem, „hello” zostałoby wydrukowane 100 razy, podczas gdy ciało pętli for byłoby nadal wykonywane tylko 33 razy.
Wernsey,
@ iWerner: Jestem pewien, że ten sam efekt można uzyskać w Javie. Implementacja next () w równoważnym iteratorze Java nadal musiałaby wyszukiwać od 0 do 99 (używając przykładu mygen (100)), więc możesz System.out.println () za każdym razem, jeśli chcesz. Wrócisz tylko 33 razy od next (). W Javie brakuje bardzo przydatnej składni, która jest znacznie łatwiejsza do odczytu (i zapisu).
przemyślał
Uwielbiałem czytać i pamiętać tę definicję jednego wiersza: jeśli generator uruchamia się po raz pierwszy, uruchamia się na początku, w przeciwnym razie kontynuuje działanie od czasu poprzedniej pracy.
Iqra.
8

Lubię opisywać generatory, tym z dobrym doświadczeniem w językach programowania i informatyce, w kategoriach ramek stosu.

W wielu językach na stosie znajduje się stos „frame”. Ramka stosu zawiera miejsce przydzielone na zmienne lokalne dla funkcji, w tym argumenty przekazane do tej funkcji.

Po wywołaniu funkcji bieżący punkt wykonania („licznik programu” lub równoważny) jest wypychany na stos i tworzona jest nowa ramka stosu. Wykonanie przechodzi następnie na początek wywoływanej funkcji.

W przypadku zwykłych funkcji w pewnym momencie funkcja zwraca wartość, a stos jest „otwierany”. Ramka stosu funkcji jest odrzucana, a wykonywanie jest wznawiane w poprzedniej lokalizacji.

Gdy funkcja jest generatorem, może zwrócić wartość bez odrzucania ramki stosu, używając instrukcji fed. Wartości zmiennych lokalnych i licznik programu w funkcji są zachowane. Pozwala to na wznowienie działania generatora w późniejszym czasie, z kontynuowaniem wykonywania instrukcji return, i może wykonać więcej kodu i zwrócić inną wartość.

Przed Pythonem 2.5 działały już wszystkie generatory. Pyton 2,5 dodano możliwość przekazywania wartości z powrotem w celu generatora, jak również. W ten sposób przekazywana wartość jest dostępna jako wyrażenie wynikające z instrukcji return, która tymczasowo zwróciła kontrolę (i wartość) z generatora.

Kluczową zaletą generatorów jest to, że „stan” funkcji jest zachowany, w przeciwieństwie do zwykłych funkcji, w których za każdym razem, gdy ramka stosu jest odrzucana, tracisz cały ten „stan”. Druga zaleta polega na tym, że unika się niektórych narzutów wywołania funkcji (tworzenie i usuwanie ramek stosu), choć jest to zwykle niewielka zaleta.

Peter Hansen
źródło
6

Jedyną rzeczą, jaką mogę dodać do odpowiedzi Stephan202, jest zalecenie, aby spojrzeć na prezentację PyCon '08 Davida Beazleya „Generatory Tricks for Systems Programmers”, która jest najlepszym wyjaśnieniem tego, jak i dlaczego generatory, które widziałem gdziekolwiek. To właśnie zabrało mnie z „Python wygląda trochę zabawnie” na „Właśnie tego szukałem”. Jest na http://www.dabeaz.com/generators/ .

Robert Rossney
źródło
6

Pomaga dokonać wyraźnego rozróżnienia między funkcją foo a generatorem foo (n):

def foo(n):
    yield n
    yield n+1

foo jest funkcją. foo (6) jest obiektem generatora.

Typowy sposób użycia obiektu generatora to pętla:

for n in foo(6):
    print(n)

Pętla zostanie wydrukowana

# 6
# 7

Pomyśl o generatorze jako funkcji do wznowienia.

yieldzachowuje się tak, jakby returngenerowane wartości były „zwracane” przez generator. Jednak w przeciwieństwie do return, kiedy następnym razem generator zostanie poproszony o podanie wartości, funkcja generatora, foo, wznawia od miejsca, w którym została przerwana - po ostatniej instrukcji fed - i kontynuuje działanie, dopóki nie trafi do innej instrukcji fed.

Za kulisami, kiedy wywołujesz bar=foo(6)generator, pasek obiektu jest zdefiniowany, abyś miał nextatrybut.

Możesz to nazwać samemu, aby pobrać wartości uzyskane z foo:

next(bar)    # Works in Python 2.6 or Python 3.x
bar.next()   # Works in Python 2.5+, but is deprecated. Use next() if possible.

Kiedy foo kończy się (i nie ma już uzyskanych wartości), wywołanie next(bar)generuje błąd StopInteration.

unutbu
źródło
5

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 mainfunkcji.

Możemy zwrócić a vectorwartości i użyć iteratoriteracji 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 maini 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 mainnie 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

yieldOś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

Brian R. Bondy
źródło
3

Wierzę, że pierwsze pojawienie się iteratorów i generatorów miało miejsce w języku programowania Icon, około 20 lat temu.

Możesz cieszyć się przeglądem Icon , który pozwala ci owinąć głowę bez koncentrowania się na składni (ponieważ Icon jest językiem, którego prawdopodobnie nie znasz, a Griswold wyjaśniał zalety swojego języka osobom pochodzącym z innych języków).

Po przeczytaniu zaledwie kilku akapitów użyteczność generatorów i iteratorów może stać się bardziej widoczna.

Nosredna
źródło
2

Doświadczenie ze zrozumieniem list pokazało ich powszechne zastosowanie w Pythonie. Jednak wiele przypadków użycia nie musi mieć pełnej listy utworzonej w pamięci. Zamiast tego muszą tylko iterować elementy pojedynczo.

Na przykład poniższy kod sumowania utworzy pełną listę kwadratów w pamięci, powtórzy te wartości, a gdy odwołanie nie będzie już potrzebne, usunie listę:

sum([x*x for x in range(10)])

Pamięć jest zachowywana przez użycie zamiast tego wyrażenia generatora:

sum(x*x for x in range(10))

Podobne korzyści są przyznane konstruktorom obiektów kontenerowych:

s = Set(word  for line in page  for word in line.split())
d = dict( (k, func(k)) for k in keylist)

Wyrażenia generatora są szczególnie przydatne z funkcjami takimi jak sum (), min () i max (), które redukują iterowalne dane wejściowe do pojedynczej wartości:

max(len(line)  for line in file  if line.strip())

więcej

Saqib Mujtaba
źródło
1

Umieściłem ten fragment kodu, który wyjaśnia 3 kluczowe pojęcia dotyczące generatorów:

def numbers():
    for i in range(10):
            yield i

gen = numbers() #this line only returns a generator object, it does not run the code defined inside numbers

for i in gen: #we iterate over the generator and the values are printed
    print(i)

#the generator is now empty

for i in gen: #so this for block does not print anything
    print(i)
Stefan Iancu
źródło