Generator Expressions

tl;dr

Generator expressions são mais adequadas do que list comprehensions quando queremos apenas gerar sequências de elementos para iterar sobre, pois geram um elemento de cada vez, ao contrário das list comprehensions que geram uma lista inteira em memória.

Generator Expressions

Frequentemente, você pode economizar memória e processamento em seus programas fazendo:

lista = (x**2 for x in xrange(1, 1000001))

ao invés do costumeiro:

lista = [x**2 for x in xrange(1, 1000001)]

O primeiro trecho de código usa uma generator expression,  que são expressões que retornam um generator (calma aí que já já vou descrever o que é um generator). O segundo trecho de código usa uma list comprehension expression, que retorna uma lista. Para entendermos a diferença entre as duas expressões, primeiro é necessário que saibamos o que é um generator. Se você já sabe, pode pular a próxima seção.

Generators

Não são raras as situações em que precisamos criar uma sequência de elementos, para depois iterar sobre essa sequência realizando alguma operação sobre esses elementos. Por exemplo, queremos gerar uma sequência contendo os n primeiros números primos. Poderíamos criar uma funçãozinha que gera uma lista com esses valores:

def primos(n):
    lista = []
    i = 0
    while len(lista) < n:
        if eh_primo(i):
            lista.append(i)
        i = i + 1
    return lista

E quando precisarmos usar tal lista, simplesmente chamamos a função primos(). Assim, podemos iterar sobre o resultado da chamada a essa função:

for i in primos(1000):
    # faça algo com o i
    print i,

O problema é que a função primos() gera uma lista de n elementos em memória — e isso pode ser um tanto quanto caro, dependendo do valor de n. Como estamos apenas querendo iterar sobre um conjunto de elementos (ou seja, usar cada um de uma vez), poderíamos usar um generator. Para entender o que é um generator, vamos primeiro reescrever a função anterior:

def primos_gen(n):
    i = 1
    count = 0
    while count < n:
        if eh_primo(i):
            count = count + 1
            yield i
        i = i + 1

Repare na palavra-chave yield. Em Python, toda função que possui em seu corpo a instrução yield, retorna um generator quando for chamada. O yield pode ser lido como um pause, que retorna um objeto do tipo generator. Veja:

>>> x = primos_gen(100)
>>> print type(x)
<type 'generator'>

Sendo um objeto do tipo generator, x possui um método next(), que irá retornar um elemento apenas. Veja que a cada chamada ao next(), o generator x retorna o valor seguinte da sequência que está sendo gerada:

>>> x.next()
1
>>> x.next()
2
>>> x.next()
3
>>> x.next()
5
>>> x.next()
7
>>> x.next()
11

E assim sucessivamente… O que deve ser entendido sobre o comando yield é que ele é parecido com o return, pois acaba retornando um elemento para quem chamar a função next(). Porém, a execução da função generator fica “pausada” após o yield, sem perder o contexto atual, como ocorreria no caso de um return. Assim, quando chamarmos novamente o método next() do objeto, a execução irá continuar na linha seguinte ao yield, não reiniciando a execução da função desde o seu início. Ou seja, a função volta a ser executada do ponto onde estava parada. Legal, né?

Isso permite que façamos uma iteração sobre uma sequência de elementos sem ter que gerar toda essa sequência em memória antecipadamente. Assim, geramos elemento por elemento e o retornamos, e, quando quisermos outro elemento, a execução da função geradora será retomada de onde parou na execução anterior. Caso ainda não tenha entendido o yield, observe e teste o seguinte código (emprestado daqui):

def func():
    yield 1
    yield 2
    yield 3
x = func()
print x.next()
print x.next()
print x.next()

Se você testar o código, verá que quando executamos a primeira chamada à função x.next(), teremos como valor de retorno o número 1. Quando executamos a segunda chamada à x.next(), teremos como retorno o valor 2. Por fim, quando executamos a terceira chamada à x.next(), teremos como resposta o inteiro 3.

Mas, ao invés de invocar explicitamente o método next() de x, poderíamos usar um laço for (repare que não estamos chamando o next()). Veja:

def func():
    yield 1
    yield 2
    yield 3

x = func()
for i in x:
    print i,

Execute o código acima e verá que teremos a seguinte saída:

1 2 3

Parabéns, você acaba de aprender a “mágica” que o laço for usa para percorrer sequências de elementos! Na verdade, o for espera que o objeto a ser percorrido retorne para ele um iterator, para que ele possa “conversar” com tal objeto, chamando o método next() a cada iteração para obter o próximo valor.

Enfim, generators são objetos que retornam objetos e que mantém o estado da função geradora entre a geração de um objeto e outro.

Generator Expressions

Como comentei anteriormente, muitas vezes usamos list comprehensions quando na verdade elas não são a melhor alternativa. Quando usamos list comprehensions, a lista inteira é gerada de uma vez e armazenada na memória. Por exemplo, se quisermos gerar uma lista contendo os quadrados de todos os números inteiros de 1 a 1.000.000, podemos fazer o seguinte:

>>> lista = [x**2 for x in xrange(1, 1000001)]

Ao usarmos uma list comprehension, estamos gerando uma lista inteira na memória e armazenando-a em uma variável chamada lista. Tudo bem, às vezes é mesmo necessário manter essa lista na memória para usar seu conteúdo posteriormente, mas muitas vezes fazendo mau uso da ferramenta e usamos esse tipo de expressão quando não precisamos da lista inteira de uma vez só.

Vamos seguir o raciocínio utilizando um exemplo. Estudando o módulo random, desejamos verificar, em um conjunto de 1000000 (um milhão) de números aleatórios gerados através da função random.randint(), onde limitamos os números gerados à faixa de 0 a 1000000, se alguma vez o valor 0 é gerado pela função. Usando uma list comprehension e a função any(), poderíamos verificar se algum dentre os 1000000 números gerados é igual a 0. (Perceba que o resultado vai variar de execução para execução, dependendo dos números gerados.)

>>> any([random.randint(0, 1000000) == 0 for x in xrange(0, 1000000)])
True
>>> any([random.randint(0, 1000000) == 0 for x in xrange(0, 1000000)])
False

O código acima basicamente executa os seguintes passos:

  1. A cada volta do loop é gerado um número aleatório entre 0 e 1000000.
  2. Para cada número gerado, verificamos se ele é igual a 0 e armazenamos o booleano correspondente a tal verificação em uma lista (assim, temos uma lista de 1000000 de booleanos, por exemplo: [False, True, False, False, …, False]).
  3. Após gerada a lista, usamos a função any(), que verifica se algum dos valores armazenados na lista é True.

Nosso código tem um sério problema. Antes de dizer qual é, pergunto a vocês: “Precisamos realmente armazenar na memória uma lista de 1000000 de elementos para fazer a operação acima?”. A resposta é: “Nesse caso, não!”. A função any() recebe um objeto iterável como parâmetro e irá chamar o método next() do iterator retornado por esse objeto a cada iteração necessária. Poderíamos usar uma generator expression nesse caso. Esse tipo de expressão se comporta de forma semelhante a uma função do tipo generator. Ao contrário de quando iteramos sobre uma list comprehension, onde geramos uma lista inteira antes de percorrê-la, com uma generator expression, os elementos são gerados “sob demanda”. Podemos escrever o mesmo exemplo acima utilizando a sintaxe das generator expressions (muito semelhante à list comprehensions, trocando o [] por ()):

>>> any((random.randint(0, 1000000) == 0 for x in xrange(0, 1000000)))
True
>>> any((random.randint(0, 1000000) == 0 for x in xrange(0, 1000000)))
False

A função any() itera sobre o objeto gerado pela generator expression. Temos então a geração de um elemento a cada iteração. Dessa forma, estamos economizando memória, pois os elementos são gerados e, assim que não são mais necessários, podem ser descartados.

As generator expressions estão disponíveis a partir da versão 2.4 do Python.

List comprehensions são do mal?

Claro que não. Em muitos casos, list comprehensions são exatamente o que precisamos. Elas geram listas, que permitem acesso aleatório a elementos dela (ou seja, podemos acessar o n-ésimo elemento dela sem antes passar pelos n-1 elementos anteriores). Também permite que façamos uso do operador de slicing, dentre outras vantagens das listas.

Mais informações

Veja mais na PEP que propôs a criação de generator expressions. Outro material muito bom são os slides da palestra que o Luciano Ramalho fez no FISL/2012 sobre esse assunto.

Anúncios

5 comentários sobre “Generator Expressions

  1. Pingback: all() e any() « Python Help
  2. Pingback: each_cons — percorrendo sequências em N elementos por vez | Python Help
  3. Pingback: Web Scraping com Scrapy – primeiros passos | Python Help

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s