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

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

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

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

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

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

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

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

>>> odict = OrderedDict.fromkeys(urls)

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

Como resultado, temos:

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

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

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

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

>>> list(odict.keys())

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

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

Vez por outra os sistemas que a gente usa não entregam as informações da forma que desejamos. Seja o sistema do seu cartão de crédito que não lhe dá uma visualização legal dos seus gastos, ou até mesmo seu app de táxi que não lhe deixa fazer uma análise mais aprofundada dos trajetos que você tem feito.

Ah se todos eles tivessem um botãozinho “exportar tudo em JSON”!

A realidade é dura e a maioria dos apps não nos dão essa opção. Uma alternativa nesses casos é raspar os dados que desejamos do site do tal app, e isso envolve fazer seu web spider se autenticar no sistema. Nesse post, vamos ver como fazer para que um spider Scrapy faça login em um sistema qualquer.

Como funciona a autenticação em um website?

Existem várias maneiras diferentes, mas em linhas gerais a autenticação em websites funciona assim:

1. O usuário acessa URL que contém formulário de login. Exemplo: http://quotes.toscrape.com/login
2. O usuário preenche campos do formulário com suas credenciais e clica no botão de login
3. O navegador envia os dados preenchidos para o servidor, no corpo de uma requisição HTTP do tipo POST
4. O servidor valida as credenciais do usuário e envia de volta uma resposta contendo uma página indicando que o usuário se autenticou com sucesso e, juntamente com ela, um cookie de sessão.

O cookie de sessão é uma informação que o browser irá armazenar localmente e irá enviar juntamente com as requisições subsequentes ao mesmo website, de forma que o último possa identificar quem é o usuário fazendo tais requisições.

Assim sendo, nosso spider deverá reproduzir os passos recém descritos para que consiga se autenticar em um website. Então vamos a ele!

Nosso spider

Vamos construir um spider que se autentique em http://quotes.toscrape.com e de lá extraia o link para a página no Goodreads de cada autor, informação que só é visível para usuários autenticados.

Dê uma olhada no esqueleto do nosso spider:

# -*- coding:utf-8 -*-
import scrapy

class LoginSpider(scrapy.Spider):
    name = 'login-spider'
    start_urls = ['http://quotes.toscrape.com/login']

    def parse(self, response):
        # depois a gente vai implementar aqui o preenchimento do formulário
        # contido em response e fazer a requisição de login
        self.log('visitei a página de login: {}'.format(response.url))

    def parse_author_links(self, response):
        # aqui a gente vai extrair os links para as páginas dos autores
        # ou seja, quando chegar aqui, o spider já estará autenticado
        pass

Quando rodarmos nosso spider, o Scrapy vai chamar automaticamente o método parse() assim que a resposta para a URL http://quotes.toscrape.com/login tiver sido baixada e a mensagem de log será impressa. Vá em frente e rode o spider acima só pra ver isso acontecendo:

$ scrapy runspider loginspider.py

Manipulando o formulário

O formulário de login do nosso site está representado assim:

<form action="/login" method="post" accept-charset="utf-8" >
    <input type="hidden" name="csrf_token" value="fHQgXTCzxs...aOkolIudtjV"/>
    <label for="username">Username</label>
    <input type="text" class="form-control" id="username" name="username" />
    <label for="username">Password</label>
    <input type="password" class="form-control" id="password" name="password" />
    <input type="submit" value="Login" class="btn btn-primary" />
</form>

Perceba que temos 4 inputs nesse formulário: username, password, o botão de login em si e um campo oculto chamado csrf_token. Não vou entrar em detalhes sobre proteção CSRF, mas o que você precisa saber é que a maioria dos sites por aí vai ter um campo desses no formulário de login deles e que você precisa enviar tal campo juntamente com a requisição de autenticação. Caso contrário, o servidor não irá validar sua requisição.

No Scrapy, requisições do tipo POST podem ser feitas com um tipo especial de Request chamado FormRequest. Nossa requisição de autenticação será:

req = scrapy.FormRequest(
    url='http://quotes.toscrape.com/login',
    formdata={
        'username': 'john.doe',
        'password': 'anything',
        'csrf_token': token,
    },
    callback=self.parse_author_links,
}

Alguns detalhes importantes:

• O valor do campo csrf_token é gerado dinamicamente para cada requisição à página de login. Assim, teremos que extrair ele da página de login antes de fazer a requisição.
• A URL passada ao objeto FormRequest deve ser aquela encontrada no atributo action do formulário de login.
• As chaves do dicionário passado ao parâmetro formdata devem usar como nome o valor do atributo name do input correspondente no formulário.

Agora que a gente já sabe como fazer uma requisição do tipo POST, vamos ao spider:

# -*- coding:utf-8 -*-
import scrapy
from scrapy.exceptions import CloseSpider

class LoginSpider(scrapy.Spider):
    name = 'login-spider'
    start_urls = ['http://quotes.toscrape.com/login']

    def parse(self, response):
        self.log('visitei a página de login: {}'.format(response.url))
        token = response.css('input[name="csrf_token"]::attr(value)').extract_first()
        yield scrapy.FormRequest(
            url='http://quotes.toscrape.com/login',
            formdata={
                'username': 'john.doe',
                'password': 'anything',
                'csrf_token': token,
            },
            callback=self.parse_author_links,
        )

    def parse_author_links(self, response):
        has_logout_link = response.css('a[href="/logout"]').extract_first()
        if not has_logout_link:
            raise CloseSpider('falha de autenticação')
        self.log('acabei de fazer login')

        links = response.css('.quote a[href*="goodreads.com"]::attr(href)').extract()
        for link in links:
            yield {'link': link}

        next_page = response.css('li.next a::attr(href)').extract_first()
        if next_page:
            yield scrapy.Request(
                url=response.urljoin(next_page),
                callback=self.parse_author_links,
            )

Na linha 11 (método parse()), extraímos o token da página para enviar junto com a requisição de autenticação e, logo em seguida, o método parse() gera a requisição POST para a URL de login. Repare que registramos o método self.parse_author_links como o callback para manipular a página enviada como resposta pelo servidor.

No método parse_author_links, verificamos se o botão de logout apareceu na página (o que indica que estamos autenticados) e, caso não esteja, encerramos a execução do spider (linha 25).

Depois disso, basta extrair as URLs dos autores (linhas 28-30). Veja a versão completa do spider aqui.

E o cookie de sessão?

Ah, lembra que falei no começo do artigo que o navegador armazena um cookie de sessão e envia ele junto com as requisições subsequentes pro mesmo site? Pois é, o Scrapy faz a mesma coisa pra gente. Ou seja, não precisamos nos preocupar em manter a sessão.

Simplificando um pouco

É bem comum termos que submeter valores presentes em campos ocultos (hidden) juntamente com os dados que preenchemos no formulário. Para facilitar a nossa vida, o Scrapy fornece um método chamado FormRequest.from_response(), que carrega automaticamente os valores dos campos do formulário que possuem valores default. Nosso método parse() ficaria assim se utilizássemos o from_response():

def parse(self, response):
    self.log('visitei a página de login: {}'.format(response.url))
    yield scrapy.FormRequest.from_response(
        response,
        formdata={
            'username': 'john.doe',
            'password': 'anything',
        },
        callback=self.parse_author_links,
    )

Como você pode ver, não precisamos extrair e passar o csrf token, nem passar a URL do formulário. O from_response já faz isso pra gente.

Por fim

Agora você já pode fazer um spider para extrair aqueles dados que você precisa para o seu relatório. Mas, antes de fazer seu spider, verifique se ele não está violando os termos de serviço do seu banco, ou seja lá qual sistema que você estiver acessando.

>>> round(1.2)
1
>>> round(1.8)
2

Ela ainda aceita um segundo parâmetro, que indica quantos dígitos de precisão queremos no resultado. O valor padrão desse parâmetro é 0, mas podemos passar qualquer valor:

>>> round(1.847, ndigits=2)
1.85
>>> round(1.847, ndigits=1)
1.8

E o que será que acontece quando queremos arredondar um número como 1.5? A round() arredonda pra cima ou pra baixo? Vamos ver:

>>> round(1.5)
2

Arredonda pra cima? Vamos ver mais um número só pra ter certeza:

>>> round(2.5)
2

Ops, agora foi pra baixo! Vamos ver mais alguns:

>>> round(3.5)
4
>>> round(4.5)
4
>>> round(5.5)
6

Calma aí que tudo tem uma explicação. Em Python 3, a round() define o arredondamento assim:

Arredonda pro mais próximo.
Se empatar, arredonda pro número PAR mais próximo.

Agora faz sentido né? Revendo os exemplos dali de cima, vemos que o arredondamento sempre foi feito pro par mais próximo:

>>> round(3.5)
4
>>> round(4.5)
4
>>> round(5.5)
6

No caso do 3.5, tanto o 3 quanto o 4 estão à mesma distância dele. Ou seja, deu empate. Como a regra determina, round() desempata pro par mais próximo, que é 4.

E em Python 2?

Em Python 2 é diferente. O empate em arredondamentos é sempre resolvido pra cima, em caso de números positivos:

>>> round(1.5)
2.0
>>> round(2.5)
3.0

E pra baixo, em caso de números negativos:

>>> round(-1.5)
-2.0
>>> round(-2.5)
-3.0

Mas por que Python 3 faz diferente?

O objetivo é deixar o arredondamento menos tendencioso.

Imagine um banco onde todos os arredondamentos são feitos para cima. Ao final do dia, o relatório de receitas do banco vai mostrar um valor mais alto do que o banco realmente recebeu. É exatamente o que acontece em Python 2:

>>> valores = [1.5, 2.5, 3.5, 4.5]
>>> sum(valores)
12.0
>>> sum(round(v) for v in valores)
14.0

Usando a regra de arredondamento de Python 3, os valores arredondados nas operações tendem a ser amortizados, porque metade deles vai ser para cima e a outra metade para baixo, visto que metade dos números existente são pares e a outra metade são ímpares. Veja o mesmo código, agora rodando em Python 3:

>>> valores = [1.5, 2.5, 3.5, 4.5]
>>> sum(valores)
12.0
>>> sum(round(v) for v in valores)
12

Na realidade, isso não é uma novidade de Python 3. Esse tipo de arredondamento é antigo e tem até nome: Bankers Rounding (Arredondamento de Banqueiros).

Se ficou interessado no assunto, dê uma olhada num outro post daqui do blog, que mostra como funciona a divisão inteira em Python: https://pythonhelp.wordpress.com/2013/06/30/comportamento-inesperado-na-divisao-inteira/

    f = open(...)
    ....
    f.close()

    a = A(...)
    a.start(...)
    ...
    a.end()

    c = Coisa(...)
    c.cria(...)
    ....
    c.destroi()

    test = Test()
    test.setUp()
    test.run()
    test.tearDown()

Os trechos de código acima possuem em comum o que chamamos acoplamento temporal (do inglês, temporal coupling).

Acoplamento mede o quanto uma coisa depende de outra em software, e é comumente medida entre módulos ou componentes – tipo, o quanto certas classes ou funções dependem uma da outra. Em geral, é desejável que haja poucas interdependências, para evitar que a complexidade se espalhe em um projeto.

O acoplamento temporal acontece quando uma coisa precisa ser feita depois de outra, mesmo que seja dentro do mesmo módulo ou função. A relação de interdependência é com o tempo, isto é, o momento em que as coisas precisam acontecer. Alguns exemplos seriam: fechar um arquivo depois de terminar de carregar o conteúdo, liberar memória quando acabar de usar, etc.

Reduzindo o acoplamento temporal

Desde a versão 2.5, Python possui o comando with para lidar exatamente com este tipo de situação. Com ele, podemos fazer:

    with open(...) as f:
        dados = f.read()
    # processa dados aqui

Ao usar o bloco with para abrir um arquivo, o método close() é chamado por trás dos panos pelo gerenciador de contexto incondicionalmente (isto é, mesmo que ocorra alguma exceção no código de dentro do bloco).

O código equivalente seria:

    f = open(...)
    try:
        dados = f.read()
    finally;
        f.close()

Repare como o primeiro código é mais curto e mais simples que o segundo, pois há menos interdependências entre as coisas que estão acontecendo.

A ideia é não precisar lembrar de ter que escrever try/finally e chamar o close(), utilizando por trás dos panos um código que se certifique de que as coisas aconteçam na ordem esperada. A este código, chamamos de gerenciadores de contexto, ou context managers.

Implementando um gerenciador de contexto

A maneira mais simples de implementar um gerenciador de contexto Python é utilizar o decorator contextlib.contextmanager. Vejamos um exemplo:

import os
import contextlib

@contextlib.contextmanager
def roda_em_dir(dir):
    orig_dir = os.getcwd()
    os.chdir(dir)
    try:
        yield
    finally:
        os.chdir(orig_dir)

Esse gerenciador de contexto nos permite rodar um código em um diretório qualquer, e ao fim dele voltar para o diretório que estávamos antes.

A função os.getcwd() devolve o diretório atual e a função os.chdir() entra no diretório passado como argumento, e depois os.chdir() é usada novamente para voltar para o diretório original.

Veja como usá-lo:

print('Comecei no diretorio: %s' % os.getcwd())

with roda_em_dir('/etc'):
    print('Agora estou no diretorio: %s' % os.getcwd())

print('E agora, de volta no diretorio: %s' % os.getcwd())

Rodando esse código na minha máquina, a saída é:

Comecei no diretorio: /home/elias
Agora estou no diretorio: /etc
E agora, de volta no diretorio: /home/elias

A função roda_em_dir() é o que chamamos de uma corotina, pois utiliza o comando yield para “pausar” sua execução, entregando-a para o código que está dirigindo-a. Neste caso, isso é o trabalho do decorator contextlib.contextmanager, que entrega a execução para o código que está dentro do bloco with até que este termine, o que devolverá a execução para a corotina roda_em_dir(), que irá executar o código dentro do finally.

Não se preocupe se for um pouco difícil de entender como a coisa toda funciona, estamos passando por cima de alguns tópicos avançados aqui (decorators, corotinas, etc). O importante é que você se dê conta de que pode implementar um gerenciador de contexto rapidamente usando o contextlib.contextmanager com uma função que faça yield dentro de um bloco try/finally.

Vejamos um outro exemplo, desta vez vamos fazer um gerenciador de contexto que cria um arquivo temporário para utilizarmos em um código de teste, e deleta o arquivo automaticamente ao fim do bloco with:

import os
import contextlib
import tempfile

@contextlib.contextmanager
def arquivo_temp():
    _, arq = tempfile.mkstemp()
    try:
        yield arq
    finally:
        os.remove(arq)

Repare como desta vez, o comando yield não está mais sozinho, desta vez ele está enviando a variável arq que contém o nome do arquivo temporário para ser usado no with, como segue:

with arquivo_temp() as arq:
    print('Usando arquivo temporario %s' % arq)
    print('Arquivo existe? %s' % os.path.exists(arq))

print('E agora, arquivo existe? %s' % os.path.exists(arq))

Rodando na minha máquina, a saída ficou:

Usando arquivo temporario /tmp/tmp2IUF7H
Arquivo existe? True
E agora, arquivo existe? False

Note como a variável arq pode ser usada depois do with também: isto mostra que o contexto está sendo gerenciado de maneira especial, mas o espaço de nomes de variáveis ainda é o mesmo (ou seja, o comando with é mais parecido com if e for, do que com o comando def, por exemplo).

Para concluir

Bem, apesar do mecanismo por trás ser um pouquinho complicado de entender inicialmente, você pode perceber que implementar um gerenciador de contexto não é muito difícil. Você precisa usar o decorator contextlib.contextmanager em uma função geradora fazendo yield dentro de um bloco try/finally – moleza!

Você também pode implementar um gerenciador de contexto escrevendo uma classe que implemente o protocolo do comando with, que envolve basicamente implementar dois métodos especiais chamados __enter__ e __exit__ que sinalizam respectivamente entrar e sair do bloco with.

Em geral é mais conveniente utilizar o @contextlib.contextmanager, mas em alguns casos é melhor implementar os métodos. Por exemplo, caso queira compartilhar o próprio objeto gerenciador do contexto dentro do with, você pode usar return self no método __enter__.

Agora, vá refatorar aqueles códigos com acoplamento temporal e se divirta!

# -*- coding:utf-8 -*-
import random
segredo = random.randint(0, 10)
for tentativa in range(1, 4):
    numero = input('Digite um número entre 0 e 9 (tentativa %d de 3):' % tentativa)
    if numero == segredo:
        print('você acertou!')
        break
else:
    print('você esgotou as suas tentativas')

Perceba que o else está alinhado com o for e não com o if. Neste caso, os comandos contidos nele somente serão executados se o loop não tiver sido encerrado por um break. O mesmo vale para o else em loops while. No exemplo abaixo, o else nunca será executado pois o loop é sempre encerrado por um break:

while True:
    break
else:
    print('nunca serei!')

Confesso que sempre tive uma certa dificuldade para lembrar o significado do else nesses casos, até porque raramente me deparo com eles. Então, certo dia assisti a palestra Transforming Code into Beautiful, Idiomatic Python do Raymond Hettinger, em que ele diz em um certo momento:

O else de loops em Python deveria ser chamado ‘nobreak’.

Pronto, nunca mais esqueci o significado do else em loops!

Há um tempo atrás mostramos aqui no blog um pequeno exemplo disso, explicando como baixar uma URL com tolerância a falhas simples em Python só com a biblioteca padrão. Acontece que tem um jeito melhor de fazer esse tipo de coisa, que resulta em código limpo e fácil de mudar: usar a biblioteca retrying.

Para começar, instale o pacote retrying com:

pip install retrying

Agora, para usar no seu código, importe o decorator retry (aprenda aqui sobre decorators) e use-o para alguma função que você deseja tentar de novo quando falhar (isto é, quando levantar alguma exceção):

from retrying import retry

@retry
def faz_algo_nao_confiavel():
    print("Tentando...")
    import random
    if random.randint(0, 10) > 1:
        raise RuntimeError("Putz, deu zica!")
    else:
        return "Funcionou!"

A função acima só funciona sem levantar exceção 20% das vezes que é chamada. Colocando o decorator, ela fica envolta em uma lógica que tenta de novo até que funcione sem a exceção. Rodando algumas vezes no meu laptop, a saída fica:

>>> faz_algo_nao_confiavel()
Tentando...
'Funcionou!'
>>> faz_algo_nao_confiavel()
Tentando...
Tentando...
Tentando...
Tentando...
Tentando...
Tentando...
Tentando...
'Funcionou!'
>>> faz_algo_nao_confiavel()
Tentando...
Tentando...
'Funcionou!'

Esse é apenas o jeito mais simples de usar. Em problemas do mundo real, você provavelmente vai querer configurar um intervalo de espera entre cada tentativa e também um limite máximo:

@retry(stop_max_attempt_number=7, wait_fixed=2000)
def busca_algo_na_rede():
    ....

A função acima será tentada no máximo 7 vezes, esperando 2 segundos (2000 ms) entre cada tentativa.

Outra opção interessante é o backoff exponencial, útil quando você quer ajustar a taxa de tentativas para não exigir demais de um sistema remoto que pode estar tendo dificuldades de sobrecarga. Veja um exemplo:

@retry(wait_exponential_multiplier=500, wait_exponential_max=30000)
def aciona_outro_sistema():
    ...

Nesse exemplo, caso a função falhar, será tentada novamente com um intervalo de espera calculado usando uma fórmula exponencial, tentando a primeira vez após 1s, na segunda 2s, na próxima 4s, 8s, 16s até o limite de 30s e então seguirá tentando com esse limite.

Quando não é adequado usar @retry?

Essa ideia de tentar de novo só funciona bem para operações que sejam idempotentes, isto é, que você pode acionar várias vezes sem alterar o resultado.

Por isso, quando quiser adicionar @retry em uma função existente, tenha cuidado para que seja uma função segura de ser chamada mais de uma vez. Em alguns casos, você terá que criar uma nova função com a parte que pode falhar e que funcione dependendo apenas dos próprios parâmetros (tornando-a assim idempotente) e colocar o @retry nessa função.

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:

• https://docs.python.org/2/reference/expressions.html#lambda
• http://www.diveintopython.net/power_of_introspection/lambda_functions.html

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:

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.

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:

• Brincando com listas
• Ordenação de uma lista
• List Comprehensions
• Acessando o último elemento de uma lista
• filter() – filtrando elementos de uma lista
• A função enumerate()
• Por que for i in range(x, y)?
• each_cons – percorrendo sequências em N elementos por vez
• map, reduce, filter e lambda
• Retirando elementos vazios de uma lista

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.

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.

Á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ó.

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.

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

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

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

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

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

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

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

root = BSTNode(42)

Esse código cria a seguinte árvore:

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:

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:

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:

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.

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:

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:

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).

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:

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:

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.

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.

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.

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!

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:

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

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.

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.

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:

• python-twitter: https://github.com/bear/python-twitter
• tweepy: https://github.com/tweepy/tweepy
• twython: http://twython.readthedocs.org/en/latest/(dica do @cassiobotaro)
• Outros wrappers: http://dev.twitter.com/docs/twitter-libraries#python