Esquisitices (ou não) no arredondamento em Python 3

O arredondamento de números em Python 3 pode ser feito usando uma função builtin chamada round(). Em sua forma mais simples, ela recebe um número qualquer e o arredonda para um número inteiro. Veja ela em ação:

>>> 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/

Anúncios

Web scraping em páginas baseadas em JavaScript com Scrapy

O Scrapy é um framework todo prontinho pra lidar com a maioria dos problemas que enfrentamos ao fazer web scraping. Porém, é um tanto comum termos que extrair dados de páginas cuja parte do conteúdo seja gerada por código JavaScript, que é tipicamente executado no nosso navegador. Aí é que tá problema, pois o Scrapy não executa os scripts presentes no HTML. Tudo o que ele faz é baixar o HTML exatamente da forma que o servidor entrega.

Este post vai fazer um apanhado geral sobre algumas formas de lidar com páginas baseadas em JavaScript. Vamos começar vendo como saber se determinada informação que queremos extrair é gerada por código JavaScript ou não.

Como identificar uma página baseada em JavaScript

Um jeito simples de descobrir se as informações que queremos extrair são gerada por código JS é usando o nosso navegador. Carregue a página e então utilize a opção “Visualizar código-fonte”. Se o conteúdo que você quer extrair estiver ali representado em HTML, você pode ficar tranquilo, pois você poderá extraí-lo tranquilamente usando somente o Scrapy.

Nota: não utilize a opção “Inspecionar Elemento” (ferramentas do desenvolvedor) neste caso. Embora ela seja uma mão na roda pra descobrirmos como os dados estão estruturados, o problema é que ela já mostra o fonte da página após ter sido renderizada pelo browser (incluindo conteúdo gerado dinamicamente por código JS).

Por exemplo, abra http://quotes.toscrape.com. Esta página mostra frases de autores famosos e, se você abrir o código-fonte da página, verá que cada frase está representada por um bloco div.quote.

Entretanto, se você carregar a variação gerada por JavaScript → http://quotes.toscrape.com/js, você irá perceber que as frases não estão lá bonitinhas dentro do HTML. Na realidade, elas estão entranhadas em um trecho de código JavaScript presente na página, que é executado pelo motor JavaScript do navegador.

Outra opção é usar uma extensão pro navegador que permita desabilitar o JavaScript em uma aba, como o Quick JavaScript Switcher, e então verificar se os dados que queremos extrair estão na página mesmo após desabilitamos o JavaScript.

Bom, uma vez que identificamos que o conteúdo da página é gerado por código JavaScript, o próximo passo é usar alguma das soluções a seguir para que possamos lidar com páginas baseadas em JS usando o Scrapy.

1. Usando um navegador headless

Usando o Scrapy, podemos terceirizar a tarefa de renderizar a página completa para um navegador web. Assim, ao invés de utilizarmos o HTML baixado pelo Scrapy, vamos fazer com que um navegador baixe a página e execute o código JS pra gente e entregue como resposta o HTML prontinho. Uma opção legal para isso é o PhantomJS, que é um navegador headless e que pode ser facilmente integrado com Python via Selenium.

import scrapy
from selenium import webdriver

class QuotesSeleniumSpider(scrapy.Spider):
    name = 'quotes-selenium'
    start_urls = ['http://quotes.toscrape.com/js']

    def __init__(self, *args, **kwargs):
        self.driver = webdriver.PhantomJS()
        super(QuotesSeleniumSpider, self).__init__(*args, **kwargs)

    def parse(self, response):
        self.driver.get(response.url)
        sel = scrapy.Selector(text=self.driver.page_source)
        for quote in sel.css('div.quote'):
            yield {
                'text': quote.css('span.text::text').extract_first(),
                'author': quote.css('small.author::text').extract_first(),
                'tags': quote.css('a.tag::text').extract()
            }

        next_page_url = response.css("li.next > a::attr(href)").extract_first()
        if next_page_url is not None:
            yield scrapy.Request(response.urljoin(next_page_url))

Nota: O spider acima requer o módulo Python para o Selenium, que pode ser instalado via pip install selenium. Também é necessária a instalação do binário do PhantomJS em algum lugar do seu PATH.

O spider acima instancia o driver selenium pro PhantomJS e, no método parse(), faz com que o PhantomJS baixe e renderize a página http://quotes.toscrape.com/js. O HTML renderizado (self.driver.page_source) é então usado para construir um objeto Selector que nos permite extrair dados usando os tradicionais seletores do Scrapy.

Contudo, quando executarmos o código acima, cada página será baixada duas vezes: uma pelo downloader do Scrapy e outra pelo método parse(), na chamada à self.driver.get(). Para evitar esse comportamento, podemos criar um downloader middleware que utilize o selenium para baixar a página ao invés do downloader do Scrapy. Você pode ver o código do middleware clicando aqui e um spider que utiliza tal middleware aqui.

2. Extraindo dados de dentro do código JavaScript

O código fonte da página http://quotes.toscrape.com/js nos mostra que as frases que são renderizadas pelo navegador estão dentro de um arrayzão JavaScript chamado data:

var data = [
{
  "author": {
    "goodreads_link": "/author/show/9810.Albert_Einstein",
    "name": "Albert Einstein",
    "slug": "Albert-Einstein"
  },
  "tags": ["Change", "deep-thoughts", "thinking", "world"],
  "text": "\u201cThe world as we have created it is a process of our thinking. It cannot be changed without changing our thinking.\u201d"
},
{
  "author": {
    "goodreads_link": "/author/show/1077326.J_K_Rowling",
    "name": "J.K. Rowling",
    "slug": "J-K-Rowling"
  },
  "tags": ["abilities","choices"],
  "text": "\u201cIt is our choices, Harry, that show what we truly are, far more than our abilities.\u201d"
},
...

Os dados que queremos extrair já estão prontinhos dentro da página, então podemos extraí-los sem usar um navegador headless. Como os seletores do Scrapy apenas lidam com HTML/XML, vamos usar a lib js2xml para converter o array JavaScript acima para XML e então extrair os dados usando seletores Scrapy.

import scrapy
import js2xml

class QuotesJs2XmlSpider(scrapy.Spider):
    name = 'quotes-js2xml'
    start_urls = ['http://quotes.toscrape.com/js/']

    def parse(self, response):
        script = response.xpath('//script[contains(., "var data =")]/text()').extract_first()
        script_as_xml = js2xml.parse(script)
        sel = scrapy.Selector(_root=script_as_xml)
        for quote in sel.xpath('//var[@name="data"]/array/object'):
            yield {
                'text': quote.xpath('string(./property[@name="text"])').extract_first(),
                'author': quote.xpath(
                    'string(./property[@name="author"]//property[@name="name"])'
                ).extract_first(),
                'tags': quote.xpath('./property[@name="tags"]//string/text()').extract(),
            }

        next_page_url = response.css("li.next > a::attr(href)").extract_first()
        if next_page_url is not None:
            yield scrapy.Request(response.urljoin(next_page_url))

No método parse() do spider acima primeiramente obtemos o código JS contido no elemento (linha 10) e então utilizamos o js2xml para convertê-lo para JavaScript. Depois disso, bastou construir um seletor Scrapy sobre tal valor e extrair os dados usando XPath (ou CSS).

Além de ter menos dependências, esta solução tem um desempenho melhor pois não depende do carregamento de um navegador (mesmo que seja headless como o PhantomJS) durante a execução.

3. Imitando o comportamento do navegador

A web está cheia de sites com conteúdo dinâmico carregado de acordo com ações do usuário. Por exemplo, o usuário de um e-commerce rola a página até o final e novos produtos são carregados automaticamente (a.k.a. rolagem infinita – infinite scrolling). Ou então o usuário clica em um botão que faz com que mais informações sejam mostradas sem recarregar a página.

Nesses casos, o que tipicamente acontece é que o navegador faz requisições AJAX que retornam mais informações quando determinado evento do usuário é disparado (scroll, click, etc).

Extrair dados de páginas desse tipo pode ser bem mais fácil do que a gente imagina. Ao invés de usar Selenium + PhantomJS, basta inspecionar as requisições AJAX que o navegador faz e imitá-las no nosso spider.

Considere a seguinte página: http://quotes.toscrape.com/scroll. A cada vez que rolamos ela até o fim, uma nova requisição é feita para a obtenção de novas frases que são então renderizadas pelo navegador. Para verificar quais requisições são feitas e para quais recursos, podemos usar o painel “Rede” das “Ferramentas do desenvolvedor” do nosso navegador favorito, como mostro abaixo no Chrome:

image00

No nosso exemplo, os novos resultados são obtidos por requisições para http://quotes.toscrape.com/api/quotes?page= e a resposta para as requisições vem prontinha em formato JSON. Ou seja, nem precisaremos usar XPath ou CSS para extrair os dados:

import json
import scrapy


class QuotesAjaxSpider(scrapy.Spider):
    name = 'quotes-ajax'
    base_url = 'http://quotes.toscrape.com/api/quotes?page=%d'
    start_urls = [base_url % 1]

    def parse(self, response):
        json_data = json.loads(response.text)
        for quote in json_data['quotes']:
            yield quote
        if json_data['has_next']:
            next_page = self.base_url % (int(json_data['page']) + 1)
            yield scrapy.Request(url=next_page, callback=self.parse)

O spider acima imita as requisições AJAX feitas pelo navegador e obtém os dados de todas as frases do site.

Em geral, você pode fazer o mesmo para a maioria das páginas que usam AJAX. Algumas podem ser mais complicadinhas, requerendo que você envie alguns dados pré-computados (como hashes) como parâmetro, mas nada que uma boa investigada na página não resolva.

Por fim

Espero que este post tenha ajudado a desmistificar um pouco o scraping de páginas baseadas em JavaScript. Como você pôde ver, nem sempre precisamos recorrer a uma ferramenta externa para renderizar o JS para a gente. Basta entender melhor como o protocolo HTTP e o navegador funcionam para que possamos lidar com esse tipo de problema.

Em alguns casos mais complexos (e também mais raros), você precisará simular a interação do usuário com a página. Para isso, você pode usar os métodos do selenium webdriver ou então simular tal comportamento usando um script Lua com o Splash.

O código apresentado neste post está disponível em: https://github.com/stummjr/pythonhelp-scrapy-javascript/

Customizando o prompt do IPython 5+

Há poucos meses atrás foi lançada a versão 5 do IPython. O shell que antes já era super legal, agora ficou mais interessante ainda, com syntax highlighting no código digitado e um esquema de completação inline usando umas listinhas bem convenientes:

screen-shot-2016-09-18-at-8-41-50-am

Porém, a forma de configuração do prompt mudou. Algumas das dicas apresentadas no post Sintonia Fina no IPython não se aplicam mais. Assim, vou mostrar aqui como fazer para que o seu IPython 5+ fique com aparência semelhante à abaixo:

screen-shot-2016-09-18-at-8-40-12-am

O que mudou basicamente é que ao invés de simplesmente definir a string que será usada como prompt em um atributo, agora é preciso implementar uma subclasse de Prompts, com alguns métodos para alterar o comportamento do seu prompt:

from IPython.terminal.prompts import Prompts, Token


class MyCustomPrompt(Prompts):

    def in_prompt_tokens(self, cli=None):
        return [(Token.Prompt, '>>> '), ]

    def out_prompt_tokens(self, cli=None):
        return [(Token.Prompt, ''), ]

    def continuation_prompt_tokens(self, cli=None, width=None):
        return [(Token.Prompt, ''), ]

No exemplo acima, customizei os prompts de entrada (de In [1]: para o tradicional >>>), de saída ( de Out[1]: para nada) e de continuação (de ...: para nada).

O legal dessa nova abordagem é que agora temos mais flexibilidade pra customizar os prompts, colocando valores dinâmicos dentro deles se quisermos.

Como configurar seu prompt

A configuração do IPython se dá através de perfis, então vamos começar criando o perfil default:

$ ipython profile create

Isso irá criar um diretório ~/.ipython com a seguinte estrutura:

.ipython
├── extensions
├── nbextensions
└── profile_default
    ├── ipython_config.py
    ├── ipython_kernel_config.py
    ├── log
    ├── pid
    ├── security
    └── startup
        └── README

Agora salve a classe MyCustomPrompt em um arquivo ~/.ipython/my_custom_prompt.py e depois disso edite o arquivo ~/.ipython/profile_default/ipython_config.py para que tenha o seguinte conteúdo:

from my_custom_prompt import MyCustomPrompt


c = get_config()

c.TerminalInteractiveShell.prompts_class = MyCustomPrompt
c.TerminalIPythonApp.display_banner = False
c.TerminalInteractiveShell.separate_in = ''

Pronto, agora o seu IPython 5+ deverá se parecer com aquele que mostrei no screenshot lá no começo do post.

Se você estiver usando uma versão anterior do IPython, verifique meu post anterior sobre o mesmo assunto: https://pythonhelp.wordpress.com/2013/12/29/sintonia-fina-do-ipython/

Confira as minhas configurações do IPython em: https://github.com/stummjr/dotfiles/tree/master/ipython

O estranho caso do else em loops

Uma das coisas que me chamou a atenção quando comecei a usar Python é o else. O seu uso “natural”, para definir um caminho alternativo para um if, não tem nada demais. O que é um pouco estranho é o fato de Python aceitar else em expressões de loop como for e while. Por exemplo, o código abaixo é perfeitamente válido:

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

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!