Python Language
generatorer

Introduktion

Syntax

• utbyte <expr>
• utbyte från <expr>
• <var> = utbyte <expr>
• nästa ( <iter> )

Iteration

Ett generatorobjekt stöder iteratorprotokollet . Det vill säga den tillhandahåller en next() -metod ( __next__() i Python 3.x), som används för att gå igenom dess körning, och dess __iter__ metod returnerar sig själv. Detta innebär att en generator kan användas i alla språkkonstruktioner som stöder generiska iterbara objekt.

# naive partial implementation of the Python 2.x xrange()
def xrange(n):
    i = 0
    while i < n:
        yield i
        i += 1

# looping
for i in xrange(10):
    print(i)  # prints the values 0, 1, ..., 9

# unpacking
a, b, c = xrange(3)  # 0, 1, 2

# building a list
l = list(xrange(10))  # [0, 1, ..., 9]

Nästa funktion ()

next() inbyggda är ett bekvämt omslag som kan användas för att ta emot ett värde från vilken iterator som helst (inklusive en generator-iterator) och för att tillhandahålla ett standardvärde om iteratorn är slut.

def nums():
    yield 1
    yield 2
    yield 3
generator = nums()

next(generator, None)  # 1
next(generator, None)  # 2
next(generator, None)  # 3
next(generator, None)  # None
next(generator, None)  # None
# ...

Syntaxen är next(iterator[, default]) . Om iteratorn slutar och ett standardvärde har passerat, returneras det. Om ingen standard tillhandahålls, StopIteration .

Skicka objekt till en generator

Förutom att ta emot värden från en generator är det möjligt att skicka ett objekt till en generator med metoden send() .

def accumulator():
    total = 0
    value = None
    while True:
        # receive sent value
        value = yield total
        if value is None: break
        # aggregate values
        total += value

generator = accumulator()

# advance until the first "yield"
next(generator)      # 0

# from this point on, the generator aggregates values
generator.send(1)    # 1
generator.send(10)   # 11
generator.send(100)  # 111
# ...

# Calling next(generator) is equivalent to calling generator.send(None)
next(generator)      # StopIteration

Vad som händer här är följande:

• När du först ringer next(generator) går programmet vidare till det första yield och returnerar värdet på total vid den punkten, som är 0. Genomförandet av generatorn stängs av vid denna punkt.
• När du sedan anropar generator.send(x) tar tolkaren argumentet x och gör det till returvärdet för det sista yield , som tilldelas value . Generatorn fortsätter sedan som vanligt tills den ger nästa värde.
• När du äntligen ringer next(generator) , behandlar programmet detta som om du skickar None till generatorn. Det finns inget speciellt med None , men detta exempel använder None som ett specialvärde för att be generatorn att stoppa.

Generatoriska uttryck

Det är möjligt att skapa generator iteratorer med en förståelse-liknande syntax.

generator = (i * 2 for i in range(3))

next(generator)  # 0
next(generator)  # 2
next(generator)  # 4
next(generator)  # raises StopIteration

Om en funktion inte nödvändigtvis behöver ges en lista kan du spara på tecken (och förbättra läsbarheten) genom att placera ett generatoruttryck i ett funktionssamtal. Parentesen från funktionsanropet implicit gör ditt uttryck till ett generatoruttryck.

sum(i ** 2 for i in range(4))  # 0^2 + 1^2 + 2^2 + 3^2 = 0 + 1 + 4 + 9 = 14

Dessutom kommer du att spara på minnet eftersom istället för att ladda hela listan du iterera över ( [0, 1, 2, 3] i exemplet ovan) tillåter generatorn Python att använda värden efter behov.

Introduktion

Generatoruttryck liknar lista, ordlista och uppsättningar, men har med parenteser. Parenteserna behöver inte vara när de används som det enda argumentet för ett funktionssamtal.

expression = (x**2 for x in range(10))

Detta exempel genererar de 10 första perfekta rutorna, inklusive 0 (där x = 0).

Generatorfunktioner liknar vanliga funktioner, förutom att de har en eller flera yield i kroppen. Sådana funktioner kan inte return några värden (emellertid är tomma return tillåtna om du vill stoppa generatorn tidigt).

def function():
    for x in range(10):
        yield x**2

Denna generatorfunktion motsvarar det föregående generatoruttrycket, den matar ut samma sak.

Obs : alla generatoruttryck har sina egna ekvivalenta funktioner, men inte tvärtom.

Ett generatoruttryck kan användas utan parenteser om båda parenteserna skulle upprepas på annat sätt:

sum(i for i in range(10) if i % 2 == 0)   #Output: 20
any(x = 0 for x in foo)                   #Output: True or False depending on foo
type(a > b for a in foo if a % 2 == 1)    #Output: <class 'generator'>

Istället för:

sum((i for i in range(10) if i % 2 == 0))
any((x = 0 for x in foo))
type((a > b for a in foo if a % 2 == 1))

Men inte:

fooFunction(i for i in range(10) if i % 2 == 0,foo,bar)
return x = 0 for x in foo
barFunction(baz, a > b for a in foo if a % 2 == 1)

Att ringa en generatorfunktion producerar ett generatorobjekt som senare kan itereras. Till skillnad från andra typer av iteratorer, kan generatorobjekt bara korsas en gång.

g1 = function()
print(g1)  # Out: <generator object function at 0x1012e1888>

Lägg märke till att en generatorkropp inte omedelbart körs: när du ringer function() i exemplet ovan returnerar den omedelbart ett generatorobjekt utan att ens utföra det första utskriftsmeddelandet. Detta gör att generatorer kan konsumera mindre minne än funktioner som returnerar en lista, och det gör det möjligt att skapa generatorer som producerar oändligt långa sekvenser.

Av denna anledning används generatorer ofta inom datavetenskap och andra sammanhang som involverar stora datamängder. En annan fördel är att annan kod omedelbart kan använda värdena som genereras av en generator, utan att vänta på att hela sekvensen ska produceras.

Men om du behöver använda värdena som produceras av en generator mer än en gång, och om att generera dem kostar mer än lagring, kan det vara bättre att lagra de avgivna värdena som en list än att generera sekvensen igen. Se 'Återställa en generator' nedan för mer information.

Typiskt används ett generatorobjekt i en slinga, eller i vilken funktion som helst som kräver en iterbar:

for x in g1:
    print("Received", x)

# Output:
# Received 0
# Received 1
# Received 4
# Received 9
# Received 16
# Received 25
# Received 36
# Received 49
# Received 64
# Received 81

arr1 = list(g1)
# arr1 = [], because the loop above already consumed all the values.
g2 = function()
arr2 = list(g2)  # arr2 = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Eftersom generatorobjekt är iteratorer, kan man iterera över dem manuellt med next() -funktion. Om du gör det kommer de returnerade värdena en efter en att återkommas vid varje efterföljande åkallande.

Under huven, Python kör varje gång du anropar next() på en generator uttalanden i generatorfunktionens kropp tills den träffar nästa yield . Vid denna punkt returnerar det argumentet för yield och kommer ihåg punkten där det hände. Att ringa next() återigen kommer att återuppta körningen från den punkten och fortsätta tills nästa yield .

Om Python når slutet av generatorfunktionen utan att stöta på någon mer yield s, a StopIteration är undantag höjs (detta är normalt, alla iteratorer beter sig på samma sätt).

g3 = function()
a = next(g3)  # a becomes 0
b = next(g3)  # b becomes 1
c = next(g3)  # c becomes 2
...
j = next(g3)  # Raises StopIteration, j remains undefined

Observera att i Python 2-generatorobjekt hade .next() -metoder som kan användas för att iterera genom de avgivna värdena manuellt. I Python 3 ersattes denna metod med .__next__() -standard för alla iteratorer.

Återställ en generator

Kom ihåg att du bara kan iterera igenom de objekt som genereras av en generator en gång . Om du redan har itererat igenom objekten i ett skript kommer varje ytterligare försök att göra det att ge None .

Om du behöver använda objekten som genereras av en generator mer än en gång kan du antingen definiera generatorfunktionen igen och använda den en andra gång, eller alternativt kan du lagra generatorfunktionens utgång i en lista vid första användningen. Att definiera generatorfunktionen på nytt är ett bra alternativ om du har att göra med stora datamängder, och att lagra en lista med alla dataelement skulle ta mycket skivutrymme. Omvänt, om det är kostsamt att generera objekten initialt, kanske du föredrar att lagra de genererade objekten i en lista så att du kan återanvända dem.

Använda en generator för att hitta Fibonacci-nummer

Ett praktiskt användningsfall för en generator är att iterera genom värden i en oändlig serie. Här är ett exempel på att hitta de första tio termerna i Fibonacci-sekvensen .

def fib(a=0, b=1):
    """Generator that yields Fibonacci numbers. `a` and `b` are the seed values"""
    while True:
        yield a
        a, b = b, a + b

f = fib()
print(', '.join(str(next(f)) for _ in range(10)))

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Oändliga sekvenser

Generatorer kan användas för att representera oändliga sekvenser:

def integers_starting_from(n):
    while True:
        yield n
        n += 1

natural_numbers = integers_starting_from(1)

Oändlig antal sekvenser som ovan kan också genereras med hjälp av itertools.count . Ovanstående kod kan skrivas enligt nedan

natural_numbers = itertools.count(1)

Du kan använda generatorförståelser på oändliga generatorer för att producera nya generatorer:

multiples_of_two = (x * 2 for x in natural_numbers)
multiples_of_three = (x for x in natural_numbers if x % 3 == 0)

Var medveten om att en oändlig generator inte har något slut, så att vidarebefordra den till någon funktion som kommer att försöka konsumera generatorn helt kommer att få allvarliga konsekvenser :

list(multiples_of_two)  # will never terminate, or raise an OS-specific error

Använd istället lista / uppsättningar med range (eller xrange för python <3.0):

first_five_multiples_of_three = [next(multiples_of_three) for _ in range(5)] 
# [3, 6, 9, 12, 15]

eller använd itertools.islice() att skära iteratorn till en delmängd:

from itertools import islice
multiples_of_four = (x * 4 for x in integers_starting_from(1))
first_five_multiples_of_four = list(islice(multiples_of_four, 5))
# [4, 8, 12, 16, 20]

Observera att originalgeneratorn också är uppdaterad, precis som alla andra generatorer som kommer från samma "root":

next(natural_numbers)    # yields 16
next(multiples_of_two)   # yields 34
next(multiples_of_four)  # yields 24

En oändlig sekvens kan också itereras med en for loop . Se till att inkludera ett villkorligt break uttalande så att slingan slutligen slutar:

for idx, number in enumerate(multiplies_of_two):
    print(number)
    if idx == 9:
        break  # stop after taking the first 10 multiplies of two

Klassiskt exempel - Fibonacci-nummer

import itertools

def fibonacci():
    a, b = 1, 1
    while True:
        yield a
        a, b = b, a + b

first_ten_fibs = list(itertools.islice(fibonacci(), 10))
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

def nth_fib(n):
    return next(itertools.islice(fibonacci(), n - 1, n))

ninety_nineth_fib = nth_fib(99)  # 354224848179261915075

Att ge alla värden från en annan iterable

def foob(x):
    yield from range(x * 2)
    yield from range(2)

list(foob(5))  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]

def fibto(n):
    a, b = 1, 1
    while True:
        if a >= n: break
        yield a
        a, b = b, a + b

def usefib():
    yield from fibto(10)
    yield from fibto(20)

list(usefib())  # [1, 1, 2, 3, 5, 8, 1, 1, 2, 3, 5, 8, 13]

korutin

Generatorer kan användas för att implementera koroutiner:

# create and advance generator to the first yield
def coroutine(func):
    def start(*args,**kwargs):
        cr = func(*args,**kwargs)
        next(cr)
        return cr
    return start

# example coroutine
@coroutine
def adder(sum = 0):
    while True:
        x = yield sum
        sum += x

# example use
s = adder()
s.send(1) # 1
s.send(2) # 3

Coroutines används vanligtvis för att implementera tillståndsmaskiner, eftersom de främst är användbara för att skapa procedurer med en enda metod som kräver att ett tillstånd fungerar korrekt. De verkar i ett befintligt tillstånd och returnerar värdet som erhålls efter operationens slut.

Utbyte med rekursion: rekursivt listar alla filer i en katalog

Först importera biblioteken som fungerar med filer:

from os import listdir
from os.path import isfile, join, exists

En hjälpfunktion för att bara läsa filer från en katalog:

def get_files(path):
    for file in listdir(path):
        full_path = join(path, file)
        if isfile(full_path):
            if exists(full_path):
                yield full_path

En annan hjälpfunktion för att få endast underkataloger:

def get_directories(path):
    for directory in listdir(path):
        full_path = join(path, directory)
        if not isfile(full_path):
            if exists(full_path):
                yield full_path

Använd nu dessa funktioner för att rekursivt få alla filer i en katalog och alla dess underkataloger (med hjälp av generatorer):

def get_files_recursive(directory):
    for file in get_files(directory):
        yield file
    for subdirectory in get_directories(directory):
        for file in get_files_recursive(subdirectory): # here the recursive call
            yield file

Denna funktion kan förenklas med yield from :

def get_files_recursive(directory):
    yield from get_files(directory)
    for subdirectory in get_directories(directory):
        yield from get_files_recursive(subdirectory)

Iterera över generatorer parallellt

För att iterera över flera generatorer parallellt använder du den inbyggda zip :

for x, y in zip(a,b):
    print(x,y)

Resulterar i:

1 x
2 y
3 z

I python 2 bör du använda itertools.izip istället. Här kan vi också se att alla zip funktioner ger tuples.

Observera att zip kommer att sluta upprepas så snart en av de iterables går slut. Om du vill iterera så länge som den längsta iterbara, använd itertools.zip_longest() .

Refactoring lista byggande kod

Anta att du har en komplex kod som skapar och returnerar en lista genom att börja med en tom lista och flera gånger lägga till den:

def create():
    result = []
    # logic here...
    result.append(value) # possibly in several places
    # more logic...
    return result # possibly in several places

values = create()

När det inte är praktiskt att ersätta den inre logiken med en listaförståelse, kan du förvandla hela funktionen till en generator på plats och sedan samla in resultaten:

def create_gen():
    # logic...
    yield value
    # more logic
    return # not needed if at the end of the function, of course

values = list(create_gen())

Om logiken är rekursiv, använd yield from att inkludera alla värden från det rekursiva samtalet i ett "plattat" resultat:

def preorder_traversal(node):
    yield node.value
    for child in node.children:
        yield from preorder_traversal(child)

Sökande

next funktion är användbar även utan att upprepas. Att skicka ett generatoruttryck till next är ett snabbt sätt att söka efter den första förekomsten av ett element som matchar något predikat. Procedurkod som

def find_and_transform(sequence, predicate, func):
    for element in sequence:
        if predicate(element):
            return func(element)
    raise ValueError

item = find_and_transform(my_sequence, my_predicate, my_func)

kan ersättas med:

item = next(my_func(x) for x in my_sequence if my_predicate(x))
# StopIteration will be raised if there are no matches; this exception can
# be caught and transformed, if desired.

För detta ändamål kan det vara önskvärt att skapa ett alias, till exempel first = next , eller en omslagsfunktion för att konvertera undantaget:

def first(generator):
    try:
        return next(generator)
    except StopIteration:
        raise ValueError