Python Language
generatori

introduzione

Sintassi

• resa <expr>
• rendimento da <expr>
• <var> = rendimento <expr>
• next ( <iter> )

Iterazione

Un oggetto generatore supporta il protocollo iteratore . Vale a dire, fornisce un metodo next() ( __next__() in Python 3.x), che viene usato per passare attraverso la sua esecuzione, e il suo metodo __iter__ restituisce sé stesso. Ciò significa che un generatore può essere utilizzato in qualsiasi costrutto linguistico che supporti oggetti iterabili generici.

# 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]

La funzione next ()

Il next() built-in è un comodo wrapper che può essere usato per ricevere un valore da qualsiasi iteratore (incluso un iteratore di generatore) e per fornire un valore predefinito nel caso in cui l'iteratore sia esaurito.

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

La sintassi è next(iterator[, default]) . Se l'iteratore termina e viene passato un valore predefinito, viene restituito. Se non è stato fornito alcun valore predefinito, StopIteration viene generato.

Invio di oggetti a un generatore

Oltre a ricevere i valori da un generatore, è possibile inviare un oggetto a un generatore usando il metodo 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

Quello che succede qui è il seguente:

• Alla prima chiamata next(generator) , il programma avanza alla prima dichiarazione di yield e restituisce il valore total a quel punto, che è 0. L'esecuzione del generatore viene sospesa a questo punto.
• Quando si chiama generator.send(x) , l'interprete prende l'argomento x e lo rende il valore di ritorno dell'ultima dichiarazione di yield , che viene assegnata al value . Il generatore procede come al solito, finché non produce il valore successivo.
• Quando finalmente si chiama next(generator) , il programma lo tratta come se invii None al generatore. Non c'è nulla di speciale in None , tuttavia, questo esempio usa None come valore speciale per chiedere al generatore di fermarsi.

Espressioni del generatore

È possibile creare iteratori di generatore utilizzando una sintassi simile alla comprensione.

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

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

Se non è necessario che una funzione passi una lista, è possibile salvare sui caratteri (e migliorare la leggibilità) inserendo un'espressione di generatore all'interno di una chiamata di funzione. La parentesi della chiamata di funzione rende implicitamente la tua espressione un'espressione di generatore.

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

Inoltre, si risparmia sulla memoria perché invece di caricare l'intero elenco su cui si sta iterando ( [0, 1, 2, 3] nell'esempio precedente), il generatore consente a Python di utilizzare i valori secondo necessità.

introduzione

Le espressioni del generatore sono simili a list, dictionary e set comprehensions, ma sono racchiuse tra parentesi. Le parentesi non devono essere presenti quando vengono utilizzate come unico argomento per una chiamata di funzione.

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

Questo esempio genera i primi 10 quadrati perfetti, incluso 0 (in cui x = 0).

Le funzioni del generatore sono simili alle funzioni regolari, tranne che hanno una o più dichiarazioni di yield nel loro corpo. Tali funzioni non possono return alcun valore (tuttavia è possibile return vuoti se si desidera arrestare anticipatamente il generatore).

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

Questa funzione del generatore è equivalente alla precedente espressione del generatore, emette lo stesso risultato.

Nota : tutte le espressioni del generatore hanno le loro funzioni equivalenti , ma non viceversa.

Un'espressione di generatore può essere utilizzata senza parentesi se entrambe le parentesi si ripetessero diversamente:

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'>

Invece di:

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))

Ma no:

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)

Chiamando una funzione generatore si genera un oggetto generatore , che può essere successivamente ripetuto. A differenza di altri tipi di iteratori, gli oggetti generatore possono essere attraversati solo una volta.

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

Si noti che il corpo di un generatore non viene immediatamente eseguito: quando si chiama function() nell'esempio precedente, viene immediatamente restituito un oggetto generatore, senza eseguire nemmeno la prima istruzione print. Ciò consente ai generatori di consumare meno memoria rispetto alle funzioni che restituiscono una lista e consente la creazione di generatori che producono sequenze infinitamente lunghe.

Per questo motivo, i generatori vengono spesso utilizzati nella scienza dei dati e in altri contesti che coinvolgono grandi quantità di dati. Un altro vantaggio è che l'altro codice può utilizzare immediatamente i valori prodotti da un generatore, senza attendere che venga prodotta la sequenza completa.

Tuttavia, se è necessario utilizzare i valori prodotti da un generatore più di una volta, e se generarli costa più della memorizzazione, potrebbe essere preferibile memorizzare i valori ottenuti come list piuttosto che rigenerare la sequenza. Vedi 'Ripristino di un generatore' sotto per maggiori dettagli.

In genere un oggetto generatore viene utilizzato in un ciclo o in qualsiasi funzione che richiede un iterable:

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]

Poiché gli oggetti generatore sono iteratori, uno può scorrere su di essi manualmente usando la funzione next() . Fare così restituirà i valori ottenuti uno per uno su ogni chiamata successiva.

Sotto il cofano, ogni volta che chiamate next() su un generatore, Python esegue istruzioni nel corpo della funzione generatore fino a quando non raggiunge la successiva dichiarazione di yield . A questo punto restituisce l'argomento del comando yield e ricorda il punto in cui è successo. Chiamando next() ancora una volta riprenderà l'esecuzione da quel punto e continuerà fino alla prossima dichiarazione di yield .

Se Python raggiunge la fine della funzione del generatore senza incontrare altri yield s, viene sollevata un'eccezione StopIteration (questo è normale, tutti gli iteratori si comportano allo stesso modo).

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

Si noti che in Python 2 gli oggetti del generatore avevano metodi .next() che potevano essere utilizzati per scorrere manualmente i valori ottenuti. In Python 3 questo metodo è stato sostituito con lo standard .__next__() per tutti gli iteratori.

Reimpostazione di un generatore

Ricorda che puoi solo scorrere gli oggetti generati da un generatore una sola volta . Se avete già iterato attraverso gli oggetti in uno script, ogni ulteriore tentativo di farlo produrrà None .

Se è necessario utilizzare gli oggetti generati da un generatore più di una volta, è possibile definire nuovamente la funzione generatore e utilizzarla una seconda volta oppure, in alternativa, è possibile memorizzare l'uscita della funzione generatore in un elenco al primo utilizzo. La ridefinizione della funzione del generatore sarà una buona opzione se si hanno a che fare con grandi volumi di dati e la memorizzazione di un elenco di tutti gli elementi di dati richiederebbe molto spazio sul disco. Viceversa, se inizialmente è costoso generare gli articoli, è preferibile memorizzare gli articoli generati in un elenco in modo da poterli riutilizzare.

Usare un generatore per trovare i numeri di Fibonacci

Un caso pratico d'uso di un generatore è quello di scorrere i valori di una serie infinita. Ecco un esempio di come trovare i primi dieci termini della sequenza di Fibonacci .

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

Sequenze infinite

I generatori possono essere utilizzati per rappresentare sequenze infinite:

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

natural_numbers = integers_starting_from(1)

La sequenza infinita di numeri come sopra può anche essere generata con l'aiuto di itertools.count . Il codice sopra potrebbe essere scritto come sotto

natural_numbers = itertools.count(1)

È possibile utilizzare la comprensione del generatore su generatori infiniti per produrre nuovi generatori:

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

Siate consapevoli del fatto che un generatore infinito non ha una fine, quindi passarlo a qualsiasi funzione che tenterà di consumare del tutto il generatore avrà conseguenze disastrose :

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

Invece, usa list / set comprehensions con range (o xrange per python <3.0):

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

oppure usa itertools.islice() per itertools.islice() l'iteratore in un sottoinsieme:

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]

Nota che anche il generatore originale viene aggiornato, proprio come tutti gli altri generatori che provengono dalla stessa "root":

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

Una sequenza infinita può anche essere iterata con un for -loop . Assicurati di includere un'istruzione di break condizionale in modo che il ciclo possa terminare alla fine:

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

Esempio classico: numeri di Fibonacci

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

Cedendo tutti i valori da un altro iterabile

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]

coroutine

I generatori possono essere utilizzati per implementare le coroutine:

# 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

Coroutine sono comunemente utilizzate per implementare macchine a stati, in quanto sono principalmente utili per la creazione di procedure a metodo singolo che richiedono uno stato per funzionare correttamente. Operano su uno stato esistente e restituiscono il valore ottenuto al termine dell'operazione.

Resa con ricorsione: elenca in modo ricorsivo tutti i file in una directory

Innanzitutto, importa le librerie che funzionano con i file:

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

Una funzione di supporto per leggere solo i file da una directory:

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

Un'altra funzione di supporto per ottenere solo le sottodirectory:

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

Ora usa queste funzioni per ottenere ricorsivamente tutti i file all'interno di una directory e tutte le sue sottodirectory (usando i generatori):

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

Questa funzione può essere semplificata utilizzando il yield from :

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

Iterazione su generatori in parallelo

Per eseguire un'iterazione su più generatori in parallelo, utilizzare lo zip incorporato:

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

Risultati in:

1 x
2 y
3 z

In python 2 dovresti invece usare itertools.izip . Qui possiamo anche vedere che tutte le funzioni di zip producono tuple.

Nota che zip interromperà l'iterazione non appena uno degli iterabili finirà gli elementi. Se desideri ripetere l'iterazione fino a quando è il più lungo iterabile, usa itertools.zip_longest() .

Refactoring code-list code

Supponiamo che tu abbia un codice complesso che crea e restituisce un elenco iniziando da un elenco vuoto e aggiungendolo ripetutamente ad esso:

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

values = create()

Quando non è pratico sostituire la logica interna con una comprensione di lista, puoi trasformare l'intera funzione in un generatore sul posto e quindi raccogliere i risultati:

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

values = list(create_gen())

Se la logica è ricorsiva, usa yield from per includere tutti i valori della chiamata ricorsiva in un risultato "appiattito":

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

Ricerca

La next funzione è utile anche senza iterare. Passare un'espressione di generatore al next è un modo rapido per cercare la prima occorrenza di un elemento che corrisponde ad un predicato. Codice procedurale come

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)

può essere sostituito con:

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.

A tale scopo, potrebbe essere opportuno creare un alias, come first = next , o una funzione wrapper per convertire l'eccezione:

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