Arquivo da categoria: estruturas

Padrão

Publicado por

Postado no

25 de fevereiro de 2018

Publicado em

dicas rápidas, estruturas

comentários

3 Comentários

Preservando a ordem de sequências ao remover duplicatas

Imagine que você tenha uma lista com as URLs extraídas de uma página web e queira eliminar as duplicatas da mesma.

Transformar a lista em um conjunto (set) talvez seja a forma mais comum de se fazer isso. Tipo assim:

>>> urls = [
    'http://api.example.com/b',
    'http://api.example.com/a',
    'http://api.example.com/c',
    'http://api.example.com/b'
]
>>> set(urls)
{'http://api.example.com/a',
 'http://api.example.com/b',
 'http://api.example.com/c'}

Porém, observe que perdemos a ordem original dos elementos. Esse é um efeito colateral indesejado da eliminação de duplicatas através da transformação em um conjunto.

Um jeito de preservar a ordem dos elementos após a remoção das duplicatas é utilizar este macete com collections.OrderedDict:

>>> from colllections import OrderedDict
>>> OrderedDict.fromkeys(urls).keys()
['http://api.example.com/b',
 'http://api.example.com/a',
 'http://api.example.com/c']

Legal né? Agora vamos entender o que o código acima fez.

Antes de mais nada, é preciso saber que OrderedDict é uma estrutura de dados muito similar a um dicionário. A grande diferença é que o OrderedDict guarda internamente a ordem de inserção dos elementos. Assim, quando iteramos sobre um objeto desse tipo, ele irá retornar seus elementos na ordem em que foram inseridos.

Agora vamos quebrar as operações em partes para entender melhor o que aconteceu:

>>> odict = OrderedDict.fromkeys(urls)

O método fromkeys() cria um dicionário usando como chaves os valores passados como primeiro parâmetro e como valor o que for passado como segundo parâmetro (ou None, caso não passemos nada).

Como resultado, temos:

>>> odict
OrderedDict([('http://api.example.com/b', None),
('http://api.example.com/a', None),
('http://api.example.com/c', None)])

Agora que temos um dicionário com as chaves mantidas em ordem de inserção, podemos chamar o método keys() para obter somente as chaves que, neste caso, são as nossas URLs:

>>> odict.keys()
['http://api.example.com/b',
'http://api.example.com/a',
'http://api.example.com/c']

Obs.: em Python 3, o método keys() retorna uma view ao invés de uma lista. Esse tipo de objeto suporta iteração e teste de pertinência, assim como a lista. Caso você realmente precise de uma lista, basta construir uma usando o resultado de keys():

>>> list(odict.keys())

A eliminação de duplicatas é só uma consequência do design de dicionários, já que a unicidade das chaves é uma das propriedades fundamentais dessa estrutura de dados.

Caso queira entender melhor os princípios por trás de um dicionário, leia sobre tabelas hash: https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/st-hash.html

Padrão

Publicado por

Postado no

19 de janeiro de 2015

Publicado em

algoritmos, estruturas

comentários

10 Comentários

Á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 nó (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 nó, 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!

Padrão

Publicado por

Postado no

19 de junho de 2014

Publicado em

estruturas, módulos, strings

comentários

4 Comentários

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.

Padrão

Publicado por

Postado no

18 de junho de 2013

Publicado em

dicas rápidas, estruturas, listas

comentários

4 Comentários

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

Padrão

Publicado por

Postado no

9 de junho de 2013

Publicado em

estruturas, misc

comentários

5 Comentários

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:

Padrão

Publicado por

Postado no

11 de março de 2013

Publicado em

estruturas, misc, oo

comentários

2 Comentários

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.

Padrão

Publicado por

Postado no

26 de janeiro de 2013

Publicado em

estruturas

comentários

1 comentário

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.

Padrão

Publicado por

Postado no

10 de janeiro de 2013

Publicado em

estruturas

comentários

3 Comentários

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! 🙂

Padrão

Publicado por

Postado no

25 de setembro de 2012

Publicado em

estruturas, listas

comentários

14 Comentários

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
Padrão

Publicado por

Postado no

3 de setembro de 2012

Publicado em

estruturas

comentários

7 Comentários

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.