Funções anônimas em Python

As funções anônimas — em Python também chamadas de expressões lambda — representam um recurso bem interessante da linguagem Python, mas cuja utilidade pode não ser muito óbvia à primeira vista.

Uma função anônima é útil principalmente nos casos em que precisamos de uma função para ser passada como parâmetro para outra função, e que não será mais necessária após isso, como se fosse “descartável”.

Um exemplo

A builtin map recebe como parâmetros: uma função e uma sequência de dados nos quais a função será aplicada. Agora, imagine que temos uma lista com os números entre 1 e 100 e precisamos de outra lista que contenha os dobros dos números de 1 a 100.

numeros = list(range(1, 101))  # compatível com python 3

Para obter a lista de dobros, poderíamos chamar a função map, passando a ela uma função que retorna o dobro do elemento recebido como parâmetro. Sem funções anônimas, faríamos assim:

def dobro(x):
    return x*2

dobrados = map(dobro, numeros)

Assim, a função dobro será aplicada para cada elemento de numeros e o resultado de cada chamada será adicionado à lista dobrados. Porém, a função dobro será usada somente aqui nessa parte do programa, e o desenvolvedor pode achar que sua presença ali polui o código de forma desnecessária. Como não irá utilizá-la mais em lugar algum, essa função pode ser transformada em uma função anônima, usando a expressão lambda:

dobrados = map(lambda x: x * 2, numeros)

A expressão lambda x: x * 2 cria uma função anônima que recebe um valor como entrada e retorna como resultado tal valor multiplicado por 2. Esse tipo de função é assim chamada porque não podemos nos referir a ela através de um nome, diferentemente da função dobro, por exemplo. As funções anônimas que, em Python, são obtidas através das expressões lambda, são bastante limitadas e devem ser utilizadas com cautela, pois o seu abuso pode comprometer a legibilidade do código. Veja alguns exemplos de abuso das expressões lambda: http://wiki.python.org/moin/DubiousPython#Overuse_of_lambda.

Caso você ainda não tenha compreendido o tal do anonimato da função, costumo pensar em um exemplo que usamos com frequência onde também existe anonimato. Você já passou uma lista literal para uma função, como faço no exemplo a seguir?

soma = sum( [1, 1, 2, 3, 5, 8, 13, 21] )

Você concorda que a lista passada como argumento é também um objeto anônimo? A ideia é semelhante a da função anônima, pois passamos objetos “descartáveis”, como no trecho acima, quando sabemos que não vamos precisar daquele objeto em outros trechos do código.

Para aprender mais sobre as expressões Lambda de Python, leia:

Como funcionam as listas de Python?

Nas primeiras vezes em que ouvi falar das listas de Python, por alguma razão eu acreditava que elas eram implementadas como listas encadeadas. Porém, se assim fosse, teríamos um problema: o custo para acessar um elemento dependeria diretamente da posição em que ele estivesse dentro da lista — isto é, um acesso ao milésimo elemento de uma lista seria mais custoso do que um acesso ao primeiro elemento. Isso porque as listas encadeadas são estruturas de acesso sequencial, onde para acessar o elemento da posição i, é preciso antes percorrer os i-1 elementos que o precedem.

Vamos executar alguns testes para ver se o custo para acesso a um elemento está relacionado à posição do elemento na lista. Nos testes, vamos gerar listas de um milhão de elementos e acessar elementos de diferentes posições em cada teste. Para isso, vamos usar o módulo timeit:


$ python -m timeit -s "lista = range(1000000)" "lista[0] = 0"
10000000 loops, best of 3: 0.0276 usec per loop
$ python -m timeit -s "lista = range(1000000)" "lista[10] = 0"
10000000 loops, best of 3: 0.0276 usec per loop
$ python -m timeit -s "lista = range(1000000)" "lista[1000] = 0"
10000000 loops, best of 3: 0.0276 usec per loop
$ python -m timeit -s "lista = range(1000000)" "lista[100000] = 0"
10000000 loops, best of 3: 0.0276 usec per loop

Os experimentos nos mostram que obtivemos tempos de acesso constantes para as diversas posições da lista. Chamamos de acesso aleatório essa capacidade de termos tempos de acesso iguais para todos os elementos contidos na sequência, independentemente das suas posições. Em estruturas de acesso aleatório, o custo para acessar o primeiro, o i-ésimo ou o último elemento deverá ser o mesmo, diferentemente de estruturas de acesso sequencial.

Para que conseguir o desempenho apresentado nos testes acima, é bem provável que as listas de Python não sejam implementadas sobre listas encadeadas, mas sim sobre arrays, que são estruturas de acesso aleatório. Para confirmar tal hipótese, vamos verificar o código-fonte do CPython. O arquivo listobject.h contém a definição da estrutura de dados que representa uma lista em Python:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Na estrutura acima, dá pra ver que a lista de Python é realmente implementada sobre um array (campo ob_item da estrutura) e, para entendermos melhor porque os arrays são eficientes, vamos dar uma olhada mais a fundo na próxima seção.

Como funcionam os Arrays?

Um array é uma área contígua de memória utilizada para armazenar vários elementos de um mesmo tipo em uma única variável. Exemplo de array:

array

Arrays são bons porque são simples e porque o acesso a qualquer elemento dentro dele é muito rápido, pois é feito através de índices, que são utilizados como deslocamentos com relação ao endereço inicial do array na memória. Podemos dizer que os arrays fornecem acesso aleatório, pois o tempo e a complexidade para acessar qualquer elemento independem do tamanho do array e da posição do elemento desejado. Vamos ver agora o porquê disso.

Imagine que o array acima esteja na memória do computador, a partir do endereço 2048, como mostra a imagem abaixo.

array2

O endereço na memória do elemento contido em uma posição i do array pode ser calculado de uma forma bem simples:

endereço base + i * tamanho em bytes do tipo

O acesso a uma posição de um array nada mais é do que um acesso ao endereço de memória calculado através da expressão acima. Desse modo, o tempo de acesso a qualquer um dos elementos de um array é igual, pois tudo que é preciso para isso é calcular o endereço de memória do elemento através de uma expressãozinha aritmética e fazer um acesso ao endereço de memória calculado. Ou seja, um array tem tempo de acesso constante — O(1) — para acesso a um elemento qualquer (diferentemente das listas encadeadas, que tem tempo de acesso linear – O(n)).

Essa característica faz com que o array seja uma estrutura mais atrativa devido ao tempo de acesso a um elemento aleatório quando comparado a estruturas como as listas encadeadas, nas quais, para acessar um elemento k, é necessário antes passar por todos os k-1 elementos que o precedem. Essa diferença é bem significativa quando estivermos lidando com listas ou arrays com alguns milhares ou milhões de elementos.

Entretanto, se for preciso redimensionar um array, pode ser necessário mover todo o conteúdo do mesmo para outra área que contenha espaço contíguo suficiente para acomodar o array antigo, além do espaço extra que precisamos. Já com uma lista encadeada, esse problema não existe, pois os elementos não precisam estar em posições contíguas de memória.

O que acontece quando fazemos um append numa lista?

As listas de Python são estruturas que crescem dinamicamente, alocando mais espaço para novos elementos sempre que for necessário. Isso poderia implicar em uma perda de desempenho ao fazer a inserção de novos elementos na lista, pois seria necessário realocar o array subjacente para que os novos elementos caibam dentro dele.

A cada vez em que tentamos fazer a inserção de um novo elemento em uma lista cheia, é preciso:

  1. Alocar um novo espaço contíguo que seja capaz de acomodar nosso array com os novos elementos adicionais.
  2. Copiar todos os elementos do array para a nova área de memória.
  3. Liberar o espaço anteriormente ocupado pelo array, para que o mesmo possa ser reutilizado.

Porém, de acordo com o código fonte do CPython, sempre que for necessário realocar o array subjacente, é incluído um pouco de espaço extra para evitar a realocação desse array nas próximas inserções. O espaço extra a ser alocado é proporcional ao tamanho atual da lista e é calculado assim:

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

De acordo com os comentários no código do CPython, essa sobre-alocação vale a pena e permite que o tempo para alocação acabe sendo amortizado quando ocorre uma grande sequência de appends na lista.

Enfim…

As listas são as estruturas padrão para representação de sequências de dados em Python e é importante que saibamos o que está acontecendo quando trabalhamos com elas. Para conhecer as listas mais a fundo, você pode ler o código fonte do CPython.

Vários outros posts aqui no blog já trataram sobre a utilização de listas; confira alguns:

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

Colorindo grafos — ou, como escolher cores para um mapa automaticamente

Imagine que você tenha um mapa com algumas áreas delimitadas (países, estados, etc), e deseja colorir cada área com uma cor diferente das áreas vizinhas.

Para um mapa pequeno (digamos, com no máximo 7 áreas), você pode simplesmente atribuir uma cor para cada área e se dar por satisfeito. Mas para um mapa com muitas áreas, você provavelmente quer usar um número mínimo de cores: muitas cores diferentes vão deixar o mapa confuso.

Esse é um típico problema a ser resolvido com coloração de grafos, uma área da ciência da computação explorada ativamente ainda hoje. Existe uma gama de problemas que podem ser resolvidos com técnicas desse tipo — outro exemplo popular é o quebra-cabeça Sudoku.

Hoje vamos mostrar um exemplo resolvendo esse problema usando um algoritmo simples para achar a configuração de cores mínima.

Veja a representação visual do grafo para colorir um mapa dos países da América do Sul:

Grafo colorido dos países num mapa da América do Sul

Colorização do grafo dos países da América do Sul usando 4 cores

Ao fim desse post, você terá aprendido a gerar colorizações e imagens para grafos como esse. :)

Escolhendo uma representação para o grafo

Existem várias maneiras de representar grafos com diferentes relações custo-benefício por operação, você escolhe a mais apropriada dependendo do tipo de grafo e do problema que você vai resolver. As duas representações mais comuns são matriz de adjacências e lista de adjacências — as demais são geralmente variações dessas.

Para o nosso problema, vamos simplesmente usar um dicionário Python mapeando os nós adjacentes:

grafo = {
    'A': ['B', 'C'],
    'B': ['A'],
    'C': ['A'],
}

Essa representação contém um pouco de duplicação, mas é interessante porque deixa trivial obter os nós do grafo fazendo grafo.keys() e consultar os nós adjacentes de um nó com grafo[nó].

Implementando o algoritmo

Vamos usar um algoritmo de colorização de grafos simples: começamos testando uma configuração com N cores, e caso detectamos que não seja possível, tentamos com N+1. Repetimos isso até encontrarmos uma solução ou atingirmos o limite de tentativas válidas.

Veja o código:

def try_coloring(graph, num_colors):
    assert num_colors >= 0, "Invalid number of colors: %s" % num_colors
    colors = {}

    def neighbors_have_different_colors(nodes, color):
        return all(color != colors.get(n) for n in nodes)

    for node, adjacents in graph.items():

        found_color = False

        for color in range(num_colors):
            if neighbors_have_different_colors(adjacents, color):
                found_color = True
                colors[node] = color
                break

        if not found_color:
            return None

    return colors


def find_graph_colors(graph):
    for num_colors in range(1, len(graph)):
        colors = try_coloring(graph, num_colors)
        if colors:
            return colors

Temos duas funções:

try_coloring() recebe um grafo e um número de cores para tentar. Ela tenta construir uma configuração de cores para o grafo, atualizando um dicionário que mapeia as cores para cada nó. Caso encontre uma configuração de cor válida a função devolve o dicionário; caso contrário, devolve None.

find_graph_colors() recebe um grafo e simplesmente aciona a função try_coloring() com diferentes valores para o número de cores, até que encontre uma configuração válida (ou esgote as tentativas). Também devolve a configuração encontrada ou None caso não for possível.

Coloque o código acima em um arquivo graph_coloring.py, e experimente chamar a função try_coloring() usando o shell para o nosso grafo exemplo:

>>> from graph_coloring import *
>>> grafo = {
...     'A': ['B', 'C'],
...     'B': ['A'],
...     'C': ['A'],
... }
>>> try_coloring(grafo, 1)
>>> try_coloring(grafo, 2)
{'A': 0, 'C': 1, 'B': 1}

Repare como a tentativa de colorir com apenas uma cor não funciona, mas a segunda já fornece uma configuração de cores válida para o nosso pequeno grafo. A propósito, a sessão acima está suplicando para ser usada como doctest para a função try_coloring(). ;-)

Bem, esse algoritmo é um pouco ingênuo e definitivamente não-otimizado, pois envolve um certo retrabalho a cada vez que tenta uma configuração de cores nova. Isso não é um problema para os grafos que vamos usar, então se preocupar com performance agora é desnecessário, mas é legal perceber onde podemos mexer caso seja necessário melhorá-lo.

Para o caso específico de mapas, existe um teorema afirmando que é sempre possível resolver esse problema usando 4 cores. Isso funciona porque os grafos que representam mapas são sempre grafos planares, isto é, podem ser representados num plano sem nenhuma aresta se cruzando — o que reduz as possibilidades de conexões entre os vértices.

Gerando uma representação visual

Uma maneira interessante de validar o nosso trabalho acima (e mais divertida do que usando testes de unidade) é gerar uma representação visual do grafo com as respectivas cores.

Para isso, vamos usar a suite open source de software para visualização de grafos Graphviz (instale no Debian/Ubuntu/Mint com sudo apt-get install graphviz; há pacotes também para Windows e Mac).

Iniciação ao uso do GraphViz

O Graphviz usa uma linguagem própria para descrever grafos chamada DOT, que você pode explorar usando a aplicação GraphViz Workspace.

Você também pode criar um arquivo.dot manualmente usando seu editor de texto favorito, e testar a saída com o comando dot. Crie um arquivo com o seguinte conteúdo que descreve nosso grafo de exemplo:

graph {
    A -- B;
    A -- C;
}

Compile uma imagem PNG com o comando dot:

dot -Tpng -o resultado.png arquivo.dot

Se você tem o ImageMagick instalado (no Debian/Ubuntu/Mint: sudo apt-get install imagemagick), pode visualizar a imagem diretamente fazendo pipe do comando dot para o comando display:

dot -Tpng arquivo.dot | display

grafo1

Para gerarmos grafos coloridos, vamos gerar uma representação do grafo que lista as conexões/arestas do grafo e imprime a configuração de cores por último, semelhante ao exemplo seguinte:

graph {
    A -- B;
    A -- C;
    A [style="filled",fillcolor="#ffffb2"];
    B [style="filled",fillcolor="#fd5d3c"];
    C [style="filled",fillcolor="#41b6c4"];
}

grafo2

Para uma documentação mais completa sobre como usar a ferramenta dot para desenhar grafos, veja o documento Drawing graphs with dot.

Gerando a representação DOT

Eis a nossa gloriosa função para gerar a representação do nosso grafo usando a linguagem DOT:

PALETTE = ('#8dd3c7', '#ffffb3', '#bebada', '#fb8072', '#80b1d3', '#fdb462',
           '#b3de69', '#fccde5', '#d9d9d9', '#bc80bd', '#ccebc5', '#ffed6f')


def generate_dot(graph, colors=None, palette=PALETTE):
    assert len(set(colors.values())) <= len(palette), (
        "Too few colors in the palette")

    edges = []
    for node, adjacents in graph.items():
        for n in adjacents:
            if not ((node, n) in edges or (n, node) in edges):
                edges.append((node, n))

    result = 'graph {\n'
    result += ''.join('    "{}" -- "{}";\n'.format(*e) for e in edges)

    if colors:
        style = '    "{}" [style="filled",fillcolor="{}",shape=box];\n'
        result += ''.join(style.format(node, palette[color])
                          for node, color in colors.items())
    result += '}\n'

    return result

A função recebe um grafo na representação de dicionário que combinamos no começo, um dicionário mapeando os números das cores para os nós do grafo (opcional) e uma paleta de cores (usada para obter as cores propriamente ditas, indexadas pelos números do dicionário de cores).

Nota: as cores da paleta fornecida são de uma das paletas disponíveis no site do GraphViz baseadas no fantástico trabalho da Cynthia Brewer.

Exemplo de saída da função generate_dot() para o nosso grafo de exemplo, usando uma paleta própria:

>>> from graph_coloring import *
>>> grafo = {
... 'A': ['B', 'C'],
... 'B': ['A'],
... 'C': ['A'],
... }
>>> colors = try_coloring(grafo, 2)
>>> colors
{'A': 0, 'C': 1, 'B': 1}
>>> print(generate_dot(grafo, colors, palette=['red', 'yellow']))
graph {
 "A" -- "B";
 "A" -- "C";
 "A" [style="filled",fillcolor="red",shape=box];
 "C" [style="filled",fillcolor="yellow",shape=box];
 "B" [style="filled",fillcolor="yellow",shape=box];
}

Gerando a imagem com GraphViz para essa mesma saída, obtemos a imagem:

grafo3

Finalizando

Veja o exemplo completo aqui (baixar graph_coloring.py), contendo o código mostrado nesse post mais a geração do grafo do mapa da América Latina mostrado no começo do post.

Desafio: experimente rodar com Python 2 e Python 3, tem uma sutil diferença no resultado. Consegue sacar o quê e por quê? Poste nos comentários. ;-)

Acessando a API REST do Twitter

Dando sequência ao post anterior sobre APIs REST, este post irá mostrar como utilizar uma API REST “de verdade”: a API do Twitter.

A API do Twitter

A API REST do twitter, em sua versão 1.1, fornece acesso a vários recursos, dentre os quais podemos destacar: Tweets, Search, Direct Messages, Users, Friends & Followers e Trends. Para uma lista exaustiva dos recursos, veja a documentação oficial em dev.twitter.com/docs/api/1.1.

Porém, boa parte dos recursos oferecidos pela API necessita de autenticação para que sejam fornecidos para sua aplicação. Dessa forma, vamos ver rapidamente como sua aplicação pode se autenticar junto ao serviço do Twitter.

Autenticação

A API REST do twitter permite a autenticação através de dois mecanismos baseados no padrão OAuth:

  1. Autenticação application-only: a autenticação não fica vinculada a um usuário específico, mas sim a uma aplicação previamente registrada. Quando autenticado com esse mecanismo, sua aplicação não poderá realizar algumas operações típicas de um usuário, como postar tweets, por exemplo. Esse tipo de autenticação é mais indicado para aplicações que não terão um usuário interagindo com a rede social. Um exemplo seria um app que vai extrair dados do twitter para realizar análises.
  2. Autenticação de usuário: a autenticação se dá diretamente por um usuário, de forma que a aplicação possa realizar operações comuns a usuários. Esse tipo de mecanismo é mais indicado para o caso de aplicativos que vão interagir com a rede social pelo usuário, como um app que posta as músicas mais ouvidas pelo usuário na semana.

Neste post, usaremos somente o primeiro tipo de autenticação (application only).

Autenticação Application-only

Antes de mais nada, precisamos conhecer alguns conceitos básicos de autenticação usando o padrão OAuth. Para que possamos nos identificar como usuários de um serviço que utiliza um mecanismo de autenticação baseado em OAuth, é preciso que tenhamos os seguintes dados:

  1. API Key: uma chave utilizada para que o nosso app se identifique perante o Twitter.
  2. API Secret: um segredo usado pelo nosso app para provar que é o dono da API Key.
  3. Access Token: depois de identificado junto ao serviço, nosso app precisa enviar o access token para que o serviço possa verificar qual é o nível de acesso que o app possui.
  4. Access Token Secret: segredo usado pelo nosso app para provar que é o dono do access token.

Como Obter Essas Chaves com o Twitter

Para obter as chaves de acesso ao serviço é preciso primeiramente registrar um aplicativo junto ao Twitter. Acesse apps.twitter.com e clique no botão “Create new app” para registrar um aplicativo para acesso à API. Primeiramente, você terá que preencher alguns dados básicos, como mostrado na imagem abaixo:

twitter1

Após isso, você será redirecionado para a página de gerenciamento do seu app, como mostra a imagem abaixo.

twitter2

Vá até a aba “API Keys” para acessar a página de gerenciamento das chaves de acesso do seu app ao serviço REST do twitter. Você verá uma página semelhante à da imagem abaixo.

twitter3

Nela, clique no botão “Create my access token” (em vermelho na imagem acima) para que seja criado o token de acesso do app ao serviço. A imagem abaixo mostra a aba “API Keys” após termos criado as chaves de acesso necessárias.

 

twitter4

Agora que já temos todos os dados que precisamos para autenticar nosso aplicativo, vamos ver como fazer a autenticação junto ao serviço.

Autenticando no serviço

Para nos autenticarmos no serviço do Twitter, precisaremos da biblioteca requests-oauthlib (instalável via pip install requests_oauthlib). De posse dela e das chaves geradas na etapa anterior, vamos criar uma sessão OAuth da seguinte forma:

>>> from requests_oauthlib import OAuth1Session
>>> session = OAuth1Session(API_KEY, API_SECRET, ACCESS_TOKEN, ACCESS_TOKEN_SECRET)

Agora, podemos usar o objeto session recém criado para realizar acesso à API.

Acessando os recursos de busca da API

Vamos começar fazendo uma busca pelo termo #python, usando o recurso search fornecido pela API. De acordo com a documentação, uma busca simples pode ser feita passando um parâmetro q à URL https://api.twitter.com/1.1/search/tweets.json. Veja no código abaixo que estamos executando as requisições sobre o objeto session criado anteriormente:

>>> response = session.get('https://api.twitter.com/1.1/search/tweets.json?q=%23python')
>>> print response.status_code
200

Observe que passamos a string "%23python" ao parâmetro q.  "%23" é a representação do caractere "#" no esquema de codificação de URLs usado na web, por isso a utilizamos na URL enviada ao serviço ao invés do caractere "#". Para não termos que codificar a URL “na mão”, podemos utilizar a função requests.utils.quote() para codificar os caracteres da URL pra gente:

>>> print requests.utils.quote("#python")
%23python
>>> url = "https://api.twitter.com/1.1/search/tweets.json?q=%s"
>>> url = url % (requests.utils.quote("#python"))
>>> response = session.get(url)

O conteúdo retornado pelo serviço é uma string em formato JSON, e podemos decodificá-la usando a função json.loads:

>>> import json
>>> tweets = json.loads(response.content)

A chamada à função loads retorna um dicionário:

>>> print tweets.keys()
[u'search_metadata', u'statuses']

Os tweets encontrados são representados em uma lista dentro do dicionário, na posição de chave statuses:

>>> print len(tweets['statuses'])
15

Cada tweet é um dicionário dentro dessa lista:

>>> print type(tweets['statuses'][0])
<type 'dict'>

E para cada dicionário representando um tweet, temos os seguintes atributos:

>>> print tweets['statuses'][0].keys()
[u'contributors', u'truncated', u'text', u'in_reply_to_status_id', u'id',
 u'favorite_count', u'source', u'retweeted', u'coordinates', u'entities',
 u'in_reply_to_screen_name', u'in_reply_to_user_id', u'retweet_count', u'id_str',
 u'favorited', u'user', u'geo', u'in_reply_to_user_id_str', u'possibly_sensitive',
 u'lang', u'created_at', u'in_reply_to_status_id_str', u'place', u'metadata']

Podemos ver alguns atributos interessantes, como text e user:

>>> print tweets['statuses'][0]['text']
#python wanna *split* a #Flask application into separates modules?blueprints: 1)create it; 2)register in the *root* http://t.co/DlZxJrw1qq

Já o atributo user contém outro dicionário, com as informações do usuário:

>>> print tweets['statuses'][0]['user']['description']
Algorithms. Program languages theory. UML. Design pattens. Python. C. C++. PHP. Perl. vim. PostgreSQL. MariaDB. Unix. Me.

Enfim, de cada tweet podemos tirar várias informações interessantes. Podemos, por exemplo, imprimir os tweets ordenados pela quantidade de retweets (do mais para o menos retweetado). Cada tweet possui um atributo chamado "retweet_count", que usaremos na ordenação da lista de tweets contida em tweets["statuses"]. Veja o código abaixo:

>>> for t in sorted(tweets["statuses"], key=lambda x: x["retweet_count"], reverse=True):
        print t["text"]

Limites no acesso

Para evitar abusos, a maioria dos provedores de serviços web impõem limites na quantidade de requisições que um cliente pode fazer dentro de uma janela de tempo. Cada serviço possui suas regras, portanto é bom conhecê-las para que seu app não deixe de funcionar de forma inesperada. Esse tipo de limite é por vezes chamado de rate limiting e você pode descobrir como isso funciona no twitter lendo a seção da documentação deles que fala sobre isso.

Além desses limites, requisições de busca como as apresentadas anteriormente possuem limites na quantidade de valores que retornam por vez. Para evitar respostas muito grandes, o serviço do Twitter não retorna mais do que 100 tweets como resposta a uma única requisição. Por padrão, são retornados 15 tweets, mas esse valor pode ser alterado através do parâmetro count. Para obter 80 resultados nas requisições de pesquisa usadas anteriormente, poderíamos adicionar o parâmetro count com valor 80 à URL do serviço:

>>> url = "https://api.twitter.com/1.1/search/tweets.json?q=%s&count=%d"
>>> url = url % (requests.utils.quote("#python"), 80)
>>> response = session.get(url)
>>> tweets = json.loads(response.content)
>>> print len(tweets['statuses'])
80

E se precisarmos mais do que 100 resultados?

Se precisamos obter os primeiros 1000 resultados, teremos que fazer 10 requisições solicitando 100 resultados de cada vez. Porém, 10 requisições à mesma URL possuem boas chances de terem como resultado os mesmos tweets. Para que não recebamos sempre os mesmos 100 resultados, a API possibilita que informemos o id do tweet mais antigo recebido na última resposta, de forma que, na próxima resposta, somente serão inclusos aqueles tweets que possuírem id menor que o especificado. Assim, basta pegar o menor id dentro do grupo de tweets recebidos para solicitar os próximos 100 tweets. Assim como anteriormente, vamos solicitar os 100 primeiros tweets contendo a palavra "python":

>>> url = 'https://api.twitter.com/1.1/search/tweets.json?q=python&count=100'
>>> response = session.get(url)
>>> tweets = json.loads(response.content)
>>> print len(tweets['statuses'])
100

Para obtermos os próximos 100 tweets, precisamos descobrir o id do tweet mais antigo retornado na última resposta:

>>> oldest = min( for tweet in tweets['statuses']])-1

Vamos passar esse valor na próxima requisição em um parâmetro chamado max_id, que indica ao serviço o id do tweet mais recente que queremos na requisição. Ou seja, iremos pegar agora os 100 tweets seguintes aos 100 que já obtivemos anteriormente. Para isso, basta:

>>> url = 'https://api.twitter.com/1.1/search/tweets.json?q=python&count=100&max_id='
>>> response = session.get(url + str(oldest))
>>> tweets = json.loads(response.content)
>>> print len(tweets['statuses'])
100

E assim, sucessivamente. Para obter os próximos 100 tweets, buscaríamos novamente o tweet de menor id do conjunto de resultados e passaríamos o mesmo como max_id da próxima requisição.

O campo next_results

Para facilitar a vida do desenvolvedor, o serviço já retorna um campo next_results dentro do campo search_metadata no resultado de uma requisição. Esse campo já contém a parte da URL relativa aos parâmetros prontinha, com o max_id corretamente configurado para pegarmos os próximos resultados. Veja um exemplo:

>>> response = session.get('https://api.twitter.com/1.1/search/tweets.json?q=brazil&count=100')
>>> tweets = json.loads(response.content)
>>> print tweets['search_metadata']['next_results']
?max_id=508446478730551295&q=python&count=100&include_entities=1

O valor de max_id é o mesmo que obteríamos pegando o menor id da requisição anterior e subtraindo 1. Agora, podemos pegar os próximos 100 resultados usando next_results:

>>> url = 'https://api.twitter.com/1.1/search/tweets.json'
>>> response = session.get(url + tweets['search_metadata']['next_results'])
>>> tweets = json.loads(response.content)
>>> print len(tweets['statuses'])
100

Obtendo os trending topics

Outra possibilidade (dentre muitas) é obter os trending topics de determinada região através do recurso trends. Sua utilização é muito simples, bastando passar à URL https://api.twitter.com/1.1/trends/place.json um identificador indicando o local de interesse. Esse identificador deve ser do tipo WOEID (Where On Earth IDentifier). Nesse esquema de representação, o id 1 representa o mundo inteiro, enquanto que o Brasil é representado como 23424768. Abaixo, obtemos os 10 primeiros trending topics do mundo todo:

>>> response = session.get("https://api.twitter.com/1.1/trends/place.json?id=1")
>>> worlds = json.loads(response.content)[0]["trends"]
>>> for trend in worlds:
        print trend["name"]

E também do Brasil:

>>> response = session.get("https://api.twitter.com/1.1/trends/place.json?id=23424768")
>>> brazils = json.loads(response.content)[0]["trends"]
>>> for trend in brazils:
        print trend["name"]

Agora que temos acesso aos dados, poderíamos começar a brincar com eles. Por exemplo, obter a lista de tópicos que estão no topo tanto no mundo quanto no Brasil:

>>> set([t['name'] for t in worlds]).intersection([t['name'] for t in brazils])

Mas é meio chato ter que ficar fazendo chamadas HTTP a cada vez que queremos obter dados do Twitter em nosso código. Que tal escrevermos uma classe com alguns métodos para nos auxiliar?

Uma classe para acesso ao Twitter

Vamos agora criar uma classe Python que implemente algumas tarefas pré-definidas pra nós, como fazer uma busca por palavras-chave.

import json
from requests_oauthlib import OAuth1Session

MAX_TWEETS = 100
BASE_URL = "https://api.twitter.com/1.1/search/tweets.json"

class MyTwitterSearchClient(object):
    # preencha com os dados do seu app
    API_KEY = "sua API KEY"
    API_SECRET = "sua API SECRET"
    ACCESS_TOKEN = "SEU ACCESS TOKEN"
    ACCESS_TOKEN_SECRET = "SEU ACCESS TOKEN SECRET"
    
    
    def __init__(self):
        self.session = OAuth1Session(self.API_KEY,
                                     self.API_SECRET,
                                     self.ACCESS_TOKEN,
                                     self.ACCESS_TOKEN_SECRET)
    
    
    def get_tweets(self, keyword, n=15, max_id=None):
        if n > 0:
            url = BASE_URL + ("?q=%s&count=%d" % (keyword, n))
            if max_id is not None:
                url = url + "&max_id=%d" % (max_id)
            response = self.session.get(url)
            if response.status_code == 200:
                tweets = json.loads(response.content)
                oldest_id = min( for tweet in tweets['statuses']])-1
                return tweets['statuses'] + \
					self.get_tweets(keyword, n-MAX_TWEETS, oldest_id)
        return []

Agora ficou mais fácil de buscar as informações que desejamos. Para obter os últimos 500 tweets contendo a palavra "python", basta fazer:

>>> client = MyTwitterSearchClient()
>>> tweets = client.get_tweets("python", 500):

Assim como criamos uma classezinha para facilitar a nossa vida, existem alguns wrappers para a API REST do Twitter. Usando eles, não é preciso fazer requisições HTTP explicitamente. Basta invocar métodos em objetos Python para obter os dados desejados. Se quiser conhecer essas ferramentas, siga os links abaixo:

Web Scraping com Scrapy – primeiros passos

Imagine que você queira extrair conteúdo da Web que não esteja em apenas uma página só: você precisa de uma maneira de “navegar” no site para as páginas que realmente contém as informações úteis. Por exemplo, você pode estar interessado nas notícias destaques do dia no Portal Brasil.gov.br, mas somente aquelas das seções “Infraestrutura” e “Ciência e Tecnologia”.

webpage-brasil-links

Bem, há uns tempos atrás, já mostramos aqui no blog como usar a biblioteca requests para acessar páginas disponíveis na Web usando nossa linguagem predileta. Também mostramos como usar a biblioteca BeautifulSoup para facilitar a extração do conteúdo útil da página, o que chamamos de Web Scraping. Hoje, vamos mostrar como usar o framework Scrapy, que contém todas essas funcionalidades e muitas outras mais, de maneira que agiliza bastante resolver problemas como esse da introdução. Tudo em Python, lógico! =)

Vale notar então, que o Scrapy busca resolver não só a extração de conteúdo das páginas (scraping), mas também a navegação para as páginas relevantes para a extração (crawling). Para isso, uma ideia central no framework é o conceito de Spider — na prática, objetos Python com algumas características especiais que você escreve o código e o framework aciona.

Só para você ter uma ideia de como se parece, dê uma olhada no código de um programa que usa Scrapy para extrair informações (link, título e visualizações) de um canal do YouTube abaixo. Não se preocupe em entender esse código ainda, estamos mostrando aqui só para você ter um feeling do código com Scrapy. Ao terminar esse tutorial, você será capaz de entender e escrever programas como esse. =)

import scrapy
from scrapy.contrib.loader import ItemLoader

class YoutubeVideo(scrapy.Item):
    link = scrapy.Field()
    title = scrapy.Field()
    views = scrapy.Field()

class YoutubeChannelLister(scrapy.Spider):
    name = 'youtube-channel-lister'
    youtube_channel = 'LongboardUK'
    start_urls = ['https://www.youtube.com/user/%s/videos' % youtube_channel]

    def parse(self, response):
        for sel in response.css("ul#channels-browse-content-grid > li"):
            loader = ItemLoader(YoutubeVideo(), selector=sel)

            loader.add_xpath('link', './/h3/a/@href')
            loader.add_xpath('title', './/h3/a/text()')
            loader.add_xpath('views', ".//ul/li[1]/text()")

            yield loader.load_item()

Mas antes de começarmos a falar mais sobre o Scrapy, certifique-se de tê-lo instalado em sua última versão (dependendo do caso, você pode precisar usar o comando sudo ou a opção –user para o pip install):

pip install --upgrade scrapy

Nota: dependendo do seu ambiente Python, a instalação pode ser um pouco enrolada por causa da dependência do Twisted. Se você usa Windows, confira as instruções específicas no guia de instalação oficial. Se você usa uma distribuição Linux baseada em Debian, pode querer usar o repositório APT oficial do Scrapy. Se você está usando o pip no Ubuntu, pode precisar instalar os pacotes libffi-dev, libssl-dev, libxml2-dev e libxslt1-dev antes.

Para seguir este tutorial, você precisará do Scrapy com número de versão 0.24 para cima. Você pode verificar a versão do Scrapy instalada com o comando:

python -c 'import scrapy; print(&quot;%s.%s.%s&quot; % scrapy.version_info)'

A saída desse comando no ambiente que usamos para esse tutorial está assim:

$ python -c 'import scrapy; print(&quot;%s.%s.%s&quot; % scrapy.version_info)'
0.24.2

A anatomia de uma aranha

spider_anatomy

Um Scrapy spider é responsável por definir como seguir os links “navegando” por um site (o que chamamos de crawling) e como extrair as informações das páginas em estruturas de dados Python. 

Para definir um spider mínimo, crie uma classe estendendo scrapy.Spider e dê um nome ao spider usando o atributo name:

import scrapy

class MinimalSpider(scrapy.Spider):
    &quot;&quot;&quot;A menor Scrapy-Aranha do mundo!&quot;&quot;&quot;
    name = 'minimal'

Coloque isso em um arquivo com o nome minimal.py e rode o seu spider para conferir se está tudo certo, usando o seguinte comando:

scrapy runspider minimal.py

Caso estiver tudo certo, você verá na tela algumas mensagens do log marcadas como INFO e DEBUG. Caso houver alguma mensagem marcada com ERROR, significa que deu algo errado e você precisa conferir se tem algum erro no código do spider.

A vida de um spider começa com a geração de requisições HTTP (objetos do tipo Request) para o motor do framework acionar. A parte do spider responsável por isso é o método start_requests(), que retorna um iterable contendo as primeiras requisições a serem feitas para o spider.

Adicionando esse elemento ao nosso spider mínimo, ficamos com:

import scrapy

class MinimalSpider(scrapy.Spider):
    &quot;&quot;&quot;A menor Scrapy-Aranha do mundo!&quot;&quot;&quot;
    name = 'minimal'

    def start_requests(self):
        return [scrapy.Request(url)
                for url in ['http://www.google.com', 'http://www.yahoo.com']]

O método start_requests() deve retornar um iterable de objetos scrapy.Request, que representam uma requisição HTTP a ser acionada pelo framework (incluindo URL, parâmetros, cookies, etc) e definem uma função a ser chamada para quando a requisição completar — uma função callback. 

Nota: Caso esteja familiarizado com implementar AJAX com JavaScript, essa maneira de trabalhar disparando requisições e registrando callbacks pode soar familiar.

No nosso exemplo, retornamos uma lista de requisições simples para o site do Google e do Yahoo, mas o método start_requests() também poderia ser implementado como um Python generator.

Se você tentou executar o exemplo como está agora, pode ter notado que ainda está faltando coisa, o Scrapy irá cuspir duas mensagens marcadas como ERROR, reclamando que um método não foi implementado:

....
  File &quot;/home/elias/.virtualenvs/scrapy/local/lib/python2.7/site-packages/scrapy/spider.py&quot;, line 56, in parse
    raise NotImplementedError
exceptions.NotImplementedError:

Isso ocorre porque, como não registramos nenhuma função callback para os objetos Request, o Scrapy tentou chamar o callback padrão, que é o método parse() do objeto Spider. Vamos adicionar esse método ao nosso spider mínimo, para podemos executar o spider:

import scrapy

class MinimalSpider(scrapy.Spider):
    &quot;&quot;&quot;A menor Scrapy-Aranha do mundo!&quot;&quot;&quot;
    name = 'minimal'

    def start_requests(self):
        return (scrapy.Request(url)
                for url in ['http://www.google.com', 'http://www.yahoo.com'])

    def parse(self, response):
        self.log('ACESSANDO URL: %s' % response.url)

Se você executar novamente agora o spider com o comando: scrapy runspider minimal.py deverá observar na saída algo semelhante a:

2014-07-26 15:39:56-0300 [minimal] DEBUG: Crawled (200) &lt;GET http://www.google.com.br/?gfe_rd=cr&amp;ei=_PXTU8f6N4mc8Aas1YDABA&gt; (referer: None)
2014-07-26 15:39:56-0300 [minimal] DEBUG: ACESSANDO URL: http://www.google.com.br/?gfe_rd=cr&amp;ei=_PXTU8f6N4mc8Aas1YDABA
2014-07-26 15:39:57-0300 [minimal] DEBUG: Redirecting (302) to &lt;GET https://br.yahoo.com/?p=us&gt; from &lt;GET https://www.yahoo.com/&gt;
2014-07-26 15:39:58-0300 [minimal] DEBUG: Crawled (200) &lt;GET https://br.yahoo.com/?p=us&gt; (referer: None)
2014-07-26 15:39:58-0300 [minimal] DEBUG: ACESSANDO URL: https://br.yahoo.com/?p=us

Para deixar o código do nosso spider ainda mais enxuto, podemos nos aproveitar do funcionamento padrão do método start_requests(): caso você não o defina, o Scrapy irá criar requisições para uma lista de URLs num atributo com o nome start_urls — exatamente o que estamos fazendo. Portanto, podemos reduzir o código acima e manter o mesmo funcionamento, usando:

import scrapy

class MinimalSpider(scrapy.Spider):
    &quot;&quot;&quot;A menor Scrapy-Aranha do mundo!&quot;&quot;&quot;
    name = 'minimal'
    start_urls = [
        'http://www.google.com',
        'http://www.yahoo.com',
    ]

    def parse(self, response):
        self.log('ACESSANDO URL: %s' % response.url)

Como no método parse() mostrado acima, todos os callbacks recebem o conteúdo da resposta da requisição HTTP como argumento (em um objeto Response). É dentro do callback, onde já temos o conteúdo das páginas que nos interessam, que fazemos a extração das informações, ou seja, o data scraping propriamente dito.

excited-scrapy

Callbacks, Requests & Items

As funções registradas como callback associadas às requisições podem retornar um iterable de objetos, em que cada objeto pode ser:

  • um objeto de uma classe scrapy.Item que você define para conter os dados coletados da página
  • um objeto da classe scrapy.Request representando ainda outra requisição a ser acionada (possivelmente registrando outro callback)

Com esse esquema de requisições e callbacks que podem gerar novas requisições (com novos callbacks), você pode programar a navegação por um site gerando requisições para os links a serem seguidos, até chegar nas páginas com os itens que nos interessam. Por exemplo, para um spider que precise extrair produtos de um site de compras navegando em páginas por categorias, você poderia usar uma estrutura como a seguinte:

import scrapy

class SkeletonSpider(scrapy.Spider):
    name = 'spider-mummy'
    start_urls = ['http://www.someonlinewebstore.com']

    def parse(self, response):
        for c in [...]:
            url_category = ...
            yield scrapy.Request(url_category, self.parse_category_page)

    def parse_category_page(self, response):
        for p in [...]:
            url_product = ...
            yield scrapy.Request(url_product, self.parse_product)

    def parse_product(self, response):
        ...

Na estrutura acima, o callback padrão — método parse() — trata a resposta da primeira requisição ao site da loja e gera novas requisições para as páginas das categorias, registrando outro callback para tratá-las — o método parse_category_page(). Este último faz algo parecido, gerando as requisições para as páginas dos produtos, desta vez registrando um callback que extrai os objetos itens com os dados do produto.

Por que eu preciso definir classes para os itens?

O Scrapy propõe que você crie algumas classes que representem os itens que você pretende extrair das páginas. Por exemplo, se você deseja extrair os preços e detalhes de produtos de uma loja virtual, poderia representar uma classe como a seguinte:

import scrapy

class Produto(scrapy.Item):
    descricao = scrapy.Field()
    preco = scrapy.Field()
    marca = scrapy.Field()
    categoria = scrapy.Field()

Como pode ver, são simples subclasses de scrapy.Item, em que você adiciona os campos desejados (objetos da classe scrapy.Field). Você pode usar uma instância dessa classe como se fosse um dicionário Python:

&gt;&gt;&gt; p = Produto()
&gt;&gt;&gt; p['preco'] = 13
&gt;&gt;&gt; print p
{'preco': 13}

A maior diferença para um dicionário tradicional é que um Item, por padrão, não permite você atribuir um valor para uma chave que não foi declarada como campo:

&gt;&gt;&gt; p['botemo'] = 54
...
KeyError: 'Produto does not support field: botemo'

A vantagem de definir classes para os itens é que isso permite você aproveitar outros recursos do framework que funcionam para essas classes. Por exemplo, o recurso de exportação de dados possibilita escolher entre exportar os itens coletados para JSON, CSV, XML, etc. Ou ainda, o esquema de pipeline de itens, que permite você plugar outros processamentos em cima dos itens coletados (coisas tipo, validar o conteúdo, remover itens duplicados, armazenar no banco de dados, etc).

Let’s do some scraping!

Para fazer o scraping propriamente dito, isto é, a extração dos dados da página, é legal você conhecer XPath, uma linguagem feita para fazer consultas em conteúdo XML — base do mecanismo de seletores do framework. Caso não conheça XPath você pode usar seletores CSS no Scrapy, mas encorajamos você a conhecer XPath mais de perto, pois ela permite expressões mais poderosas do que CSS (de fato, as funções de CSS no Scrapy funcionam convertendo os seletores CSS para expressões com XPath).

Você pode testar o resultado de expressões XPath ou CSS para uma página usando o Scrapy shell. Rode o comando:

scrapy shell http://pt.stackoverflow.com

Esse comando dispara uma requisição para a URL informada e abre um shell Python (ou IPython, caso o tenha instalado) disponibilizando alguns objetos para você explorar. O objeto mais importante é o response, que contém a resposta da requisição HTTP e equivale ao argumento response recebido pelas funções de callback.

dog-excited-tem_ate_um_shell

&gt;&gt;&gt; response.url
'http://pt.stackoverflow.com'
&gt;&gt;&gt; response.headers
{'Cache-Control': 'public, no-cache=&quot;Set-Cookie&quot;, max-age=60',
 'Content-Type': 'text/html; charset=utf-8',
 'Date': 'Fri, 01 Aug 2014 02:27:12 GMT',
 'Expires': 'Fri, 01 Aug 2014 02:28:12 GMT',
 'Last-Modified': 'Fri, 01 Aug 2014 02:27:12 GMT',
 'Set-Cookie': 'prov=cf983b7c-a352-4713-9aa8-6deb6e262b01; domain=.stackoverflow.com; expires=Fri, 01-Jan-2055 00:00:00 GMT; path=/; HttpOnly',
 'Vary': '*',
 'X-Frame-Options': 'SAMEORIGIN'}

Você pode usar os métodos xpath() e css() do objeto response para executar uma busca no conteúdo HTML da resposta:

&gt;&gt;&gt; response.xpath(&amp;amp;amp;quot;//title&amp;amp;amp;quot;) # obtem o elemento &amp;amp;amp;lt;title&amp;amp;amp;gt; usando XPath
[&lt;Selector xpath='//title' data=u'&lt;title&gt;Stack Overflow em Portugu\xeas&lt;/titl'&gt;]
&gt;&gt;&gt; response.css('title') # obtem o elemento &lt;title&gt; com seletor CSS
[&lt;Selector xpath=u'descendant-or-self::title' data=u'&lt;title&gt;Stack Overflow em Portugu\xeas&lt;/titl'&gt;]
&gt;&gt;&gt; len(response.css('div')) # conta numero de elementos &lt;div&gt;
252

O resultado de chamar um desses métodos é um objeto lista que contém os objetos seletores resultantes da busca e possui um método extract() que extrai o conteúdo HTML desses seletores. Os objetos seletores contidos nessa lista, por sua vez, além de possuírem o método extract() para extrair o conteúdo dele, também possuem métodos xpath() e css() que você pode usar fazer uma nova busca no escopo de cada seletor.

Veja os exemplos abaixo ainda no mesmo Scrapy shell, que ajudam a esclarecer as coisas.

Extrai conteúdo HTML do elemento <title>, acionando método extract() da lista de seletores (repare como o resultado é uma lista Python):

&gt;&gt;&gt; response.xpath(&quot;//title&quot;).extract()
[u'&lt;title&gt;Stack Overflow em Portugu\xeas&lt;/title&gt;']

Guarda o primeiro seletor do resultado numa variável, e aciona o método extract() do seletor (veja como agora o resultado é uma string):

&gt;&gt;&gt; title_sel = response.xpath('//title')[0]
&gt;&gt;&gt; title_sel.extract()
u'&lt;title&gt;Stack Overflow em Portugu\xeas&lt;/title&gt;'

Aplica a expressão XPath text() para obter o conteúdo texto do seletor, e usa o método extract() da lista resultante:

&gt;&gt;&gt; title_sel.xpath('text()').extract()
[u'Stack Overflow em Portugu\xeas']

Imprime a extração do primeiro seletor resultante da expressão XPath text() aplicada no seletor da variável title_sel:

&gt;&gt;&gt; print title_sel.xpath('text()')[0].extract()
Stack Overflow em Português

Bem, dominando essa maneira de trabalhar com seletores, a maneira simples de extrair um item é simplesmente instanciar a classe Item desejada e preencher os valores obtidos usando essa API de seletores.

Veja abaixo o código de um spider usando essa técnica para obter as perguntas mais frequentes do StackOverflow brazuca:

import scrapy
import urlparse

class Question(scrapy.Item):
    link = scrapy.Field()
    title = scrapy.Field()
    excerpt = scrapy.Field()
    tags = scrapy.Field()

class StackoverflowTopQuestionsSpider(scrapy.Spider):
    name = 'so-top-questions'

    def __init__(self, tag=None):
        questions_url = 'http://pt.stackoverflow.com/questions'
        if tag:
            questions_url += '/tagged/%s' % tag

        self.start_urls = [questions_url + '?sort=frequent']

    def parse(self, response):
        build_full_url = lambda link: urlparse.urljoin(response.url, link)

        for qsel in response.css(&quot;#questions &gt; div&quot;):
            it = Question()

            it['link'] = build_full_url(
                qsel.css('.summary h3 &gt; a').xpath('@href')[0].extract())
            it['title'] = qsel.css('.summary h3 &amp;amp;amp;gt; a::text')[0].extract()
            it['tags'] = qsel.css('a.post-tag::text').extract()
            it['excerpt'] = qsel.css('div.excerpt::text')[0].extract()

            yield it

Como você pode ver, o spider declara uma classe Item com o nome Question, e usa a API de seletores CSS e XPath para iterar sobre os elementos HTML das perguntas (obtidos com o seletor CSS #questions > div), gerando um objeto Question para cada com os campos preenchidos (link, título, tags e trecho da pergunta).

Duas coisas são interessantes que você note na extração feita no callback parse(): a primeira é que usamos um pseudo-seletor CSS ::text para obter o conteúdo texto dos elementos, evitando as tags HTML. A segunda é como usamos a função urlparse.urljoin() combinando a URL da requisição com conteúdo do atributo href para ter certeza que o resultado seja uma URL absoluta.

Coloque esse código em um arquivo com o nome top_asked_so_questions.py e execute-o usando o comando:

scrapy runspider top_asked_so_questions.py -t json -o perguntas.json

Se tudo deu certo, o Scrapy vai mostrar na tela os itens que extraiu e também escrever um arquivo perguntas.json contendo os mesmos itens. No fim da saída, devem aparecer algumas estatísticas da execução, incluindo a contagem dos itens extraídos:

2014-08-02 14:27:37-0300 [so-top-questions] INFO: Dumping Scrapy stats:
	{'downloader/request_bytes': 242,
	 'downloader/request_count': 1,
	 ...
	 'item_scraped_count': 50,
	 'log_count/DEBUG': 53,
	 'log_count/INFO': 8,
	 ...
	 'start_time': datetime.datetime(2014, 8, 2, 17, 27, 36, 912002)}
2014-08-02 14:27:37-0300 [so-top-questions] INFO: Spider closed (finished)

question_block_little_dudes-are_belong_to_us

Argumentos aracnídeos

Talvez você notou que a classe do spider tem um construtor aceitando um argumento tag opcional. Podemos passar esse argumento para o spider para obter as perguntas frequentes com a tag python, usando a opção -a:

scrapy runspider top_asked_so_questions.py -t json -o perguntas.json -a tag=python

Usando esse truque você pode fazer spiders mais genéricos, que você passe alguns parâmetros e obtém um resultado diferente. Por exemplo, você poderia fazer um spider para sites que possuam a mesma estrutura HTML, parametrizando a URL do site. Ou ainda, um spider para um blog em que os parâmetros definam um período desejado para extrair posts e comentários.

Juntando tudo

Nas seções anteriores, você viu como fazer crawling com o Scrapy, navegando entre as páginas de um site usando o mecanismo de “navegação” criando requisições com funções callback. Viu também como usar a API de seletores para extrair o conteúdo da página em itens e executar o spider usando o comando scrapy runspider.

Agora, vamos juntar tudo isso em um spider que resolve o problema que apresentamos na introdução: vamos fazer scraping das notícias destaques do Portal Brasil, oferecendo uma opção para informar o assunto (Infraestrutura, Educação, Esporte, etc). Dessa forma, se apenas executar o spider, ele deve fazer scraping das notícias destaques na página inicial; caso informe um assunto, ele deve fazer scraping dos destaques da página daquele assunto.

Nota: Antes de começar a escrever um spider, é útil explorar um pouco as páginas do site usando o navegador e a ferramenta scrapy shell, assim você pode ver como o site é organizado e testar alguns seletores CSS ou XPath no shell. Existem também extensões para os browsers que permitem você testar expressões XPath em uma página: XPath Helper para o Chrome e XPath Checker para o Firefox. Descobrir a melhor maneira de extrair o conteúdo de um site com XPath ou CSS é mais uma arte do que uma ciência, e por isso não tentaremos explicar aqui, mas vale dizer que você aprende bastante com a experiência.

Veja como fica o código do spider:

import scrapy
import urlparse

class Noticia(scrapy.Item):
    titulo = scrapy.Field()
    conteudo = scrapy.Field()
    link = scrapy.Field()
    data_publicacao = scrapy.Field()

class PortalBrasilDestaques(scrapy.Spider):
    name = 'portal-brasil'

    def __init__(self, assunto=None):
        main_url = 'http://www.brasil.gov.br'
        if assunto:
            self.start_urls = ['%s/%s' % (main_url, assunto)]
        else:
            self.start_urls = [main_url]

    def parse(self, response):
        &quot;&quot;&quot;Recebe a pagina com as noticias destaques, encontra os links
        das noticias e gera requisicoes para a pagina de cada uma
        &quot;&quot;&quot;
        links_noticias = response.xpath(
            &quot;//div/h1/a/@href&quot;
            &quot; | //div/h3/a/@href[not(contains(.,'conteudos-externos'))]&quot;
        ).extract()

        for link in links_noticias:
            url_noticia = urlparse.urljoin(response.url, link)
            yield scrapy.Request(url_noticia, self.extrai_noticia)

    def extrai_noticia(self, response):
        &quot;&quot;&quot;Recebe a resposta da pagina da noticia,
        e extrai um item com a noticia
        &quot;&quot;&quot;
        noticia = Noticia()

        noticia['link'] = response.url
        noticia['titulo'] = response.xpath(&amp;amp;amp;quot;//article/h1/text()&amp;amp;amp;quot;)[0].extract()
        noticia['conteudo'] = response.xpath(
            &quot;string(//div[@property='rnews:articleBody'])&quot;)[0].extract()
        noticia['data_publicacao'] = ''.join(
            response.css('span.documentPublished::text').extract()).strip()

        yield noticia

Da mesma forma como antes, você pode rodar o spider com:

scrapy runspider portal_brasil_destaques.py -t json -o destaques-capa.json

E para obter os destaques de cada seção, pode usar comandos como:

scrapy runspider portal_brasil_destaques.py -t json -o destaques-infraestrutura.json -a assunto=infraestrutura
scrapy runspider portal_brasil_destaques.py -t json -o destaques-ciencia-e-tecnologia.json -a assunto=ciencia-e-tecnologia

O código desse spider é bem semelhante ao anterior na sua estrutura, com o suporte a argumentos no construtor.

A principal diferença é que neste, o primeiro callback (método parse()) gera outras requisições para as páginas das notícias, que são tratadas pelo segundo callback: o método extrai_noticia(), que faz a extração do conteúdo da notícia propriamente dita.

A extração de conteúdo nesse último spider também está um pouco mais complexa, considerando a expressão XPath usada para obter os links das notícias, que filtra os links que contenham a string ‘conteudos-externos’ em seu endereço, pois não são links de notícias. Note como aproveitamos que Python concatena strings literais para quebrar a expressão XPath em duas linhas.

Conclusão

Se você chegou até aqui, parabéns! Aqui vai um troféu pra você:

trofeu-scrapy

Agora que você já aprendeu a escrever spiders Scrapy e está habilitado a baixar a Internet inteira no seu computador, tente não ser banido nos sites por aí! :D

Visite a documentação oficial do Scrapy, tem bastante coisa legal lá, desde um tutorial ensinando a criar projetos Scrapy completos, perguntas frequentes, dicas para crawlings grandes, como depurar um spider, dicas para evitar ser banido e muito mais.

 

Links úteis:

Obrigado pela revisão, Valdir e Zé!

Acessando APIs REST com Python

Um serviço web (web service) é um mecanismo utilizado para comunicação entre dois ou mais programas através da infraestrutura da internet. Apesar do que o nome pode sugerir, um serviço web não oferece funcionalidades diretamente para o usuário final, mas sim para outros programas que precisam de sua ajuda para realizar alguma tarefa, seja para computar algo ou para fornecer dados úteis.

Você conhece o serviço de busca de endereços postais por CEP? O site dos correios fornece aos cidadãos um serviço que permite que estes façam consultas à base de dados de endereços através de uma página web. Esse não é um exemplo de web service, pois tem como foco servir diretamente ao usuário final. Um web service equivalente poderia ser um serviço oferecido pelos próprios correios para que outros programas, como por exemplo o software de alguma loja virtual, possam verificar qual é o endereço do CEP preenchido pelo usuário. Nesse caso, o software faz uma requisição ao web service, aguarda a resposta, decodifica a mesma e então inclui a resposta obtida na página mostrada ao usuário final.

Um web service pode ser fornecido de várias maneiras. Entretanto, foram definidos alguns padrões para facilitar a interoperabilidade entre programas de diferentes origens, sendo REST e SOAP os mais conhecidos. Este post irá mostrar como utilizar APIs web baseadas no padrão REST.

APIs REST

Uma API (application programming interface) é uma especificação que define como componentes de software devem interagir entre si (thanks, wikipedia!). APIs REST se utilizam do protocolo HTTP para fornecer determinadas funcionalidades aos seus clientes. Essas funcionalidades são descritas por conjuntos de recursos que podem ser acessados remotamente pelos clientes do serviço, através de requisições HTTP comuns.

Em uma API REST existem dois conceitos principais: os recursos (resources) e as coleções (collections). Um recurso é uma unidade que representa um objeto (composto por dados, relacionamentos com outros recursos e métodos). Já uma coleção é um conjunto de recursos que pode ser obtido acessando uma URL. Tal coleção poderia representar a coleção de todos os registros de determinado tipo, ou então, todos os registros que possuem relacionamento com determinado objeto, ou todos os registros que atendem à determinada condição, etc.

A API do twitter, por exemplo, fornece acesso a alguns recursos como os tweets enviados pelos usuários. Com ela, nossa aplicação pode enviar uma requisição HTTP ao twitter solicitando os últimos tweets de um determinado usuário ou até mesmo postar uma mensagem em nome do usuário autenticado.

Por exemplo, para obter uma lista com os últimos 10 tweets postados por mim, basta enviar uma requisição HTTP do tipo GET ao endereço https://api.twitter.com/1.1/statuses/user_timeline.json?screen_name=stummjr&count=10. Para que isso funcione, porém, é preciso de autenticação utilizando o mecanismo descrito na documentação da API.

Outro exemplo, com a API do próprio twitter, é o serviço de busca de tweets. Se quisermos buscar os últimos 20 tweets que contenham a hashtag #python, podemos enviar uma requisição à URL: https://api.twitter.com/1.1/search/tweets.json?q=#python&count=20. Como resposta às requisições, receberemos coleções de dados estruturados em formato JSON. A resposta dada por uma chamada a uma API REST normalmente é composta por dados em algum formato estruturado, como JSON ou XML. Esses formatos permitem a interoperabilidade entre plataformas e linguagens diferentes, pois o conteúdo é nada mais do que texto puro codificado com algum esquema de caracteres.

Muitos sites famosos (como twitter, facebook, reddit, etc) fornecem APIs REST para que terceiros possam escrever aplicativos que utilizem os dados armazenados nesses sites. Com essas APIs, fica fácil criar programas que interajam com redes sociais, lendo e postando dados para as mesmas.

Como você pôde ver, uma API REST nada mais é do que uma API que fornece acesso remoto a recursos via HTTP. Para podermos entender melhor e fazer requisições HTTP a um serviço REST, precisamos conhecer um pouquinho mais sobre o protocolo HTTP e como seus métodos são utilizados em uma API REST.

HTTP e seus métodos

O protocolo HTTP define que uma requisição de um cliente para um servidor é composta por:

  1. Uma linha descrevendo a requisição, composta por:
    1. Método: indica o que desejamos fazer com o recurso. Pode ser: GET, POST, PUT, DELETE, além de outros menos utilizados.
    2. URL: o endereço do recurso que se deseja acessar.
    3. Versão: a versão do protocolo a ser usada (1.1, atualmente).
  2. O corpo da requisição, que pode conter informações como o nome do host de onde desejamos obter o recurso solicitado, dados a serem enviados do cliente para o servidor, etc.

O exemplo abaixo mostra uma requisição HTTP do tipo GET para um recurso na web:

GET /r/programming/.json HTTP/1.1
Host: http://www.reddit.com

O método de uma requisição HTTP indica a ação que pretendemos realizar com aquela requisição, e cada método tem um significado próprio:

  • GET: utilizado para a obtenção de dados. É o tipo de requisição que o navegador faz a um servidor quando você digita uma URL ou clica em um link.
  • POST: utilizada na web para o envio de dados do navegador para o servidor, principalmente quando esses dados vão gerar alguma alteração no último. É o tipo de requisição que o navegador faz a um servidor quando você preenche um formulário na web e clica em “Enviar” (embora existam formulários na web que utilizem outros tipos de requisição, como GET).
  • PUT: serve para solicitar a criação de objetos no servidor caso esses ainda não existirem. Na prática, a maioria das páginas utiliza o método POST para isso também.
  • DELETE: serve para indicar que o usuário (emissor da requisição em questão) deseja apagar determinado recurso do servidor.

Após executar a requisição do cliente, o serviço responde com uma mensagem de resposta HTTP. O protocolo HTTP define que as mensagens de resposta devem possuir um campo indicando o status da requisição. O status mais conhecido na web é o 404 (not found – recurso não encontrado), mas existem vários, como: 200 (OK), 401 (not authorized – indicando falta de autenticação), 500 (internal server error – erro no servidor), dentre outros. Por ser baseado em HTTP, o padrão REST define que as mensagens de resposta devem conter um código de status, para que o cliente do serviço web possa verificar o que aconteceu com a sua requisição.

A seguir veremos como emitir requisições HTTP “programaticamente” em Python, acessando uma API REST disponível na web.

Acessando uma API REST

Para entender melhor, vamos utilizar como exemplo a API REST JSONPlaceHolder, disponível em jsonplaceholder.typicode.com, que é uma API fake criada para ser usada por quem estiver usando REST em seu programa e precisando de dados falsos (dummy data) para testes.

O JSONPlaceHolder disponibiliza acesso a alguns recursos, como: posts, comments, albums, photos, todos e users. Cada um dos recursos está disponível em uma URL específica:

Em nosso exemplo, vamos usar somente o recurso comments, mas o exemplo será válido para qualquer um dos recursos acima.

Como já foi mencionado anteriormente, as APIs REST fornecem suas funcionalidades através dos métodos existentes no protocolo HTTP (GET, POST, PUT e DELETE). Por exemplo, para listar todos os comments existentes, basta enviar uma requisição HTTP do tipo GET à URL http://jsonplaceholder.typicode.com/comments. Para listar algum registro comment em específico, basta enviar um GET à mesma URL, passando como parâmetro o id do comment que queremos obter: http://jsonplaceholder.typicode.com/comments/1. Uma requisição HTTP usando o método DELETE à URL http://jsonplaceholder.typicode.com/comments/1 irá remover o objeto comment em questão. Também é possível alterar um objeto através do método HTTP PUT ou incluir um novo objeto com o método POST.

Podemos resumir a semântica dos métodos HTTP em uma API REST da seguinte forma:

  • GET: obtenção de dados (seja um conjunto de objetos ou um em específico).
  • POST: criação de dados.
  • PUT: alteração de dados existentes.
  • DELETE: remoção de dados.

Obviamente, as APIs REST utilizam mecanismos de autenticação para evitar que alguém altere ou acesse dados de forma indevida.

Mãos na massa

Atenção: esta seção supõe que você tem uma certa familiaridade com JSON. Caso não conheça o formato, veja aqui um post anterior sobre o assunto.

Agora que já temos uma ideia sobre como uma API REST funciona, vamos ver na prática como nosso programa poderia utilizar uma API desse tipo para obtenção e manipulação de dados externos. Para fazer as requisições HTTP ao serviço, vamos utilizar a biblioteca requests (instalável via pip install requests) e para manipular o JSON retornado pelo serviço, vamos usar a biblioteca json (inclusa na biblioteca padrão).

Primeiramente, vamos importar as bibliotecas necessárias:

>>> import json, requests

Obtendo dados

Vamos começar testando a leitura de registros usando o método HTTP GET, que está disponível na requests através do método get().

>>> response = requests.get("http://jsonplaceholder.typicode.com/comments")
>>> print response.status_code
200
>>> print response.content
   [
    {
    "postId": 1,
    "id": 1,
    "name": "id labore ex et quam laborum",
    "email": "Eliseo@gardner.biz",
    "body": "laudantium enim quasi est quidem magnam voluptate ipsam eos\ntempora quo necessitatibus\ndolor quam autem     quasi\nreiciendis et nam sapiente accusantium"
    },
    {
    "postId": 1,
    "id": 2,
    "name": "quo vero reiciendis velit similique earum",
    "email": "Jayne_Kuhic@sydney.com",
    "body": "est natus enim nihil est dolore omnis voluptatem numquam\net omnis occaecati quod ullam at\nvoluptatem error expedita pariatur\nnihil sint nostrum voluptatem reiciendis et"
    }
    ...
    ,
    {
    "postId": 100,
    "id": 500,
    "name": "ex eaque eum natus",
    "email": "Emma@joanny.ca",
    "body": "perspiciatis quis doloremque\nveniam nisi eos velit sed\nid totam inventore voluptatem laborum et eveniet\naut aut aut maxime quia temporibus ut omnis"
    }
   ]

Agora que vimos que nossa requisição HTTP foi executada com sucesso (código 200) e que a string retornada como resposta está em formato JSON, vamos empacotar o resultado em um objeto Python para que possamos manipular os dados com maior facilidade:

>>> comments = json.loads(response.content)

A função json.loads() transformou a string JSON em um objeto Python de tipo correspondente, em nosso caso, um objeto list contendo vários dict dentro, onde cada dict representará um dos registros existentes no servidor.

>>> print comments[0]
    {u'body': u'laudantium enim quasi est quidem magnam voluptate ipsam eos\ntempora quo necessitatibus\ndolor quam autem quasi\nreiciendis et nam sapiente accusantium', u'email': u'Eliseo@gardner.biz', u'postId': 1, u'id': 1, u'name': u'id labore ex et quam laborum'}

>>> print comments[0]['body']
     laudantium enim quasi est quidem magnam voluptate ipsam eos
     tempora quo necessitatibus
     dolor quam autem quasi
     reiciendis et nam sapiente accusantium

Listando os nomes dos 10 primeiros comments:

>>> for comment in comments[0:10]:
        print comment['name']
     labore ex et quam laborum
     quo vero reiciendis velit similique earum
     odio adipisci rerum aut animi
     alias odio sit
     vero eaque aliquid doloribus et culpa
     et fugit eligendi deleniti quidem qui sint nihil autem
     repellat consequatur praesentium vel minus molestias voluptatum
     et omnis dolorem
     provident voluptas
     eaque et deleniti atque tenetur ut quo ut

Além da listagem de todos os objetos, também podemos obter um objeto em específico:

>>> response = requests.get("http://jsonplaceholder.typicode.com/comments/1")
>>> response.content
     '{\n  "postId": 1,\n  "id": 1,\n  "name": "id labore ex et quam laborum",\n  "email": "Eliseo@gardner.biz",\n  "body": "laudantium enim quasi est quidem magnam voluptate ipsam eos\\ntempora quo necessitatibus\\ndolor quam autem quasi\\nreiciendis et nam sapiente accusantium"\n}'
>>> comment = json.loads(response.content)
>>> print comment['name']
     labore ex et quam laborum

Se quisermos descobrir a qual post que o comment acima se refere, basta fazer uma requisição GET à http://jsonplaceholder.typicode.com/posts/X, sendo X o valor do campo postId do comment retornado. Veja:

>>> post = requests.get("http://jsonplaceholder.typicode.com/posts/%d" % comment['postId'])
>>> post.content
     '{\n  "userId": 1,\n  "id": 1,\n  "title": "sunt aut facere repellat provident occaecati excepturi optio reprehenderit",\n  "body": "quia et suscipit\\nsuscipit recusandae consequuntur expedita et cum\\nreprehenderit molestiae ut ut quas totam\\nnostrum rerum est autem sunt rem eveniet architecto"\n}'
>>> post = json.loads(post.content)
>>> post
     {u'body': u'quia et suscipit\nsuscipit recusandae consequuntur expedita et cum\nreprehenderit molestiae ut ut quas totam\nnostrum rerum est autem sunt rem eveniet architecto',
     u'id': 1,
     u'title': u'sunt aut facere repellat provident occaecati excepturi optio reprehenderit',
     u'userId': 1}
>>> post['title']
     u'sunt aut facere repellat provident occaecati excepturi optio reprehenderit'

Dessa forma, podemos navegar entre registros, obter objetos relacionados, etc.

Inserindo dados

Para a inserção de dados em um serviço que oferece uma API REST, precisamos utilizar o método POST do HTTP, disponível através da função post da requests. Como queremos inserir um novo registro no servidor, é necessário que passemos esse registro junto à requisição HTTP. Isso pode ser feito passando um dicionário com os dados ao parâmetro data:

>>> dados = data={"postId": 1, "name": "John Doe", "email": "john@doe.com", "body": "This is it!"}
>>> response = requests.post("http://jsonplaceholder.typicode.com/comments/", data=dados)

Feito isso, agora podemos verificar qual a resposta do serviço para a nossa requisição. O valor esperado depende de quem projetou a API, pois ele pode enviar uma resposta contendo o novo registro, a URL de acesso ao registro recém-criado, ou outra informação. Além disso, o código de resposta HTTP também pode variar (alguns serviços respondem com 200 — OK, outros com 201 – Created, embora o último faça muito mais sentido). O serviço que estamos usando para os exemplos envia uma resposta com o código 200 e o registro recém inserido como conteúdo.

Como ocorreu tudo dentro do esperado, o serviço respondeu com o registro criado (repare que foi adicionado um campo id que não havia nos dados que enviamos):

>>> print response.status_code
     200
>>> print response.content
     {
     "body": "This is it!",
     "postId": "1",
     "name": "John Doe",
     "email": "john@doe.com",
     "id": 501
     }

Para ter certeza sobre o funcionamento da API que você estiver usando, é preciso ler a especificação dela para descobrir o que esperar como resultado em caso de sucesso ou de erro. Como o protocolo HTTP já possui um conjunto pré-definido de códigos de status, os serviços baseados em REST devem usar tais códigos para indicar o status da requisição.

Alterando registros

O padrão REST define que o método HTTP PUT deve ser utilizado sobre um determinado recurso quando desejarmos alterá-lo. A biblioteca requests fornece a função put para o envio de requisições HTTP que utilizam o método PUT. Vamos a um exemplo, onde vamos alterar o campo email do comentário de id 10:

>>> dados = {"email": "john@doe.com"}
>>> response = requests.put("http://jsonplaceholder.typicode.com/comments/10", data=dados)

Ou seja, enviamos uma requisição PUT à URL que representa o comentário que queremos alterar, e passamos também um dicionário contendo o novo valor para o campo que desejamos alterar. Como resposta, obtivemos o recurso alterado.

Removendo registros

Para apagar um registro, o padrão REST define que uma requisção HTTP usando o método DELETE deve ser enviada ao serviço, passando como recurso o registro que deve ser removido. Para apagar o comment de id 10, utilizamos a função delete da requests:

>>> response = requests.delete("http://jsonplaceholder.typicode.com/comments/10")

Acessando recursos aninhados

Como já vimos pela estrutura dos dados retornados para os comments, cada registro desse tipo está associado a um registro post. Assim, uma necessidade que surge naturalmente é a de obter todos os comments pertencentes a um determinado post. O web service que estamos usando permite consultas a recursos relacionados. Para obter todos os comments relacionados ao post de id 2, fazemos:

>>> response = requests.get("http://jsonplaceholder.typicode.com/posts/2/comments")

Enfim

Apesar de o exemplo que seguimos ter focado em um web service específico, cada serviço possui uma interface de acesso própria. Ou seja, algumas APIs podem não permitir acesso a recursos aninhados, ou não permitir a remoção de registros, etc. É importante que você, antes de utilizar uma API REST, leia a documentação da mesma para saber o que é possível fazer com ela.

Apesar dessas diferenças entre uma API e outra, o mecanismo de acesso às mesmas não muda. Você vai precisar de uma biblioteca para emitir requisições HTTP (requests ou urllib2) e uma biblioteca para fazer a decodificação dos dados retornados (json, simplejson ou alguma biblioteca para manipulação de XML).

Obrigado ao Elias Dorneles pela revisão!