Árvore Binária de Busca em Python

Onde quer que você esteja lendo este texto, é bem provável que existam algumas árvores instanciadas na memória do seu computador. Árvores são estruturas de dados muito versáteis que são utilizadas na solução de uma enorme gama de problemas, como na otimização de consultas e na indexação de bancos de dados, na geração de códigos para compressão de dados, na análise sintática de código por compiladores, na representação da estrutura de diretórios em um sistema de arquivos, etc. O conceito será explorado neste post, onde veremos a implementação de uma das variações dessa estrutura, a Árvore Binária de Busca.

As Árvores

As árvores são estruturas de dados hierárquicas nas quais os dados são armazenados por nós, sendo o primeiro destes chamado de nó raiz. Cada nó de uma árvore possui um nó pai (exceto o nó raiz) e possui nós filhos (exceto os nós folha). Veja na figura abaixo um exemplo de árvore que guarda números inteiros em seus nós.

image06

Na figura acima, o nó raiz é o 8, e ele tem como filhos os nós de chave 4, 2, 9 e 1. O nó 4 é pai dos nós 6 e 7. Estes dois, assim como os nós de chave 5, 2 e 1, são chamados de folhas por não terem filhos (ou seja, seus filhos são nulos).

Uma árvore pode ser composta por uma ou mais subárvores. A figura abaixo destaca as subárvores que compõem uma outra árvore.

image08

Árvores Binárias

Uma árvores binária é um tipo especial de árvore, em que cada nó pode ter no máximo 2 filhos, um à esquerda e um à direita do nó.

image10

A árvore da figura acima é, de fato, uma árvore binária, pois nenhum nó possui mais do que dois filhos. Observe que um dos nós possui somente um filho e outros nós nem sequer possuem filhos, o que também está de acordo com as propriedades de uma árvore binária.

Árvores Binárias de Busca

As Árvores Binárias de Busca são árvores binárias com a seguinte propriedade: todos os nós pertencentes à subárvore esquerda de qualquer nó possuem chave menor que a chave do mesmo, e em que os nós da subárvore à sua direita possuem chave maior que a chave do nó em questão. Essa propriedade deve ser válida para todas as subárvores, possibilitando a realização de buscas mais eficientes, pois podemos comparar a chave procurada com a chave de um nó e decidir se devemos continuar a busca somente na subárvore à esquerda ou à direita do nó, reduzindo assim a quantidade de nós a serem visitados na busca.

Vamos agora observar a árvore da figura abaixo e verificar se a propriedade acima é realmente válida para todos os nós dela.

image14

Todos os elementos contidos na subárvore à esquerda do nó 8 (nós 2, 4, e 7) possuem chaves menores que ele e todos os elementos da subárvore à direita dele (nó 9) são maiores. A subárvore iniciada pelo nó de chave 4 também respeita tais propriedades pois os elementos à esquerda dele são menores (no caso o nó de chave 2) e os que estão à direita são maiores (o nó 7). Desse modo, podemos afirmar que a árvore da figura acima é uma árvore binária de busca.

Implementação de uma Árvore Binária de Busca

Uma árvore nada mais é do que um conjunto de nós, e cada nó é um objeto com uma chave, um valor e uma referência aos seus dois filhos (esquerdo e direito). A chave serve para identificar o nó e o valor armazena os dados que o nó representa. Por exemplo, em um sistema de arquivos que utiliza uma árvore para representação da hierarquia de diretórios, a chave do nó poderia ser o nome do arquivo e o valor poderia ser uma referência ao conteúdo do arquivo em si.

Em Python, podemos definir um (BSTNode – de Binary Search Tree Node) de árvore da seguinte forma:

class BSTNode(object):
    def __init__(self, key, value=None, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

Os campos left e right são as referências a outros nós, o campo key guarda a chave utilizada para identificar o nó e value representa o valor que desejamos armazenar nele.

A construção de um , com chave 42, sem valor armazenado e sem filhos pode ser feita da seguinte forma:

root = BSTNode(42)

Esse código cria a seguinte árvore:

image15

Se quisermos adicionar filhos ao nó 42, podemos fazer:

root.left = BSTNode(10)
root.right = BSTNode(90)

O que faz com que a árvore fique:

image05

Se quisermos adicionar um filho esquerdo ao nó de valor 10, recém criado, podemos fazer:

root.left.left = BSTNode(2)

O encadeamento feito acima gera a seguinte árvore:

image07

Embora funcione, nossa implementação de árvore não possui uma boa interface de programação, pois é necessário fazer os encadeamentos entre nós de forma manual.

Operações em uma Árvore Binária de Busca

Para que seja útil, a interface de programação de nossa árvore binária de busca deve fornecer algumas operações básicas, como: busca por chave, inserção de um elemento na árvore, remoção de um elemento e travessia.

A seguir veremos a implementação dessas operações, definindo uma interface melhor para nossa classe.

Busca em uma Árvore Binária de Busca

As Árvores Binárias de Busca são assim chamadas porque suas estruturas permitem a realização de buscas de forma eficiente. Vamos entender o porquê disso observando a árvore da figura abaixo:

image03

Se estivermos procurando pelo nó de chave 10, tudo o que precisamos é de duas comparações: uma, na qual verificamos que a chave procurada é maior que a chave do nó raiz, o que nos indica que devemos continuar a busca na subárvore à direita, e outra, na qual encontramos o elemento no próximo nó.

Agora vamos simular a busca pelo nó de chave 4: começamos comparando o 4 com a chave da raiz. Como 4 é menor que a chave da raiz, devemos focar nossa busca na subárvore à esquerda (cuja raiz é o nó de chave 3). Como 4 é maior que a chave da raiz dessa subárvore, devemos nos direcionar para a subárvore à direita do nó de valor 3. A chave que estamos procurando (4) é menor que a chave contido na raiz dessa subárvore (6). Assim sendo, devemos seguir buscando pelo nosso elemento na subárvore à esquerda, cuja raiz possui chave 4. A animação abaixo demonstra as comparações realizadas nessa busca.

image04

Implementação da busca

O código abaixo implementa o algoritmo de busca descrito acima para a classe BSTNode, através do método get:

class BSTNode(object):
    def __init__(self, key, value=None, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

    def get(self, key):
        if key < self.key:
            return self.left.get(key) if self.left else None
        elif key > self.key:
            return self.right.get(key) if self.right else None
        else:
            return self

Observe que este é um método recursivo, o que é condizente com a estrutura da árvore, que também é uma estrutura recursiva, com um nó sendo definido com base nele próprio. A função tem como condição de parada o nó ser nulo (None). Quando isso acontece, significa que chegamos ao fim de um galho da árvore sem ter encontrado a chave, isto é, a chave não existe na árvore.

Para realizar uma busca pela chave 4, devemos fazer o seguinte (onde tree é uma referência ao nó raiz da árvore):

tree = BSTNode(8)
...
found = tree.get(4)
if found:
    print(found)

O método get apresentado acima poderia ser refatorado, evitando a duplicação de código:

def get(self, key):
    """Retorna uma referência ao nó de chave key
    """
    if self.key == key:
        return self
    node = self.left if key < self.key else self.right
    if node is not None:
        return node.get(key)

Inserção em uma Árvore Binária de Busca

Uma inserção em uma árvore binária de busca deve respeitar a propriedade fundamental dessa estrutura, mantendo menores à esquerda e maiores à direita. Para que isso seja possível, é interessante que a interface de programação da nossa árvore ofereça um método que faça a inserção de um elemento garantindo tal propriedade.

O algoritmo para a inserção funciona de forma semelhante à busca. Vamos descendo na árvore com o objetivo de encontrar o local certo onde o elemento deve ser inserido, verificando sempre se devemos continuar o percurso na subárvore à esquerda ou à direita do nó. Diferentemente da busca, na inserção nossa travessia termina ao encontrarmos um nó folha, no qual o elemento a ser inserido é adicionado como filho — à esquerda, se o elemento a ser adicionado for menor que o nó, ou à direita, caso contrário.

A animação abaixo ilustra o processo de inserção de um elemento:

image11

Implementação da inserção

Assim como a busca, o método para inserção também pode ser implementado de forma recursiva. Veja o código abaixo:

class BSTNode(object):
    def __init__(self, key, value=None, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

    def add(self, node):
        if node.value < self.value:
            if self.left is None:
                self.left = node
            else:
                self.left.add(node)
        else:
            if self.right is None:
                self.right = node
            else:
                self.right.add(node)

Como podemos ver no método add, a inserção percorre a árvore até encontrar uma folha onde o novo nó pode ser inserido. Isso ocorre quando, no percurso da árvore, encontramos um nó que não possui um filho do lado esquerdo (quando o valor que estivermos inserindo for menor que o nó) ou do lado direito (quando o valor do nó que estivermos inserindo for maior que o valor do nó).

Novamente, para eliminar um pouco a repetição de código, o método add poderia ser refatorado para:

def add(self, key):
    """Adiciona elemento à subárvore
    """
    side = 'left' if key < self.key else 'right'
    node = getattr(self, side)
    if node is None:
        setattr(self, side, BSTNode(key))
    else:
        node.add(key)

Porém, nosso algoritmo de inserção um problema: ele pode deixar desbalanceada a árvore após algumas inserções.

Balanceamento de árvore

Manter uma árvore bem organizadinha é um pouquinho mais complicado, pois é necessário que mantenhamos o balanceamento da árvore. Para entendermos melhor esse conceito, vamos ver um exemplo que ilustra o pior caso em uma árvore binária de busca não balanceada, que ocorre quando os elementos são inseridos de forma ordenada:

tree = BSTNode(0)
for i in range(1, 10):
    tree.add(i)

Veja a árvore resultante dessas inserções:

image09

Esse layout é péssimo para a realização de uma busca, pois ela acaba se tornando linear, como se estivéssemos fazendo uma busca sequencial em uma lista encadeada.

Para evitar situações como esta, existem algoritmos que são usados durante a inserção de um elemento e que promovem uma reorganização dos nós da árvore para que seu layout fique mais balanceado. Para compreender melhor o conceito de balancemento de uma árvore, precisamos compreender antes o conceito de altura de uma árvore, que é definido pela quantidade de arestas no caminho mais longo entre a raiz e as folhas. A figura abaixo ilustra uma árvore de altura 3, que é a quantidade de arestas entre a raiz e a folha mais distante dela (de valor 4).

image01

Uma árvore balanceada é uma árvore na qual a altura de uma subárvore não pode ser muito maior do que a altura da sua irmã.

Para manter uma árvore balanceada, após cada inserção, devemos verificar se a árvore permanece balanceada e, em caso negativo, ela deve ser reorganizada, trocando os encadeamentos entre os nós. Isso pode ser um pouco custoso, mas compensa no momento de fazer a busca por algum elemento. Os tipos mais conhecidos de árvores binárias balanceadas são: as Árvores AVL e as Árvores Rubro-Negras. Mas esse assunto fica para um post futuro.

Remoção de um elemento

A remoção de um elemento é um pouco mais complicada do que a inserção e busca de um elemento. Existem 3 situações diferentes e que requerem diferentes abordagens para a remoção de um elemento:

  1. o nó a ser removido é um nó folha
  2. o nó a ser removido possui somente um filho
  3. o nó a ser removido possui dois filhos

Considere a árvore da imagem abaixo:

image03

Vamos analisar cada um dos casos acima.

Remoção de um nó folha

Imagine que desejamos remover o nó 4 da árvore acima. Para isso, basta fazer com que o campo left do nó 6 passe a apontar para None, e o coletor de lixo elimina o nó da memória pra gente em algum momento.

Remoção de um nó que possui um filho

Agora, desejamos remover o nó 10. Para isso, temos que fazer com que o nó pai do nó 10 (8) passe a apontar para o único filho de 10 (14).

Remoção de um nó que possui dois filhos

Este é o caso mais complicadinho. Imagine que queremos remover o nó 3, que possui como filhos a subárvore que tem como raiz o nó 1 e a subárvore do nó 6. Para remover o nó 3, é preciso que algum dos outros nós assuma o papel de raiz da subárvore. O melhor candidato para assumir esse posto é o nó cuja chave é mais próxima da chave do nó a ser removido.

Uma forma prática de encontramos tal valor é procurar o menor valor contido na subárvore à direita do nó a ser removido, isto é, o nó mais à esquerda da subárvore à direita. Na árvore do exemplo, esse nó é o nó de chave 4.

Implementação

O código abaixo implementa a remoção de um elemento. O método remove primeiramente encontra o nó a ser removido — é isso que as chamadas recursivas fazem — para depois fazer a remoção do elemento no código dentro do else. O método _min retorna o nó que contém o menor elemento em uma subárvore, isto é, o elemento mais à esquerda na subárvore em questão. Já o método _remove_min retira da subárvore o menor elemento, sendo usado para remover de sua posição o elemento que será utilizado como substituto ao elemento a ser removido, no caso deste possuir dois filhos.

class BSTNode(object):

    def __init__(self, key, value=None, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

    def remove(self, key):
        if key < self.key:
            self.left = self.left.remove(key)
        elif key > self.key:
            self.right = self.right.remove(key)
        else:
            # encontramos o elemento, então vamos removê-lo!
            if self.right is None:
                return self.left
            if self.left is None:
                return self.right
            #ao invés de remover o nó, copiamos os valores do nó substituto
            tmp = self.right._min()
            self.key, self.value = tmp.key, tmp.value
            self.right._remove_min()
        return self

    def _min(self):
        """Retorna o menor elemento da subárvore que tem self como raiz.
        """
        if self.left is None:
            return self
        else:
            return self.left._min()

    def _remove_min(self):
        """Remove o menor elemento da subárvore que tem self como raiz.
        """
        if self.left is None:  # encontrou o min, daí pode rearranjar
            return self.right
        self.left = self.left._removeMin()
        return self

Os dois primeiros ifs dentro do else (linhas 16 e 18) tratam o caso em que o nó a ser removido não possui filhos ou possui somente um filho. Observe que se o nó não possuir filho à direita, o filho à esquerda é retornado ao chamador, que é o próprio método remove na linha 11 ou 13.

Da linha 21 em diante tratamos o caso em que o nó a ser removido possui os dois filhos. A linha 21 obtém o elemento que irá substituir o elemento a ser removido. A linha seguinte copia os valores do nó substituto para o nó a ser “removido” (repare que acabamos não removendo o nó, mas sim copiando os valores do nó substituto para o seu lugar). Depois disso, removemos o elemento substituto de sua posição original, chamando o método _remove_min.

Caso queira entender melhor o algoritmo para remoção de um elemento, leia mais na seção sobre Árvores Binárias de Busca do material disponível na web para o livro Algorithms, 4th Edition.

Travessia em uma Árvore Binária

A última operação que vamos ver neste post é a travessia, que é útil em diversas situações, como para fazer a impressão da árvore, a geração de uma representação gráfica da mesma, ou então a aplicação de determinada transformação sobre todos os nós.

As três principais estratégias de travessia de uma árvore são:

  • pré-ordem
  • ordem simétrica
  • pós-ordem

A seguir, temos um método que implementa as três possíveis estratégias para visitar todos os nós da árvore.

def traverse(self, visit, order='pre'):
    """Percorre a árvore na ordem fornecida como parâmetro (pre, pos ou in)
       visitando os nós com a função visit() recebida como parâmetro.
    """
    if order == 'pre':
        visit(self)
    if self.left is not None:
        self.left.traverse(visit, order)
    if order == 'in':
        visit(self)
    if self.right is not None:
        self.right.traverse(visit, order)
    if order == 'post':
        visit(self)

Perceba que o parâmetro visit representa uma função que será aplicada a cada elemento da árvore. Se quiséssemos imprimir a árvore em ordem simétrica, bastaria fazermos:

tree.traverse(print, 'in')

As figuras abaixo — copiadas e adaptadas da Wikimedia (ei, a licença permite!) — ilustram os três tipos de travessia acima implementados:

image12

Essas três estratégias seguem a abordagem de travessia em profundidade, avançando sempre até o final de um galho da árvore e voltando para percorrer os outros galhos. Além dessa abordagem, existe também a travessia em largura, na qual os nós são percorridos nível por nível. A figura abaixo — thanks again, Wikimedia! — ilustra a travessia em largura.

image00

Alternativas de Implementação

A estrutura de dados Árvore Binária de Busca pode também ser representada através de um simples array. A árvore do lado esquerdo da figura abaixo poderia ser representada pelo array ilustrado no lado direito da mesma figura.

image02

Observe que a raiz é representada na posição 0 do array. Para acessar o filho à esquerda de qualquer elemento, basta acessar a posição 2*i+1 do array, sendo i a posição do elemento em questão. Para acessar o filho à direita de um elemento, basta acessar a posição 2*i+2. Já o nó pai de um elemento i é encontrado na posição calculada através da divisão inteira (i-1)/2. Na figura acima, representamos os filhos à esquerda com uma seta verde e os filhos à direita com uma seta azul.

A desvantagem dessa abordagem está no espaço necessário para representar árvores binárias incompletas, como a árvore da figura abaixo, em que é necessário representar os nós não existentes também. No exemplo abaixo, uma árvore de 5 elementos precisou de um array de tamanho 7 para representá-la.

image13

Mais sobre árvores

Isso não é tudo sobre árvores binárias de busca. Você pode estudar mais sobre essas estruturas lendo o artigo da Wikipedia sobre o assunto, interagindo com a visualização do visualgo.net, ou lendo algum dos livros clássicos de algoritmos e estruturas de dados. Além disso, você pode se interessar por outros tipos de árvores, como as listadas no artigo da wikipedia.

Conhecer e saber implementar uma árvore poderá facilitar a solução de diversos problemas que sem elas seriam bem mais complicados de resolver.

O código completo deste post pode ser visualizado aqui: https://gist.github.com/stummjr/cd9974b513419f0554c5

Obrigado ao Elias pela refatoração!

Anúncios

Manipulando strings como se fossem arquivos – StringIO

Há tempos atrás eu precisei extrair dados de pagamentos de arquivos pdf, mas a API que eu estava utilizando para extrair os dados do pdf trabalhava exclusivamente com arquivos. Isto é, a função que convertia o pdf em texto precisava receber um arquivo como argumento, para nele escrever o texto extraído do pdf. Entretanto, criar um arquivo (mesmo que temporário), escrever nele, e por fim, ler os dados que me interessavam a partir dele, não era algo muito conveniente, afinal, tudo que eu precisava eram os dados dos pagamentos para efetivar alguns registros no banco de dados. Foi aí que conheci o StringIO.

StringIO é uma classe Python que representa strings em estruturas que se comportam como se fossem arquivos (com a mesma interface dos objetos file), mas que ficam residentes em memória, como strings comuns. Isso pode ser útil quando lidamos com APIs cuja interface exige objetos file.

Para ter uma ideia melhor do que é a StringIO, veja o exemplo abaixo:

Importante: em Python 3.x, a classe StringIO foi movida para o módulo io (dica do alansteixeira). Para usá-la, faça: from io import StringIO

>>> from StringIO import StringIO
>>> fp = StringIO("uma string qualquer")
>>> fp.readline()
'uma string qualquer'
>>> fp.readline()
''

Também podemos criar um objeto StringIO, passar para alguma função escrever algo nele, e então obter os valores escritos chamando o método getvalue().

>>> fp = StringIO()
>>> def func(f):
>>>     f.write("hello")
>>> func(fp)
>>> fp.getvalue()
'hello'

Quando criamos uma API, às vezes é necessário fornecer uma mesma funcionalidade através de duas funções que diferem nos tipos dos parâmetros esperados: uma recebendo um arquivo e outra recebendo uma string. Isso acontece em algumas APIs conhecidas, como a de manipulação de JSON, que fornece as funções load()/dump() e loads()/dumps(), onde as primeiras recebem um arquivo como parâmetro e as últimas recebem uma string. O que uma classe como a StringIO nos permite fazer é implementar a lógica da função somente na função que recebe o arquivo. Dessa forma, a função que recebe uma string pode empacotá-la em um objeto StringIO e então chamar a função que recebe um arquivo, passando o objeto em questão para ela.

Uma outra coisa interessante que podemos fazer com a StringIO é interceptar a saída do programa que iria para a stdout (descobri isso aqui: http://effbot.org/librarybook/stringio.htm). Para fazer isso, temos que substituir a saída padrão (acessível via sys.stdout) por um objeto StringIO. Assim, tudo que for impresso via print será gravado em um objeto StringIO e não na saída-padrão. Veja:

# -*- encoding:utf-8 -*-
import sys
from StringIO import StringIO

backup_stdout = sys.stdout
sys.stdout = StringIO()

# será escrito em um StringIO
print "hello world"

# pega uma referência ao objeto StringIO antes de restaurar a stdout
fp = sys.stdout
sys.stdout = backup_stdout
print "stdout: " + fp.getvalue()

E, assim como fizemos com a stdout, poderíamos ter feito com a stderr (saída-padrão de erros), para interceptar as mensagens de erro e, quem sabe, analisá-las.

Enfim, sempre que se deparar com uma API que exige arquivos como parâmetros, lembre-se da StringIO caso não esteja a fim de acessar o disco e de lidar com arquivos.

Conjuntos em Python

Hoje percebi que o blog já tratou sobre listas, dicionários, tuplas; mas até agora não escrevi texto algum sobre os conjuntos (também conhecidos por sets).

Sets: o que são?

Sets (ou, como iremos chamar daqui para a frente, conjuntos) são estruturas disponíveis como builtins do Python, utilizadas para representar coleções desordenadas de elementos únicos. É importante sempre lembrar dos conjuntos por suas duas principais características:

  1. Os elementos não são armazenados em uma ordem específica e confiável;
  2. Conjuntos não contém elementos repetidos.

A característica número 1 é importante, porque o desenvolvedor jamais deve confiar na ordenação de um conjunto, visto que a ordem em que os elementos são mantidos nos conjuntos varia de implementação para implementação do interpretador Python. Não é a toa que conjuntos não suportam indexação nem fatiamento (slicing). Bom, chega de papo e vamos ver alguns exemplos de conjuntos.

Mãos na massa

Vamos começar definindo um conjunto, usando a sintaxe para literais de conjuntos (introduzida há pouco tempo nas versões 3.1 e 2.7):

>>> s = {1, 2, 3, 4}
>>> print s
set([1, 2, 3, 4])

Existem várias operações disponíveis nos conjuntos através de métodos, como as operações mais conhecidas de teoria dos conjuntos, como união, interseção e diferença.

União

Imagem da Wikipedia

A U B (Crédito da imagem: Wikipedia)

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> print a.union(b)
set([1, 2, 3, 4, 5, 6])

Interseção

Imagem da Wikipedia

A ∩ B (Crédito da imagem: Wikipedia)

>>> print a.intersection(b)
set([3, 4])

Essa operação é muito útil quando precisamos descobrir elementos que duas listas possuem em comum:

>>> l1 = [1, 2, 3]
>>> l2 = [2, 4, 3]
>>> print set(l1).intersection(l2)
set([2, 3])

Perceba que convertemos l1 para conjunto para podermos usar o método intersection; já l2 não precisou ser convertida, pois esses métodos exigem que apenas o primeiro argumento seja um conjunto. Poderíamos obter o resultado da interseção como uma lista também:

>>> l3 = list(set(l1).intersection(l2))
>>> print l3
[2, 3]

O método intersection não modifica os conjuntos recebidos como parâmetro. Se quisermos que o resultado da interseção seja gravado como novo valor do primeiro conjunto, ao invés de retornar o novo conjunto como resultado, podemos usar o método intersection_update:

>>> a.intersection_update(b)
>>> print a
set([2, 3])

Diferença

Imagem da Wikipedia

B \ A (Crédito da imagem: Wikipedia)

A diferença entre dois conjuntos A e B retorna somente os elementos de A que não estão em B, ou seja, retira de A todos os elementos comuns a ambos os conjuntos:

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> print a.difference(b)
set([1, 2])
>>> print b.difference(a)
set([5, 6])

Observe que a.difference(b) é o mesmo que a \ b e que b.difference(a) é o mesmo que b \ a.

Assim como o método anterior, difference também não altera o conjunto sobre o qual é chamado. Para alterá-lo, é necessário usar o método difference_update().

Diferença simétrica

Diferença simétrica é uma operação sobre os dois conjuntos, que retorna todos os elementos (de ambos os conjuntos a e b) que pertencem a somente um dos conjuntos.

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> print a.symmetric_difference(b)
set([1, 2, 5, 6])

Diferença Simétrica

A △ B (Crédito da imagem: Wikipedia)

Pertinência

Além das operações tradicionais de união, interseção e diferença, também temos operações de verificação de pertinência. A seguir veremos algumas.

Para verificar se um determinado elemento pertence a um conjunto, podemos usar o já conhecido operador de pertinência in:

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> 1 in a
True
>>> 5 in a
False

Também podemos verificar se um conjunto é um subconjunto de outro:

>>> a = {1, 2, 3, 4}
>>> c = {1, 2}
>>> c.issubset(a)
True
>>> a.issubset(c)
False

Além disso, podemos verificar se um conjunto é superconjunto de outro:

>>> a.issuperset(c)
True

Outra relação importante que podemos checar é a disjunção entre dois conjuntos. Dois conjuntos são disjuntos se tiverem interseção nula. Exemplo:

>>> c = {1, 2}
>>> d = {3, 4}
>>> c.isdisjoint(d)
True

Removendo elementos duplicados de uma sequência

Por definição, um conjunto é uma coleção de valores únicos (e desordenados). Assim sendo, se passarmos ao construtor de conjuntos uma lista com valores repetidos, esses valores serão eliminados de forma a permanecer apenas um deles. Exemplo:

>>> lista = [1, 1, 2, 3, 5, 8]
>>> conjunto = set(lista)
>>> print conjunto
set([8, 1, 2, 3, 5])

Ou, se quisermos ter de volta uma lista:

>>> lista = list(set(lista))

ATENÇÃO: a operação acima pode (e, com grandes chances, irá) bagunçar a lista. Ou seja, a ordem original irá se perder.

>>> print lista
[8, 1, 2, 3, 5]

Leia mais

Entendendo os decorators

Hoje me deparei com um excelente texto sobre decorators que me inspirou a escrever algo sobre o assunto que para muita gente ainda é um tanto quanto nebuloso. Vou tentar aqui explicar o funcionamento de um decorator e mostrar algumas possíveis aplicações.

Aviso aos iniciantes: esse assunto pode ser um pouco confuso para quem ainda está iniciando em programação. Caso sinta dificuldades, não desanime e pule antes para a seção que contém as referências para melhor entendimento do texto.

O que é um decorator?

Um decorator é uma forma prática e reusável de adicionarmos funcionalidades às nossas funções/métodos/classes, sem precisarmos alterar o código delas.

O framework para desenvolvimento web Django oferece diversos decorators prontos para os desenvolvedores. Por exemplo, para exigir que o acesso a determinada view seja feito somente por usuários autenticados, basta preceder o código da view (que em geral é uma funçãozinha ou classe) pelo decorator @login_required. Exemplo:

@login_required
def boas_vindas(request):
    return HttpResponse("Seja bem-vindo!")

É claro que isso não é mágica. Como a gente pode ver no código-fonte do decorator login_required, os detalhes estão apenas sendo ocultados do código-fonte do nosso projeto. Assim, ao invés de ter que, a cada view, escrever o código que verifica se determinado usuário está autenticado, basta usar o decorator. Isso faz com que adicionemos a funcionalidade de verificar se um usuário está ou não logado no site, com uma linha de código apenas. Que barbada, não?

O decorator é um açúcar sintático que Python oferece aos desenvolvedores desde a versão 2.4, facilitando o desenvolvimento de códigos reusáveis.

OK, mas como implementar um decorator?

Você já sabe como um decorator pode ser usado, então agora vamos entender as internas desse recurso do Python.

Um decorator é implementado como uma função que recebe uma função como parâmetro, faz algo, então executa a função-parâmetro e retorna o resultado desta. O algo é a funcionalidade que adicionamos a nossa função original através do decorator.

Vamos escrever um decorator que sirva para escrever na tela o nome da função a ser executada, antes da execução da mesma. Como descrito acima, precisamos definir uma função que receba outra função como parâmetro, imprima o nome dessa, execute a função e retorne o seu resultado. Veja o código:

def echo_funcname(func):

    def finterna(*args, **kwargs):
        print "Chamando funcao: %s()"  % (func.__name__)
        return func(*args, **kwargs)

    return finterna

@echo_funcname
def dobro(x):
    return x*2

dobro(10)

Antes de mais nada, observe atentamente a função echo_funcname, pois existem alguns conceitos importantes dentro dela.

def echo_funcname(func):

    def finterna(*args, **kwargs):
        print "Chamando funcao: %s()"  % (func.__name__)
        return func(*args, **kwargs)

    return finterna

Veja que ela receba um parâmetro func (que espera-se que seja uma função) e retorna outra função (finterna). A função retornada, finterna, é “configurada” para executar ao seu final a função recebida como argumento pela função externa (echo_funcname), bem como retornar o valor de retorno da função recebida. Em outras palavras, echo_funcname() cria dentro de si próprio uma função chamada finterna(), que no final (linha 5) chama a função recebida como parâmetro. Mas, é importante perceber que a palavra-chave def somente cria a função (isto é, instancia um objeto do tipo função), não executando ela. Ou seja, echo_funcname cria uma função, configura ela para executar func() ao seu final, não a executa, mas sim somente retorna o objeto função, que então poderá ser chamada por quem recebê-la. (um assunto muito importante para o entendimento desse conceito de função dentro de função é o conceito de closures).

Caso tenha ficado confuso, perceba que finterna é um objeto como qualquer outro que estamos acostumados a criar dentro de nossas funções, como uma lista, por exemplo. A diferença é que esse objeto é uma função, o que pode parecer um pouco estranho, em um primeiro momento. Sendo um objeto qualquer, a função é instanciada, recebe um nome (finterna), e pode ser retornada, assim como todo objeto (tudo isso sem ser executada, pois não chamamos finterna).

Veja um exemplo de visualização de uma função que define outra função internamente (visualização gerada pelo excepcional pythontutor.com):

func

Se quiser visualizar a versão interativa, clique aqui (powered by PythonTutor.com).

Tendo a função echo_funcname() definida, agora poderíamos fazer o seguinte:

def echo_funcname(func):

    def finterna(*args, **kwargs):
        print "Chamando funcao: %s()"  % (func.__name__)
        return func(*args, **kwargs)

    return finterna

def dobro(x):
    """ Uma funcao exemplo qualquer.
    """
    return 2*x

dobro_com_print = echo_funcname(dobro)
print dobro_com_print(10)

Ao executar o código acima, teremos como resposta na tela:

Chamando funcao: dobro()
20

Criamos uma função chamada dobro(), que recebe um número e retorna o dobro desse número. Depois, passamos esse objeto do tipo function para a função echo_funcname() e recebemos como retorno outro objeto do tipo function, ao qual referenciamos como dobro_com_print. Perceba que dobro_com_print nada mais é do que uma referência a uma função mais ou menos assim:

def finterna(*args, **kwargs):
    print "Chamando funcao: %s()"  % (dobro.__name__)
    return dobro(*args, **kwargs)

Essa função foi gerada dentro de echo_funcname() e retornada, já com dobro no lugar de func. Assim, quando chamamos a função como em print dobro_com_print(10), estamos chamando a função acima, e passando 10 como argumento.

Mas, esse negócio todo de passar uma função como parâmetro e receber uma função como retorno de uma chamada de função é um pouco confuso. Para abstrair um pouco esses detalhes, Python oferece a sintaxe do @nome_do_decorator que precede a definição de funções. Assim, ao invés de:

dobro_com_print = echo_funcname(dobro)
print dobro_com_print(10)

Poderíamos apenas preceder a definição da função dobro() com o decorator @echo_funcname:

@echo_funcname
def dobro(x):
    """ Uma funcao exemplo qualquer.
    """
    return 2*x

Agora, ao chamar a função dobro(), estaríamos chamando a função decorada (isto é, acrescida de funcionalidades). No nosso caso, o decorator apenas adiciona a impressão na tela de um aviso sobre a chamada da função.

Enfim, um decorator nada mais é do que uma função que recebe outra função como parâmetro, gera uma nova função que adiciona algumas funcionalidades à função original e a retorna essa nova função.

Concluindo …

Os decorators formam um recurso muito importante para diminuir a duplicação e aumentar o reuso de código em um projeto. O conceito pode ser um pouquinho complicado para entender de primeira, mas uma vez que você o domine, você começará a perceber diversas oportunidades para implementar e usar decorators em seus projetos.

Leia mais

Por se tratar de um assunto mais complicado para iniciantes, segue aqui uma lista de textos que poderiam ser lidos, possibilitando um melhor entendimento sobre o assunto.

Funções como objetos:

Closures:

Os métodos mágicos de Python

Obs.: Códigos testados com a versão 2.7 do Python.

Quem está chegando em Python normalmente fica um pouco confuso ao ler o código de uma classe e perceber um monte de métodos com underscores (__) no nome. Para entender o que são esses métodos, vamos ver um exemplo.

Uma classe para números binários

Suponha que, por algum motivo, você receba a tarefa de implementar uma classe para representação de números em base binária.

class Binario(object):

    def __init__(self, valor_dec):
        self.valor_dec = valor_dec
        self.valor_bin = bin(self.valor_dec)  #bin() é uma função builtin

b = Binario(5)
print b

Se executarmos o código acima, teremos em b um objeto do tipo Binario, que representa o valor 5 em base-2. 5 em base binária é 101. Porém, a execução da linha print b mostrou a seguinte saída na tela:

<__main__.Binario object at 0x28286d0>


Isso porque o print executa a função str() no objeto recebido. Essa função, por sua vez, procura por um método chamado __str__() no objeto a ser impresso. Como não definimos um método com esse nome em nossa classe, o interpretador continua sua busca pelo método na classe que está acima de Binario na hierarquia de classes, que é object. Lá ele encontra o método __str__, que então retorna o texto <__main__.Binario object at 0x28286d0>, contendo o endereço do objeto na memória.

O método __str__() deve retornar uma representação em forma de string do valor do objeto. Para personalizar essa mensagem, ou seja, para fazer com que o print em objetos do tipo Binario mostre uma sequência de 0s e 1s representando o número binário em questão, vamos adicionar um método __str__() à nossa classe:

class Binario(object):

    def __init__(self, valor_dec):
        self.valor_dec = valor_dec
        self.valor_bin = bin(self.valor_dec)

    def __str__(self):
        return "%s" % (self.valor_bin)

b = Binario(5)
print b

Agora, o resultado da execução do código acima é o seguinte:


0b101

Que é o formato retornado pela função bin() quando chamada. O prefixo 0b é adicionado para indicar que se trata de um número binário. Podemos facilmente nos livrar desse prefixo para representar o número binário na tela usando operadores de slicing:

def __str__(self):
    return "%s" % (self.valor_bin[2:])

Beleza! Agora nosso número binário pode ser impresso corretamente na tela! 🙂

Sem perceber e sem chamá-los em lugar algum, já utilizamos dois métodos mágicos de Python:

  • __init__: método chamado para inicialização do objeto, logo após a sua construção;
  • __str__: método chamado pela função str() para obter o valor do objeto em forma de string;

Chamamos eles de métodos mágicos porque eles resolvem o nosso problema sem sequer termos que chamá-los. Quem os chama são códigos de outras classes/programas, que esperam que nossos objetos forneçam tais métodos.

E se agora quisermos comparar objetos do tipo Binario em operações relacionais como >, <, >=, <=, != e ==? Se tentarmos comparar duas instâncias de Binario usando algum desses operadores, podemos ter respostas inesperadas, visto que eles não irão fazer o que esperamos. O esperado é que a > b retorne True se o valor de a for maior do que o valor de b. Porém, onde definimos qual valor será usado para comparação dos objetos? Como não fizemos isso, o interpretador irá usar o id de ambos os objetos para a comparação.

Para definir como os objetos de nossa classe serão comparados, podemos implementar o método mágico __cmp__. Na documentação oficial, vemos instruções sobre como implementar esse método para que nossos objetos possam ser comparados e usados em operações relacionais:


object.__cmp__(self, other)
Deve retornar um inteiro negativo se self < other, zero se self == other, ou um número positivo se self > other.

Vamos então implementar o nosso método __cmp__. Podemos, para isso, usar o valor em decimal, que armazenamos internamente na variável self.valor_dec:

def __cmp__(self, other):
    if self.valor_dec > other.valor_dec:
        return 1
    elif self.valor_dec < other.valor_dec:
        return -1
    else:
        return 0

Que poderia também ser escrito como:

def __cmp__(self, other):
    return self.valor_dec - other.valor_dec

Tendo adicionado o código acima à classe Binario, agora podemos utilizar nossos objetos em operações relacionais:

b = Binario(1)
c = Binario(2)
if b < c:
    print "OK"

Mais uma vez, nosso método é executado sem que o chamemos explicitamente. Além dos métodos que vimos aqui, existem vários outros métodos mágicos que podemos implementar em nossos objetos para que o comportamento deles se pareça mais com o comportamento de objetos nativos da linguagem. Vou listar alguns deles a seguir:

  • __add__(self, other): para adicionarmos a possibilidade de aplicação do operador + aos nossos objetos. Para os outros operadores, também existem métodos mágicos (subtração(-): __sub__; multiplicação(*): __mul__, divisão(/): __div__, módulo(%): __mod__, potência(**): __pow__);
  • __call__(self): faz com que o objeto seja chamável (executável), assim como uma função é;
  • __len__: retorna o comprimento do objeto (se for um container);
  • __getitem__(self, key): para containers, retorna o elemento correspondente à chave key;

São muitos os métodos. Se você quiser conhecê-los melhor, sugiro dar uma olhada nesse texto (em inglês): http://www.rafekettler.com/magicmethods.html.

Os métodos mágicos (magic methods), também chamados de métodos dunderscore (double-underscore) ou de métodos especiais, são muito úteis pois permitem que objetos de nossas classes possuam uma interface de acesso semelhante aos objetos nativos da linguagem. A função sorted(), por exemplo, ordena os elementos de um iterável de acordo com o valor dos objetos que a compõe. Se definirmos nosso método de comparação, a função sorted() irá usá-lo para fazer a ordenação dos elementos da lista. Assim, é possível que códigos de terceiros lidem com nosso código sem sequer conhecê-lo. Veja mais sobre esse conceito em: Polimorfismo.

Simplificando as coisas com namedtuples

Antes de conhecer e até mesmo nos primeiros projetos que desenvolvi usando Python, era bem comum que eu escrevesse classes que não continham método algum (a não ser os famigerados getters/setters e o construtor). Elas eram normalmente usadas para representar objetos que tinham um papel mais passivo, como por exemplo, uma classe para representar as mensagens que o cliente passava para o servidor:

class Message(object):
    headers = []
    content = None
    from_addr = None
    to_addr = None

Ou então:

class Message(object):
    def __init__(self, content, from_addr, to_addr):
        self.headers = []
        self.content = content
        self.from_addr = from_addr
        self.to_addr = to_addr

    def add_header(self, info):
        self.headers.append(info)

Além disso, eu definia os setters/getters para cada atributo (muitas vezes sem pensar se iria precisar deles ou não, afinal, a maioria das IDEs já geravam tudo pra mim).

Mas aos poucos veio a sensação de que eu estava subutilizando Python criando classes somente para representação de objetos simples assim. Afinal, além de ser uma linguagem com tipagem dinâmica, Python ainda oferece várias estruturas para representação dos dados. Minha primeira idéia foi utilizar tuplas para representar os objetos a serem trocados entre os elementos. Por exemplo, poderia representar uma mensagem através de uma tupla de 4 elementos:

message = ([], content, from_addr, to_addr)

Assim, para imprimir o conteúdo da mensagem, eu teria que fazer:

print message[1]

Assim, seria sempre necessário saber em qual posição da tupla determinado campo está armazenado. Um atentado à legibilidade e manutenção do código! Depois, pensei em usar dicionários:

message = {'headers': [], 'content': content, 'from_addr': from_addr, 'to_addr': to_addr}

Feito! O problema da legibilidade tinha acabado. Agora eu poderia acessar o campo content usando o nome do campo como chave:

print message['content']

Mas, ainda não me parecia uma solução muito adequada. Foi então que veio a luz: descobri a namedtuple, que faz parte do pacote collections. O próprio Guido Van Rossum, criador da linguagem Python, recomendou recentemente o uso de namedtuples para representação de objetos. Além de evitar a sobrecarga sintática que a definição de uma classe dá ao código, ela também oferece melhor desempenho.

Usando as namedtuples

A definição de estruturas para representação de objetos com namedtuples é bem simples. Veja o exemplo abaixo:

>>> import collections
>>> Message = collections.namedtuple('Message', 'headers content from_addr to_addr')

A segunda linha acima mostra a criação de uma namedtuple que chamamos de Message, e que possui 4 campos: headers, content, from_addr e to_addr. O primeiro argumento que passamos para a factory namedtuple() é o nome para o novo tipo (em nosso caso, Message) e o segundo argumento é uma string contendo os nomes dos campos da estrutura, separados por espaços em branco ('headers content from_addr to_addr'). A chamada à collections.namedtuple() retorna uma nova subclasse de tuple, podendo assim ser usado como se fosse um novo tipo.

Tendo a estrutura definida, podemos então criar objetos do tipo Message da seguinte forma:

>>> m = Message([], "Hello, server!", "me", "some.address.com")

A partir daí, o acesso aos campos da mensagem é feito exatamente como faríamos com instâncias de classes que definimos:

>>> print m.content
Hello, server!
>>> m.headers.append("alguma informação")
>>> print m.headers
["alguma informação"]
>>> m.to_addr = "localhost"
>>> print m.to_addr
localhost

Barbadinha, né? A partir de agora, quando for criar uma nova classe para representação de algo em seu projeto, verifique se não é o caso de definir o novo tipo usando namedtuples ao invés de uma nova classe. Se for possível, use a namedtuple. Mas, nem sempre uma namedtuple será suficiente para representar determinados objetos. Nesses casos, as classes são a solução mais adequada.

Desempacotamento de tupla

Tuple unpacking, ou em bom português, desempacotamento de tupla. Tá aí algo que usamos pra caramba, mas sobre o qual pouco ouvimos falar. Desempacotar uma tupla pode ser explicado como o ato de atribuir os elementos dela individualmente a outros objetos. Veja um exemplo de desempacotamento de tupla:

>>> t = (1, 2, 3, 4)
>>> a, b, c, d = t  # "desempacotando" uma tupla
>>> print b * c
6

No exemplo acima, o primeiro elemento da tupla t é atribuído para o nome a. O segundo elemento de t é atribuído para b, e assim por diante. É óbvio que, para desempacotar uma tupla, é necessário que tenhamos no lado esquerdo da expressão a quantidade necessária de variáveis para receber os valores. Veja uma situação que gera um erro por tentarmos desempacotar uma tupla de 4 elementos para 3 variáveis:

>>> t = (1, 2, 3, 4)
>>> a, b, c = t
Traceback (most recent call last):
  File "", line 1, in
ValueError: too many values to unpack

"ValueError: too many values to unpack", que significa “valores demais para desempacotar".

Mas isso é útil para quê?

Já viu uma função retornando mais de um valor em um único return em Python?

def f(x):
    return x, x*2, x*3

valor, dobro, triplo = f(2)

Isso é algo bastante comum em código Python. O código da segunda linha (return x, x*2, x*3) na realidade retorna apenas um valor, que é uma tupla. A expressão x, x*2, x*3 cria uma tupla de 3 elementos, apesar de não estar envolta em parênteses. Assim sendo, a chamada de função f(2) retorna uma tupla de 3 valores, que são então desempacotados para as variáveis valor, dobro e triplo, respectivamente.

Percorrendo listas de tuplas

Quando temos uma lista contendo tuplas, podemos percorrê-la assim como qualquer outra lista. Veja:

>>> lista = [(1, 2, 3), (2, 4, 6), (4, 8, 12), (8, 16, 24)]
>>> for tupla in lista:
...     print tupla
...
(1, 2, 3)
(2, 4, 6)
(4, 8, 12)
(8, 16, 24)

Dentro do for, poderíamos desempacotar os valores de cada tupla, se precisássemos usá-los individualmente:

>>> lista = [(1, 2, 3), (2, 4, 6), (4, 8, 12), (8, 16, 24)]
>>> for tupla in lista:
...     a, b, c = tupla
...     print a * b * c
...
6
48
384
3072

Mas, poderíamos fazer melhor, desempacotando os elementos dentro da expressão do for:

>>> lista = [(1, 2, 3), (2, 4, 6), (4, 8, 12), (8, 16, 24)]
>>> for (a, b, c) in lista:
...     print a * b * c
...
6
48
384
3072

Poderíamos também omitir os parênteses na hora de desempacotar as tuplas:

>>> lista = [(1, 2, 3), (2, 4, 6), (4, 8, 12), (8, 16, 24)]
>>> for a, b, c in lista:
...     print a * b * c
...
6
48
384
3072

Mas nem tudo interessa

Considere que nas tuplas da lista lista acima, somente nos interessa o primeiro elemento de cada tupla. Para não precisar criar dois novos nomes (b e c) que nunca serão usados, podemos utilizar um idioma que é um tanto comum em código python: usar o caractere de undescore _ como o nome da variável que vai receber o primeiro e último valores das tuplas:

>>> lista = [(1, 2, 3), (2, 4, 6), (4, 8, 12), (8, 16, 24)]
>>> for a, _, _ in lista:
...     print a * 2
...
2
4
8
16

Lembre-se: usamos isso somente em casos em que os elementos não serão necessários no escopo do for.

O _ é utilizado comumente como um nome para não me interessa. Por exemplo*, em uma tupla contendo nome, sobrenome e apelido, em um momento em que estamos interessados apenas no nome e no sobrenome, poderíamos usar o _ para indicar que o apelido não é importante neste momento:

dados_pessoais = ('Joao', 'Silva', 'joaozinho')
...
nome, sobrenome, _ = dados_pessoais

*Exemplo adaptado dessa resposta no StackOverflow.com

Como o autor da resposta no link acima comenta, é preciso tomar cuidado com o uso do _, pois ele também é utilizado em outros contextos e isso pode gerar confusão e mau-funcionamento. Ele é bastante usado com a biblioteca de internacionalização gettext como um atalho para funções usadas com muita frequência.

Então é isso. O desempacotamento de tuplas é um dos recursos que eu considero mais legais em Python, pois elimina bastante código desnecessário. Até a próxima! 🙂