Filas e Pilhas em Python

Você pode não perceber, mas boa parte dos programas que você usa no dia-a-dia utilizam internamente os tipos abstratos de dados chamados filas e pilhas. Eles são chamados dessa forma porque representam uma estrutura de dados com operações associadas que definem um certo comportamento. Eles são muito úteis para o programador pois podem ser utilizados em diversas situações e têm um grande poderde simplificar algoritmos. A seguir, explicarei cada uma dessas estruturas e demonstrarei como poderíamos implementá-las em Python.

Filas

Tenho certeza que você já sabe como uma fila funciona. Pense na fila que você pega toda vez que vai ao supermercado. Para que você seja atendido, é preciso que todas as pessoas que estiverem na sua frente na fila sejam atendidas ou desistam para que você seja atendido, certo? Por isso, podemos dizer que a idéia da fila é que o último a entrar na fila seja o último a sair.

                                     _________
                                    | o caixa |
------------------------------------|_________|
 o    ~o    @    &     Q    0    O     0
/|\    []  {0\  /|\   /|\  /||  /-\   /0|
/ \    |\   |\  / \    |\  /|   |-|   / \
você   p6   p5  p4     p3  p2    p1   p0
-------------------------------------------

No exemplo acima, é preciso que p0, p1, p2, p3, p4, p5 e p6 sejam atendidas para que seja a sua vez de passar as compras e pagar por elas. Uma estrutura de dados Fila funciona da mesma maneira. Uma fila é uma estrutura utilizada especificamente para armazenamento temporário de dados na memória. Diferentemente de uma lista, que também serve para esse fim, uma fila possui regras quanto a qual elemento será retirado e onde será inserido um novo elemento. Em uma lista, é possível inserir elementos em qualquer posição e retirar quaisquer elementos, não importando sua posição. Em uma fila, os novos elementos que são inseridos são sempre posicionados ao final dela. Quando se faz a retirada de um elemento de uma fila, sempre iremos retirar o elemento que há mais tempo está nela (o primeiro). Imagine um servidor Webque é capaz de atender a, no máximo, 2 requisições simultâneas. O que acontece quando chega uma terceira requisição no momento em que o servidor já está ocupado atendendo a 2 requisições? A solução mais óbvia seria colocar a nova requisição em uma área de espera. Assim, quando o servidor terminar de atender uma das atuais 2 requisições, ele poderá retirar a nova requisição da área de espera e atendê-la. E se, enquanto o servidor estiver ocupado atendendo a 2 requisições, chegarem em sequência 5 novas requisições?

   ______              
  |  r0  |       [ r6  r3]
  |  r1  |       [  r5   ]
  |______|       [r4  r2 ]
    /  \  
Servidor Web    Área de espera

O servidor poderia colocar as novas requisições em uma área de espera, e sempre que houver disponibilidade, retirar uma de lá e processá-la, até que não hajam mais requisições a serem processadas. A solução é boa, mas para ser justo com as solicitações que chegam dos usuários, o servidor deve processar primeiro as que já estão esperando há mais tempo, correto? Assim, o melhor a se fazer é utilizar uma filapara armazenar as requisições que estão em espera.

        ______    
       |  r0  |           
       |  r1  |      saída  -----------------------  entrada
       |______|      <----   r2  r3  r4  r5  r6     <------
         /  \               -----------------------
     Servidor Web                 Fila de espera

Dessa forma, a requisição que está há mais tempo esperando é a primeira a sair da fila quando o servidor tiver disponibilidade.

Implementando uma fila

Uma fila nada mais é do que uma estrutura de armazenamento com políticas de ordem de entrada e saída de elementos. Assim, ela pode ser implementada usando uma lista, por exemplo. Como poderíamos fazer? Sabemos que as listas oferecem alguns métodos conhecidos para inserção/remoção de elementos:

  • .append(elemento): adiciona elemento ao final da lista;
  • .insert(índice, elemento): insere elemento após a posição índice;
  • .pop(índice): remove e retorna o elemento contido na posição índice.

Para inserir elementos, podemos usar o método append(), que insere um elemento ao final de uma lista. Para a retirada de elementos, podemos utilizar o método pop(x), que retira e retorna um elemento da posição x. Em se tratando de uma fila em que estamos inserindo elementos no final, de qual posição devemos retirar os elementos? Acertou quem pensou “da primeira”. Isso mesmo vamos remover o primeiro elemento utilizando pop(0). Veja:

>>> fila = [10, 20, 30, 40, 50]
>>> fila.append(60)  # insere um elemento no final da fila
>>> print fila
[10, 20, 30, 40, 50, 60]
>>> print fila.pop(0) # remove o primeiro elemento da lista
10
>>> print fila
[20, 30, 40, 50, 60]
>>> print fila.pop(0) # remove o primeiro elemento da lista
20
>>> print fila
[30, 40, 50, 60]
>>> print fila.pop(0) # remove o primeiro elemento da lista
30
>>> print fila
[40, 50, 60]

Você deve estar se perguntando: “e se eu fizesse o contrário, inserindo no início e removendo do final, funcionaria também como uma fila?” Sim, funcionaria. Pois, da mesma forma, teríamos a política do primeiro a entrar, primeiro a sair também conhecida como First-In, First-Out, ou simplesmente FIFO. Agora, para criar uma forma consistente de usar filas em Python, vamos criar uma classe para encapsular as operações da fila. Podemos definir uma classe Filaque internamente tenha uma lista representando o local onde serão armazenados os elementos. Essa classe deverá ter dois métodos principais:

  • insere(elemento): recebe como entrada um elemento a ser inserido na fila.
  • retira(): remove um elemento da fila e o retorna para o chamador.

Complete a implementação de fila abaixo, de acordo com o que foi explicado acima. O código completo se encontra no final deste texto, para que você possa comparar.

class Fila(object):
    def __init__(self):
        self.dados = []

    def insere(self, elemento):
        __________________________________

    def retira(self):
        __________________________________

Tendo a classe acima definida em um arquivo fila.py, poderíamos importar o módulo e usar tal classe:

>>> import fila
>>> f = fila.Fila()
>>> f.insere(10)
>>> f.insere(20)
>>> f.insere(30)
>>> print f.retira()
10
>>> print f.retira()
20

Importante: segundo a própria documentação oficial Python, uma lista não é a estrutura mais recomendada para a implementação de uma fila, porque a inserção ou remoção de elementos do início da lista é lenta, se comparada à inserção/remoção do final da lista. Assim, é sugerido que seja usado um deque (collections.deque).

Só isso?

Não, nós vimos apenas as filas “comuns”. Voltando ao exemplo da fila do supermercado, imagine que você está chegando aos caixas e ainda não decidiu qual deles vai usar. Aí você vê que o caixa de atendimento preferencial para idosos/gestantes/deficientes possui apenas 3 pessoas na fila, enquanto que os outros caixas têm filas com no mínimo 10 pessoas. Como o caixa não é exclusivo para idosos, você vai lá e entra na fila. Outras pessoas percebem a sua “sagacidade” (:P) e fazem o mesmo. Fica tudo certo até que chega um idoso para entrar na fila e todas as pessoas que estão na fila são obrigados a ceder sua vez para o idoso. E eis que chega o clube da terceira idade inteiro para ser atendido logo em seguida. O que acontece? As pessoas que estão na fila cedem sua vez para os idosos, e assim, seu atendimento vai sendo postergado cada vez mais. Enfim, esse é um exemplo de uma fila de prioridades. Elementos (as pessoas) que possuem maior prioridade, saem antes da fila. Se quiser saber mais, veja aqui.

Pilhas

Assim como as filas, aposto que você sabe exatamente como funciona uma pilha. Pense em uma pilha de papéis sobre uma mesa. Se você precisar adicionar um papel a essa pilha, você o adiciona sobre a pilha, ou seja, no topo dela, certo? E quando vai retirar um papel da pilha, você começa pelo que estiver no topo, certo? Ou seja, diferentemente da fila (FIFO), em uma pilha o último a entrar nela, é o primeiro a sair (Last-In, First-Out — LIFO). Veja abaixo uma ilustração de como funciona uma pilha. No primeiro item da ilustração (1), temos uma pilha composta por 5 elementos, que foram inseridos cronologicamente na seguinte ordem: p0, p1, p2, p3, e, por fim, p4. A segunda parte da ilustração (2) mostra o estado da pilha p após ter sido realizada a inserção de um novo elemento (p5). A terceira parte (3) mostra a pilha p após haver a retirada de um elemento. Como você pode ver, o elemento retirado foi o último a ter sido inserido (p5). Na última parte da ilustração (4), é apresentada mais uma retirada de elemento da pilha, desta vez p4. Se houvessem mais operações de retirada, teríamos a retirada, em ordem, dos elementos: p3, p2, p1 e p0.

|          |    |----p5----|    |          |    |          |
|----p4----|    |----p4----|    |----p4----|    |          |
|----p3----|    |----p3----|    |----p3----|    |----p3----|
|----p2----|    |----p2----|    |----p2----|    |----p2----|
|----p1----|    |----p1----|    |----p1----|    |----p1----|
|----p0----|    |----p0----|    |----p0----|    |----p0----|
============    ============    ============    ============
  Pilha p       p.insere(p5)     p.retira()      p.retira()
    (1)             (2)              (3)            (4)

Tranquilo, né? O que você deve lembrar sobre as pilhas é que ela usa uma política LIFO (Last-In, First-Out) para inserção/retirada de elementos.

Onde as pilhas são usadas?

Talvez a mais famosa utilização de pilhas em computação esteja no gerenciamento de chamadas de função de um programa. Uma pilha pode ser usada para manter informações sobre as funções de um programa que estejam ativas, aguardando por serem terminadas. Considere o seguinte exemplo:

def ola():
    print "olá, "
    mundo()

def mundo():
    print "mundo!"

def olamundo():
    ola()

olamundo()

A primeira função a ser chamada é a olamundo(), que por sua vez chama a função ola(), então a função olamundo() é empilhada, pois seu término depende do término da função ola(). Essa, por sua vez, chama a função mundo() e é empilhada. Ao terminar a execução da função mundo(), a função ola() é desempilhada e sua execução termina de onde havia parado (chamada à função mundo()). Como não há mais nada a ser executado nessa função, sua execução termina, e a função olamundo()é desempilhada e sua execução continua, encerrando assim o programa.

                 ola()
olamundo()  -->  olamundo()  --> olamundo() -->   Fim do programa.

Outra utilização de pilhas é a verificação do balanceamento de parênteses. Como saber se os seguintes parênteses estão balanceados, isto é, se para cada abre-parênteses, existe um fecha-parênteses correspondente?

(((((((((((((((((()()()()))))))())))()))()))()))((()))))

Uma forma bem simples de resolver esse problema é ler a sequência de parênteses, um por um e, a cada abre-parênteses que encontrarmos, vamos empilhá-lo. Quando encontrarmos um fecha-parênteses, devemos desempilhar um abre-parênteses, pois encontramos um fecha-parênteses correspondente a ele. Assim, ao final da avaliação da sequência acima, se ela estiver balanceada corretamente, não restarão elementos na pilha. Vejamos um exemplo mais simples:

(())()

                (
Pilha       (   (   (       (

Leitura     (   (   )   )   (   )   FIM

Repare agora em uma sequência desbalanceada:

(())(

                (
Pilha       (   (   (       (   (

Leitura     (   (   )   )   (   FIM

Perceba que a leitura de parênteses da entrada terminou, mas a pilha não estava mais vazia.

Implementação

Agora eu lhe pergunto: o que muda da implementação da fila para a implementação da pilha? A diferença é pouca, mas é muito importante. Assim como para as filas, para a implementação de pilhas podemos utilizar uma lista como estrutura para armazenamento dos dados. Basta agora definir como será o funcionamento:

  1. Iremos inserir e retirar elementos do início da lista?
  2. Ou iremos inserir e retirar elementos do final da lista?

Sabendo que em Python a inserção e remoção de elementos no final de uma lista é menos custoso do que fazer as mesmas operações no início dela, vamos adotar a segunda opção. Então, complete o código abaixo e teste em seu computador.

class Pilha(object):
    def __init__(self):
        self.dados = []

    def empilha(self, elemento):
        __________________________________

    def desempilha(self):
        __________________________________

p = Pilha()
p.empilha(10)
p.empilha(20)
p.empilha(30)
p.empilha(40)
print p.desempilha(),
print p.desempilha(),
print p.desempilha(),
print p.desempilha(),

O programa acima, se implementado corretamente, deverá mostrar o seguinte resultado na tela:

40 30 20 10

Para adicionar um elemento no final de uma lista, basta usar o método append(). E para remover o último elemento da lista? .pop(tamanho_da_lista-1) é o que devemos fazer. E para obter o tamanho da lista, podemos usar a função len(). Então:

def desempilha(self):
    return self.dados.pop(len(dados)-1)

Ou então, podemos usar self.dados.pop(-1). O acesso ao índice -1é a forma pythônica de se referir ao último elemento de uma sequência.

def desempilha(self):
    return self.dados.pop(-1)

Mais alguma operação?

Outra operação fundamental que deve estar disponível em uma Pilha, é um método que retorne um booleano indicando se a pilha está vazia. Um jeito bem simples seria usando a builtin len() sobre a nossa lista interna self.dados e verificando se ela retorna 0como resultado.

def vazia(self):
    return len(self.dados) == 0

Finalizando…

Tanto a fila quanto a pilha são estruturas importantes pra caramba e sua implementação deve fornecer um bom desempenho, visto que elas são amplamente usadas nos programas que compõem o nosso dia-a-dia. As implementações vistas aqui nesse post possuem fins didáticos apenas. Embora funcionem de forma adequada para serem utilizadas, elas não utilizam os recursos mais adequados para obter o melhor desempenho. Para usar na prática, existem soluções prontas e muito mais recomendadas, como por exemplo o módulo python queue, que pode ser usado tanto para implementação de Filas quanto para a implementação de Pilhas.

Códigos completos

Abaixo, seguem os códigos completos para a Fila e para a Pilha.

Fila

class Fila(object):
    def __init__(self):
        self.dados = []

    def insere(self, elemento):
        self.dados.append(elemento)

    def retira(self):
        return self.dados.pop(0)

    def vazia(self):
        return len(self.dados) == 0

Pilha

class Pilha(object):
    def __init__(self):
        self.dados = []

    def empilha(self, elemento):
        self.dados.append(elemento)

    def desempilha(self):
        if not self.vazia():
            return self.dados.pop(-1)

    def vazia(self):
        return len(self.dados) == 0
Anúncios

Tratamento de Exceções

Exceções em Python

Alguma vez, enquanto testando seus programas Python, você recebeu na tela uma mensagem de erro parecida com a seguinte?

Traceback (most recent call last):
File "<stdin>", line 1, in \<module\>
IndexError: list index out of range

Ou com essa?

Traceback (most recent call last):
File "<stdin>", line 1, in \<module\>
NameError: name 'x' is not defined

Em caso positivo, Python lhe atirou uma exceção e você nada fez com ela. Imagine que você esteja escrevendo uma calculadora bem simples usando Python como linguagem para a implementação. Tudo que ela faz são as quatro operações básicas (soma, subtração, multiplicação, divisão) e o cálculo da raiz quadrada. Ao terminar a implementação, você mostra ao seu irmão, cheio de orgulho a calculadora que acabou de implementar. O guri já vai direto ao ponto, seleciona a opção de raiz quadrada e fornece o valor:

-1

Antes de ele pressionar o enter para confirmar a operação, você já percebeu que esqueceu de tratar a entrada do usuário em operações de raiz quadrada. Você já dever saber que raiz quadrada de número negativo só é possível se utilizarmos números complexos, não? E como tal, já imagina que a função sqrt() do módulo math que você usou vai ter problemas para lidar com isso. Quando seu irmão confirma a operação, lá vem a mensagem:

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: math domain error

ValueError. Guarde esse nome para daqui a pouco…

Prontamente, você abre o seu editor de texto e corrige o código, verificando se número do qual será calculada a raiz quadrada é menor que zero.

if op1 < 0:
    print 'Atenção! Não é possível calcular a raiz quadrada de um número negativo!'

OK, tudo certo. Seu programa voltou a funcionar e o chato do seu irmão pode parar de te incomodar.

Mas e o tal do ValueError que pedi para você lembrar? Então, ele é uma exceção que Python usa para lhe indicar que algo anormal aconteceu durante a execução do seu código. E ela não serve apenas como uma simples mensagem de erro. Muito pelo contrário, o objetivo é que o programador, sabendo que determinado trecho de código pode disparar uma exceção dessas, utilize uma estrutura específica para tratamento de exceções (try-except, para os íntimos).

try-except

A estrutura básica do bloco try-except é:

try:
    # código a ser executado "sob vigilância"
except Exception:
    # caso ocorrer alguma exceção no código acima,
    # trate-a aqui.

O código localizado entre o try: e o except é executado de forma que se algo de errado acontecer ali, o except Exception vai imediatamente chamar o código localizado abaixo de si para realizar o tratamento da exceção. Ou seja, se algo de errado acontecer na linha 2, as linhas 4-5 serão executadas para tratar esse erro.

Resolvendo o problema

Sabendo um pouco como as exceções funcionam, e sabendo que a tentativa de calcular a raiz quadrada de um número negativo gera um ValueError, você irá envolver o trecho de código que poderá gerar tal exceção em um bloco try-except. Veja:

try:
    result = math.sqrt(op1)
except Exception:
    print 'Atenção! Não é possível calcular a raiz quadrada de um número negativo!'

Ao executar o código acima e passar um valor negativo para o segundo operando da divisão, você vê que funcionou. Agora, ao invés da mensagem feia na tela, você recebe sua mensagem de erro personalizada (mais tarde veremos que o mecanismo de exceção não serve só para mandarmos mensagens de erro para o usuário, mas também (e principalmente) para tratar as exceções.).

E aí, a mala do seu irmão vem testar o programa novamente. Desta vez, ele fornece o próprio nome como entrada para a raiz quadrada. Você já imagina que lá vem outro erro, afinal Python não é mágico para calcular a raiz quadrada de "Joaozinho". 😛 Para sua surpresa, eis que aparece na tela a mensagem:

Atenção! Não é possível calcular a raiz quadrada de um número negativo!

Aí você e seu irmão não entendem mais nada, afinal ninguém passou um número negativo como entrada. Na realidade, o que aconteceu é que o bloco:

except Exception:
    print 'Atenção! Não é possível calcular a raiz quadrada de um número negativo!'

significa mais ou menos o seguinte: se ocorrer uma exceção qualquer, nas linhas entre o try e a linha except Exception:, trate-a com o bloco de código que vem após o : (que é o nosso print).

Perceba, except Exception: irá agarrar QUALQUER exceção que Python atirar, pois Exception é a classe-base da qual todas as outras exceções são descendentes. Se você quiser que a mensagem 'Atenção! Não é possível calcular a raiz quadrada de um número negativo!' seja mostrada ao usuário apenas quando for passado um valor negativo à raiz quadrada, então teremos que especializar o nosso tratamento de exceções, isto é, especificar qual é a exceção que queremos tratar realmente. Como vimos anteriormente, a exceção que Python atira quando ocorre uma tentativa de cálculo de raiz quadrada de um valor negativo se chama ValueError. Então, fazemos:

except ValueError:
    print 'Atenção! Não é possível calcular a raiz quadrada de um número negativo!'

Opa, agora sim, a mensagem só vai aparecer quando houver o erro supracitado. É claro que Python não fornece uma exceção para cada um de todos os possíveis tipos de erros, mas ele já vem de fábrica com um bocado. Às vezes, pode ser preciso que você implemente sua própria exceção, como por exemplo, se o seu programa recebesse do usuário o valor do CPF. Você poderia criar uma exceção CPFInvalidError, ou seja qual for o nome que quisesse dar. Mas, criação de exceções customizadas é assunto para outro post.

Tratando as Exceções

Talvez você esteja pensando: “mas jogar uma mensagem de erro na tela não é bem o que eu entendia por tratamento de exceção”. E você está certo, podemos fazer muito mais do que isso. No exemplo anterior, podemos corrigir o erro do usuário, transformando o número negativo em um número positivo. O código a ser executado ao tratarmos uma exceção é código Python como qualquer outro, então você pode fazer o que for preciso para corrigir o problema.

try:
    result = math.sqrt(op1)
except ValueError:
    print 'Atenção! Tranformando entrada negativa em número positivo.'
    op1 = -op1
    result = math.sqrt(op1)

Nota: Esse exemplo é meramente didático, para você entender como funcionam as exceções e como elas podem ter vários usos, mas ele não é um bom exemplo do uso de exceções. Leia a seção das boas práticas e entenda por quê.

Assim, além de avisar ao usuário sobre o erro, já estamos fazendo a correção, de forma que o programa possa seguir seu fluxo normal de execução.

Por fim, talvez você esteja se perguntando como vai adivinhar o nome da exceção para colocar no except. Uma das formas de descobrir quais exceções determinadas funções/operações disparam quando acontece uma situação imprevista, é lendo a documentação da função/operação que você estiver utilizando. Outra modo de descobrir é encarando a mensagem de erro quando acontece uma exceção não tratada. Por exemplo:

>>> math.sqrt("hello")
Traceback (most recent call last):
File "", line 1, in
TypeError: a float is required

Ao executar o comando math.sqrt("hello"), acabamos de descobrir que ele atira uma exceção do tipo TypeError quando recebe uma entrada de um tipo diferente do numérico.

Boas práticas no tratamento de exceções

Agora que você (e o seu irmão) já estão manjando como funcionam exceções e o que dá pra fazer com elas, está na hora de conhecerem algumas boas práticas, alguns conselhos que geralmente é uma boa idéia seguir, na labuta diária com exceções.

  1. Não use exceções para o fluxo principal da aplicação. Ou, dizendo de outro modo, use exceções apenas para o que é realmente excepcional, inesperado. A idéia é que, enquanto seu programa esteja executando o caminho feliz, isto é, enquanto está tudo dentro do esperado — o céu está azul, os planetas estão girando em torno do Sol e a Lua em torno da Terra — ele não precise voltar atrás na sua execução devido a uma exceção ter sido lançada. Isso é uma boa idéia por que o seu código ficará mais direto ao ponto e você ainda evita o eventual custo adicional que programar “orientado a exceções” acarreta (por exemplo, por tentar fazer uma coisa, voltar e tentar de novo). No exemplo utilizado nesse post, poderíamos simplesmente evitar que a exceção ocorra fazendo uma simples verificação sobre o valor, com um if.
  2. Interceptar exceções somente quando você sabe como tratá-la. Ou seja, não adianta de muita coisa encher o seu código de try-except se tudo o que o seu tratamento de exceção faz é imprimir uma mensagem de erro na tela. Trate exceções específicas, e quando você souber como lidar com ela. Senão você pode acabar obscurecendo uma exceção importante (como KeyboardInterrupt ou SystemExit, por exemplo) que era melhor lançá-la mesmo.
  3. Conhecer as exceções da biblioteca-padrão. Tire um tempo para dar uma olhada com cuidado nos tipos de exceções que Python já traz de fábrica, pois além de conhecer algumas exceções que você pode usar no seu programa, você passa a conhecer os principais tipos de situações inesperadas que o seu programa está sujeito.

Programe defensivamente com asserções

O trânsito é um dos ambientes em que o ser humano reconhece que precisa de ajuda pra que funcione direito pra todo mundo. Digo aqui “reconhece” querendo dizer na verdade o contrário: todo mundo acha que é o único bom motorista no mundo, que os outros é que estão querendo ferrá-lo furando sinal fechado, correndo que nem loucos e mudando de pista sem sinalizar, bando egoístas e mal-educados… Enfim, por causa disso a gente aprende a dirigir defensivamente, isto é, se prevenir dos problemas antes que eles aconteçam, evitando situações que coloquem em risco você ou os demais. 1

Em programação não é diferente. Programadores são humanos, cometem muitos erros, e em geral têm dificuldade em reconhecer que seu código não está legal, colocam a culpa no código dos outros, na linguagem, na biblioteca utilizada, no compilador e até no sistema operacional — não obstante o fato de existirem muitos outros programas usando as mesmas coisas e sem apresentar o problema do programa deles.

Assim como a direção defensiva envolve não só seguir as regras de trânsito mas também se preparar para condições adversas, na programação defensiva nosso código precisa mais do que compilar na nossa máquina e funcionar com os testes “caminho feliz” que a gente faz usualmente.

Uma boa prática de programação defensiva é verificar pré-condições do seu código, isto é, coisas que o código precisa que sejam verdadeiras para poder funcionar corretamente. Por exemplo, você pode querer verificar para um certo método se um argumento é não-nulo, ou se não é vazio para o caso de uma lista, ou se representa um objeto de determinado tipo. Em Python, você pode fazer isso criando uma asserção, usando o comando assert:

def buscaPorCpf(cpf):
    assert cpf != None, "argumento cpf nao pode ser None"
    print 'cpf:', cpf

A asserção é uma afirmação sobre o que deve ser verdadeiro em dado momento da execução do seu código. Na prática, ela funciona parecido com uma validação para se defender de erros de um usuário: a diferença é que a asserção é pra se defender de erros do programador, incluindo você mesmo. Quando a condição de uma asserção é verificada sendo falsa, o interpretador Python lança uma AssertionError, opcionalmente com a mensagem que especifique o erro.

É sempre bom usar mensagens que explicitem o tipo de erro, principalmente quando a condição é mais específica, para facilitar a detecção dos problemas, além de facilitar a leitura do código. Por exemplo, você pode querer também verificar se o argumento cpf é do tipo string:

def buscaPorCpf(cpf):
    assert cpf != None, "argumento cpf nao pode ser None"
    assert isinstance(cpf, basestring), "argumento cpf precisa ser uma string"
    print 'cpf:', cpf

Nota: A checagem aqui é feita de tal forma que aceita tanto instâncias de str (ex.: '000.000.000-00') e de unicode (ex.: u'000.000.000-00'), que são subclasses de basestring

Repare que a asserção aqui está se defendendo de coisas básicas, pré-condições que se forem falsas, são obviamente um erro na programação. Nesse exemplo que estamos lidando com um CPF, é importante notar a diferença para uma validação de dados digitados pelo usuário, por exemplo, se ele digita um CPF inválido (que também é uma forma de programação defensiva). Para a validação, o seu programa deve tratar o erro (por exemplo, lançando uma exceção pré-definida ou simplesmente retornando None) de forma consistente com o restante do seu código. Asserções são para se defender de erros de programação e documentar pré-condições ou pós-condições do código, e não para implementar lógica de tratamento de erros.

Outra coisa a ser tomada nota, que pode ser vista como desvantagem de usar asserções para checar pré-condições, é que elas não são propagadas para subclasses do seu código, por exemplo. É muito fácil alguém criar uma classe que estende a sua, e avacalhar a linda defesa que você colocou no __init__. Se você acha interessante esse tipo de recurso, você talvez queira usar ferramentas que implementem programação por contrato, como a pydbc ou a pycontract. 2

Finalizando, se o seu código tiver muitas asserções e você acha que elas podem estar fazendo processamento desnecessário, você pode rodar o interpretador Python com a opção -O que habilita otimizações básicas como pular execução dos comandos assert. Mas… não faça isso! Existe uma lei da natureza que diz que alguns problemas só acontecem quando o cliente usa seu programa, então você provavelmente quer as asserções ajudando lá também. 🙂 3

Notas:

1 Li a metáfora do trânsito a primeira vez no livro O Programador Pragmático, altamente recomendado por sinal!
2 pycontract é a implementação de referência da PEP-0316, uma proposta de embutir tratamento de programação por contrato na linguagem, colocando as pré-condições e pós-condições nas strings de documentação dos métodos. A PEP é antiga e ainda não foi aceita, mas a implementação parece ser estável, e é facilmente instalável no Ubuntu com apt-get install python-contract.
3 Citação quase-literal roubada descaradamente do texto em inglês: Usando Asserções de Forma Efetiva.

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.