Iteradores

Já vimos que objetos que são sequências e coleções podem ser lidos iterativamente com o uso do operador for.

» lista = ['Aa', 'Bb', 'Cc', 'Dd', 'Ee', 'Ff']
» for t in lista:
»     print(t, end=' < ')
↳ Aa < Bb < Cc < Dd < Ee < Ff <

Laços for são claros e concisos. Por trás desse resultado simples, a instrução for chama a função iter() na sequência (ou coleção) que retorna um objeto iterador. Dentro do iterador existe o método __next__() que acessa os elementos no contêiner um de cada vez. Ao final da iteração, quando se extinguem os elementos, __next__() levanta uma exceção StopIteration que é reconhecida pelo laço como o fim da iteração. O método __next__() pode ser chamado através da função interna next(), como mostra o exemplo:

» iterador = iter('OMS')
» print(next(iterador))
» print(next(iterador))
» print(next(iterador))
» print(next(iterador))
↳ O
↳ M
↳ S
↳ StopIteration:

No código acima usamos iter(sequencia) que retorna um iterável da sequência ‘OMS’. StopIteration é uma mensagem de erro ao final da iteração, com o iterador esgotado. Ela aparece aqui resumida.

Podemos construir uma classe iterável implementado nela os métodos __iter__() e __next__(). No caso abaixo a classe simplesmente retorna a sequência invertida, do último elemento para o primeiro

» class Inverter:
»     def __init__(self, data):
»         self.data = data
»         self.index = len(data)

»     def __iter__(self):
»         return self

»     def __next__(self):
»         if self.index == 0:
»             raise StopIteration
»         self.index -= 1
»         return self.data[self.index]

# instanciamos um objeto Inverter usando uma lista como argumento
» inv = Inverter(['Aa', 'Bb', 'Cc', 'Dd', 'Ee', 'Ff'])

» for t in inv:
»     print(t, end=' < ')
↳ Ff < Ee < Dd < Cc < Bb < Aa <

# seq é Inverter usando uma string como argumento
» seq = Inverter('Joazeiro')
» for t in seq:
»     print(t, end=' < ')
↳ o < r < i < e < z < a < o < J <     

Sequências podem ser transformados em iteradores com as funções:

que, como vimos, são úteis quando usadas com loops for, while. Por exemplo, com uma lista (ou uma tupla):

» x = ["apple", "banana", "cherry"]
» print(next(x))
↳ TypeError: 'list' object is not an iterator

» # transformado a lista em um iterador
» x = iter(["apple", "banana", "cherry"])
» print(next(x), next(x), next(x))
↳ apple banana cherry

Um objeto zip() é um iterador que junta duas sequências e retorna tuplas com elementos das sequências em seus argumentos.

» z = zip(['a', 'b', 'c', 'd'], [1, 2, 3, 4])
» print(next(z))
» print(next(z))
↳ ('a', 1)
↳ ('b', 2)

Da mesma forma map retorna um iterável.

» m = map(lambda x, y: x**y, [8, 2, 9], [5, 3, 7])
» print(next(m))
» print(next(m))
» print(next(m))
↳ 32768
↳ 8
↳ 4782969

# outro exemplo
» list(map(len, ['Abacate', 'Uva', 'Jacoticaba']))
↳ [7, 3, 10] 

Observe que um objeto pode ser um iterável (como uma lista) mas não ser um iterador. No entanto ele pode ser transformado um um iterador.

» numeros = [1, 2, 3, 4, 5]
» next(numeros)
↳ TypeError: 'list' object is not an iterator

» i = iter(numeros)
» next(i)
↳ 1
» next(i)
↳ 2
» # o estado do iterador é armazenado entre iterações
» for x in i:
»     print(x, end=' ')
↳ 3 4 5

Muitas das funções do Python retornam iteradores ao invés de listas ou tuplas. Por exemplo enumerate, reversede open(file)retornam iteradores.

» alunos = ['Pedro', 'Maria', 'Marco']
» nAluno = enumerate(alunos)        # enumerate
» next(nAluno)
↳ (0, 'Pedro')

» for t in nAluno:
»     print(t)
↳ (1, 'Maria')
↳ (2, 'Marco')

» invertido = reversed(alunos)       # reversed
» next(invertido)
↳ 'Marco'

» f = open('./dados/linhas.txt')     # arquivo
» next(f)
↳ 'Esta é a linha 1\n'

Por outro lado muitas funções internas (e das bibliotecas) aceitam iteráveis (e iteradores) como parâmetros. Abaixo exemplos do uso de zip, dict recebendo iteradores.

» numeros = [10, 20, 30]
» quadrados = (n**2 for n in numeros)
» quadrados    # é um objeto generator (que é um iterador)
↳ <generator object <genexpr> at 0x7f67280c1120>

» z = zip(numeros, quadrados)        # zip recebe um iterador como argumento
» print(next(z), next(z), next(z))
↳ (10, 100) (20, 400) (30, 900)

» # Um dicionário pode receber um iterável como argumento
» alunos = ['Pedro', 'Maria', 'Marco']
» nAluno = enumerate(alunos)         # um iterador
» d = dict(nAluno)
» d
↳ {0: 'Pedro', 1: 'Maria', 2: 'Marco'}

Módulo itertools

Um módulo da biblioteca padrão interessante para manipulação de iteradores é o itertools, que contém diversos métodos para manipulação de iteráveis e funções que retornam iteráveis. Elas são voltadas para a velocidade de execução e uso otimizado de memória.

Existem dois tipos de interadores: iteradores infinitos continuam a rodar indefinidamente se nenhuma condição de parada for imposta, enquanto os iteradores finitos são criados com um número determinado de ciclos determinados. O módulo Itertools possui funções de cada tipo:

Iteradores finitos

Função chain(): A função chain reune listas transformando-as em um único iterável.

» import itertools as it
» abc = ['Aa', 'Bb', 'Cc']
» vxz = ['Vv', 'Xx', 'Zz']
» for txt in it.chain(abc, vxz):
»     print(txt, end=' ')
↳ Aa Bb Cc Vv Xx Zz 

» # o objeto retornado por chain é um iterável: 
» letras = it.chain(abc, vxz)
» for i in range(3):
»     print(next(letras), end=' ')
» print(next(letras), next(letras), next(letras))
↳ Aa Bb Cc Vv Xx Zz

Os argumentos de chain(iteravel,...) podem ser de qualquer tipo, desde que iteráveis. Por exemplo, podemos juntar uma lista, um dicionário e um it.count():

» lista = ['Aa', 'Bb', 'Cc']
» dicio = {'G': 'g', 'H': 'h'}
» conta = it.count()
» for k in it.chain(lista, dicio.items(), conta):
»     print(k, end=' ')
↳ Aa Bb Cc ('G', 'g') ('H', 'h') 0 1 2 3 4 5 6 7 8 9 10 ...

O 4º e 5º loop retornam as tuplas do dicionário. Em seguida os inteiros são retornados. (A exibição foi interrompida manualmente!)

Função compressed(iteravel, seletor): compressed recebe um iterável e um seletor (uma lista de booleanos) e retorna um iterável filtrado pelo seletor, contendo apenas elementos onde o seletor é True.

» aluno = ['Paulo', 'Maria', 'Ricardo']
» aprovado = [False, True, True]
» for n in it.compress(aluno, aprovado):
»     print(n, end=' ')
↳ Maria Ricardo 

Os argumentos de compressed podem ser iteráveis com infinitos elementos. Por exemplo, abaixo construímos o iterador com elementos True ou False dependendo de ser o número par ou impar.

» par = (x%2==0 for x in it.count())
» for pares in it.compress(it.count(), par):
»     print(pares, end=' ')
↳ 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 ...

Função tee(iteravel): recebe um iterável e retorna dois objetos clonados do original. O iterável original fica esgotado depois da operação. Também é possível passar um parâmetro para gerar n clones, em itertools.tee(iteravel, n).

» elementos = (x**x for x in range(6) if x**x%2==0)
» lista1, lista2 = it.tee(elementos)
» print(lista1)                      # as listas são objetos itertools._tee
↳ <itertools._tee object at 0x7fc032da5ac0>

» print(list(lista1), list(lista2))
↳ ['1', '2', '3'] ['1', '2', '3']
» print(list(elementos))             # a lista original fica esgotada
↳ []

# um parâmetro pode ser passado para gerar n clones
» vitaminas = ['A', 'B12']
» vitas = it.tee(vitaminas, 4)
» for i in vitas:
»     print(list(i), end=' ')
↳ ['A', 'B12'] ['A', 'B12'] ['A', 'B12'] ['A', 'B12'] 

Função dropwhile(função, iteravel): recebe um iterável e uma função seletora (que avalia cada elemento do iterável como um booleano) e retorna os elementos do iterável à partir do primeiro retorno False da função. Em outras palavras ela descarta os elementos avaliados como True no início da lista (ou iterável). Podemos obter a lista à partir do último valor avaliado como False com reversed(lista).

» def par(x):                       # retorna True se x é par
»     return x % 2 == 0
» numeros = [0, 2, 4, 8, 16, 17, 32, 64, 67, 128]

» # o primeiro False ocorre em 17
» for t in it.dropwhile(par, numeros):
»     print(t, end=' ')
↳ 17 32 64 67 128

» # o mesmo pode ser conseguido com uma função lambda
» print(list(it.dropwhile(lambda t: t%2==0 , numeros)))
↳ [17, 32, 64, 67, 128]

» # lista anterior ao último valor avaliado como False (em ordem reversa)
» print(list(it.dropwhile(lambda t: t%2==0 , reversed(numeros))))
↳ [67, 64, 32, 17, 16, 8, 4, 2, 0]

Função takewhile(função, iteravel): retorna todos os termos iniciais de um iterável até que um de seus elementos avalie como False pela função. Os demais elementos, mesmo que avaliando como True, são descartados.

» anos = [10,30,50, 70, 90, 110, 1, 2, 3]
» take = it.takewhile(lambda x: x < 100, anos)
» for a in take:
»     print(a, end= ' ')
↳ 10 30 50 70 90 

Função itertools.zip_longest(iter1, iter2): diferente da função interna zip(), zip_longest(iter1, iter2) retorna um iterador com o comprimento da maior entre iter1, iter2, substituindo valores ausentes por None.

» # usando zip (built-in)    
» x = [0, 1, 2, 3, 4, 5]
» y = ['A', 'B', 'C']
» list(zip(x, y))
↳ [(0, 'A'), (1, 'B'), (2, 'C')]

» # usando itertools.zip_longest
» list(it.zip_longest(x, y))
↳ [(0, 'A'), (1, 'B'), (2, 'C'), (3, None), (4, None), (5, None)]

Iteradores infinitos

Função count(): a funçãocount() produz uma sequência de comprimento indefinido de inteiros, apropriada para contagem.

» import itertools as it
» t = 0
» for x in it.count():
»     if x > 10: break
»     print(x, end=' ')
↳ 0 1 2 3 4 5 6 7 8 9 10    

Se uma condição de parada do loop não for inserida ele gera uma quantidade indefinida de números. A função pode receber os parâmetroscount(inicio, passo), para indicar o início da contagem é o incremento.

» for i in it.count(10, 2):
»     if i > 24:
»         break
»     else:
»         print(i, end=' ')
↳ 10 12 14 16 18 20 22 24

Um iterador não retorna elementos indexados, o que significa que não podemos tomar apenas uma fatia (ou slice). No entanto podemos usar a função itertools.isslice().

Função isslice(iterador, n): Retorna os primeiros n elementos do iterador.

» quadrados = (n**2 for n in it.count())
» list(it.islice(quadrados, 10))
↳ [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Outra abordagem possível é usar itertools.takewhile (ou itertools.dropwhile) para fazer filtragens:

» algunsQuadrados = (n**2 for n in it.count(25, 5))
» list(it.takewhile(lambda x: x<2000, algunsQuadrados))
↳ [625, 900, 1225, 1600]

Função repeat(objeto, n): retorna o objeto repetido n vezes, em um iterável. Se n for omitido (o que é o mesmo que passar n=None) o ciclo se repete indefinidamente.
Função cycle(objeto): é o mesmo que repeat() retornando o objeto um número indefinido de vezes.

»  função repeat
» for i in it.repeat([1,2,3], times = 3):
»     print(i, end = ' ')
↳ [1, 2, 3] [1, 2, 3] [1, 2, 3]

» função cycle
» l = ['Far', 'West', 'Wing']
» i = 0
» for t in it.cycle(l):
»     if i < 5:
»         print(t, end=' ')
»     else:
»         break
»     i += 1
↳ Far West Wing Far West 

Funções Geradoras

Como sabemos, uma função do Python é executada de forma sequencial e sem interrupções, até que uma instrução return seja encontrada. Nada depois disso é executado. (Lembrando: uma função sem return retorna None.)

» def exibeLinhas():
»     print('linha 1')
»     print('linha 2')
»     print('linha 3')

» exibeLinhas()
↳  linha 1
↳  linha 2
↳  linha 3

Instrução yield: É possível pausar uma função no meio de sua execução, retomando depois no ponto de pausa. Com isso é possível criar funções que agem como um iterador. Uma função contendo pelo menos uma instrução yield, é chamada uma função geradora. Geradores são uma generalização de iteradores que produzem seus dados apenas sob demanda, sendo por isso chamados de lazy (prequiçosos).

» def funcaoGeradora():
»     print('Linha 1 é retornada')
»     yield 1
»     print('Linha 2 é retornada')
»     yield 2
»     print('Linha 3 é retornada')
»     yield 3

» gera = funcaoGeradora()
» print(gera)
↳ <generator object funcaoGeradora at 0x7f69643c8dd0>
» print(next(gera))
↳ Linha 1 é retornada
↳ 1
» print(next(gera))
↳ Linha 2 é retornada
↳ 2
» print(next(gera))
↳ Linha 3 é retornada
↳ 3
» print(next(gera)) # um erro é lançado "StopIteration"

Esse tipo de função retorna um objeto gerador que é, em termos de comportamento, um iterador. A iteração sobre esse objeto é feita com a função interna next(). Quando o iterador está esgotado o uso de next() retorna uma exceção.

yield pode ser usado para retornar qualquer valor no iterador, inclusive None, se um valor for omitido. yield substitui a instrução return que, se usada, interrompe o ciclo do iterador. Uma função geradora pode ser transformada, com todos os seus valores, em uma lista, com list(geradora).

» def geradora():
»     for i in range(10):
»         yield i

» g = geradora()
» while True:
»     try:
»         print(next(g), end=' ')
»     except:
»         break
↳ 0 1 2 3 4 5 6 7 8 9

» g = geradora() # para repopular o iterador
» for i in g:
»     print(i, end=' ')
↳ 0 1 2 3 4 5 6 7 8 9

» g = geradora()
» lista = list(g)
» print(lista)
↳ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

A função geradora só pode ser percorrida uma vez, ficando esgotada no final. Como mostrado no último bloco de código, da mesma forma que uma função geradora pode ser percorrida com next(), o iterador por ela gerado pode ser percorrido em um loop for.

Relembrando: Uma classe pode retornar um objeto iterável por meio dos métodos especiais __iter__() e __next__(). O código next(g) é equivalente à chamar o método interno do objeto iterável, g.__next__().

» # class iteradora
» class Quadrados:
»     def __init__(self, quantos):
»         self.quantos = quantos
»         self.atual = 0​

»     def __iter__(self):
»         return self

»     def __next__(self):
»         quad = self.atual ** 2
»         self.atual += 1
»         if self.atual > self.quantos:
»             raise StopIteration
»         return quad

» q = Quadrados(11)
» for s in q:
»     print(s, end=', ')
↳ 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 

As funções geradoras podem conseguir o mesmo resultado de forma mais compacta. As operações de iteração, de obter o elemento seguinte e a parada por exceção são automaticamente fornecidas. Elas retornam um objeto gerador, que é um iterável.

» def quadrados(quantos):
»     for n in range(quantos):
»         yield n**2

» q = quadrados(11)
» for s in q:
»     print(s, end=', ')        
↳ 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100,

Uma função geradora pode guardar o estado em que terminou a última chamada até ser chamada novamente. Por exemplo, podemos contruir uma geradora para exibir os elementos da sequência de Fibonacci, indefinidamente.

» # Ex.: geradora da sequência Fibonacci
» def fibonacci():
»     a, b = 1, 1
»     while True:
»         yield a
»         a, b = b, a + b
        
» # inicializamos um objeto da sequência
» f = fibonacci()
» # as 10 primeiras iterações resultam em
» for i in range(10):
»     print(next(f), end=' ')
↳ 1 1 2 3 5 8 13 21 34 55 

» # as 10 iterações seguintes
» for i in range(10):
»     print(next(f), end=' ')
↳ 89 144 233 377 610 987 1597 2584 4181 6765 

Podemos também calcular quantos números primos se desejar, desde que o computador tenha capacidade de processamento e memória para isso.

» def numerosPrimos():
»     num = 2
»     yield num
»     while True:
»         num += 1
»         primo = True
»         for i in range(2, int(num/2)):
»             if(num % i) == 0: # achou um divisor
»                 primo = False # logo não é primo
»                 break
»         if primo:
»             yield num

» for p in numerosPrimos():
»     print(p, end=' ')
»     if p > 100:
»         break
↳ 2 3 4 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101                 

Os dois últimos exemplos ilustram o fato de que a função geradora armazena seu estado entre as chamadas e os retornos com yield. Como já vimos o loop for cuida das chamadas a next() e o encerramento do laço, quando existir.

Método send(): Outra característica importante dos geradores é a possibilidade de interagir com o código do iterador. Um valor pode ser passado para yield através do método send(). Em outras palavras, além de retornar um valor calculado dentro da função geradora yield recebe o valor passado por send(), que funciona como next() mas passa um valor para yield.

» # definimos uma função geradora com send
» def usandoSend():
»     while True:
»         recebido = yield
»         print('Recebido =', recebido)

» f = usandoSend()    # inicializamos um objeto gerador
» next(f)             # a primeira interação deve ser feita para a entrada no iterador

» # passando integer 0 para yield
» f.send(0)
↳ Recebido = 0
» # passando string para yield
» f.send('palavra')
↳ Recebido = palavra
» # uma iteração send envia None para yield
» next(f)
↳ Recebido = None

Com essa funcionalidade o código que chama o iterador pode modificar o comportamento da função e, portanto, dos valores retornados. No exemplo abaixo o gerador retorna inteiros, de 1 em 1, exceto se um incremento extra for enviado por meio de send().

» # definimos uma função geradora com send
» def usandoSend():
»     n = 0
»     while True:
»         n +=1
»         incremento = yield n
»         if recebido:
»             n += incremento

» # inicializamos o gerador
» f = usandoSend()    # inicializamos um objeto gerador
» # os 4 primeiros outputs são
» print(next(f), next(f), next(f), next(f))
↳ 1 2 3 4
» # incremento 4 primeiros outputs são
» p = f.send(10)
» print(p)
↳ 15
» # os 4 próximos outputs são
» print(next(f), next(f), next(f), next(f))
↳ 16 17 18 19

O exemplo seguinte usa send() e será usado na próxima seção para ilustrar o uso de throw().

» # definimos um gerador
» def gerador_letras(texto):
»     local = 0
»     while True:
»         mandou = yield texto[local]
»         if mandou:
»             local = mandou
»         else:
»             local += 1

» # inicializamos um gerador            
» let = gerador_letras('Apocalipse Zumbi')
» next(let)
↳ 'A'
» # enviamos via send
» let.send(11)
↳ 'Z'
» next(let)
↳ 'u'

Método throw(): throw() permite que se lance uma exceção no ponto onde o gerador foi interrompido, na última execução. Ele ativa a exceção e retorna o valor seguinte (como faria yield), ou uma StopIteration se o gerador estiver esgotado. A exceção deve ser tratada dentro da função geradora, caso contrária será repassada para o código que chamou a função. A função abaixo permite que se veja em que ponto está a execução do gerador, usando throw().

» # definindo gerador com tratamento para exceção
» def gerador_letras(texto):
»     local = 0
»     while True:
»         try:
»             mandou = yield texto[local]
»         except Exception:
»             print(f'Exceção atingida na posição {local}')
»         if mandou:
»             local = mandou
»         else:
»             local += 1

» let = gerador_letras('Sei que nada será como antes')
» print(next(let), next(let))
↳ S e

» # pula a posição para 4
» let.send(4)
↳ 'q'

» # levanta exceção (que, no caso, mostra posição atual no gerador)
» let.throw(Exception)
↳ Exceção atingida na posição 4
↳ 'q'

» print(next(let), next(let))
↳ u e

• throw(exceção): permite que se envie para o iterador qualquer tipo de exceção,
• close(): fecha o iterador e levanta a exceção GeneratorExit.

» # fechando o iterador
» f.close()
» f.send('palavra')   # uma exceção é lançada
↳ StopIteration

yield from: permite que um gerador chame outros, de forma sequencial. No exemplo abaixo o gerador_principal esgota primeiro o gerador1, depois o gerador2, em sequência.

» # geradores de geradores
» def gerador1():
»     yield 'Linha 1 do gerador 1'
»     yield 'Linha 2 do gerador 1'​

» def gerador2():
»     yield 'Linha 1 do gerador 2'
»     yield 'Linha 2 do gerador 2'

» def gerador_principal():
»     yield from gerador1()
»     yield from gerador2()

» delegando = gerador_principal()
» print(next(delegando))
» print(next(delegando))
» print(next(delegando))
» print(next(delegando))
↳ Linha 1 do gerador 1
↳ Linha 2 do gerador 1
↳ Linha 1 do gerador 2
↳ Linha 2 do gerador 2

» # o mesmo resultado seria obtido com
» delegando = gerador_principal()
» for i in delegando:
»     print(i)    # linhas de output omitidas

Observação: Alguns objetos built-in são geradores e têm internamente implementados os métodos yield, next, iter, StopIteration . São eles:
range, dict.items, zip, map e File Objects.

A conjectura de Collatz

O exemplo de função geradora a seguir ilustra um problema interessante na matemática, denominado conjectura de Collatz. Collatz se perguntou se uma operação aritmética simples repetida sobre números inteiros positivos produziria sempre uma sequência terminada em 1. A sequência geralmente considerada é a seguinte: iniciando com um inteiro n cada termo da sequência é gerado da seguinte forma. Se o número é par o seguinte é n/2; se o número é impar o seguinte é 3n + 1. Para todos os inteiros testados a conjectura é verificada. Por exemplo, começando com n=7 temos: {7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}. No entanto até hoje não foi possível provar o caso geral e o problema permanece em aberto.

Para gerar a sequência vamos construir um iterador que recebe um parâmetro n, o número inicial da sequência. Observe que a sequência seria infinita sem um corte pois 1 ⟶ 4 ⟶ 2 ⟶ 1, um loop infinito. Portanto a interrompemos manualmente quando ela atinge 1. O iterador é usado pela função collatz(n) que retorna a sequência inteira e quantas iterações foram feitas (protanto quantos elementos existem na sequência).

» # sequência de Collatz
» def iterador(numero):
»     while True:
»         yield numero
»         numero = int(numero/2 if numero%2==0 else 3 * numero + 1) 

» def collatz(n):
»     itt = iterador(n)
»     quantos = 0

»     while True:
»         quantos += 1
»         val = next(itt)
»         print(val, end=' ')
»         if val == 1:
»             print(f'\nFinal alcançado em {quantos} iterações!')
»             break

» collatz(7)
↳ 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
↳ Final alcançado em 17 iterações!

Geradores e gerenciamento de memória

Geradores são uma forma prática de interagir com grande volume de dados sem esgotar a memória do computador. Eles permitem que um grande volume de dados possam ser acessados em blocos, por partes. Cada bloco pode ser retornado sob demanda, enquanto o gerador armazena seu estado entre cada chamada.

Bibliografia

• GeeksForGeeks: Python Itertools
• Python Docs: Itertools
• Python Docs: Generators
• Real Python: Python Itertools
• Real Python: Python Generators
• Sharpcorner.com: Itertools in Python