Destaques da PyCon2011: The Data Structures of Python

Vou iniciar esse artigo da mesma forma que Alex Gaynor (o palestrante) começou. "Quem aqui se lembra das aulas de estruturas de dados?". Em seguida, ele complementa: "E quem se importa?".

Para os que aprenderam a programar em linguagens de alto nível, estruturas de dado não é nada demais. Mas para as pessoas mais velhas como eu, que começaram a programar em C, estruturas de dados é algo extremamente difícil, porém valioso. O que ocorre é que as linguagens de alto nível já possuem diversas estruturas de dados implementadas, tornando sua utilização algo simples e indolor.

O Python não é exceção dessa regra, mas eu não concordo plenamente com a ideia de que esse conhecimento é descartável. O palestrante cita uma frase de Tim Peters, um dos grandes gurus do Python: "We read Knuth so you don’t have to." (Nós lêmos Knuth para que você não precise ler). Knuth, é um renomado professor da Universidade de Stanford e autor do livro The Art of Computer Programming, uma das principais referência na área de ciência da computação.

O Python implementa por padrão diversos tipos de estruturas de dados listas, tuplas, dicionários, sets, frozensets, arrays, bytearrays e outros menos utilizados ou mais recentes (como o OrderedDict). Esta palestra tenta mostrar como e onde utilizar alguns desses tipos (listas, tuplas, sets e frozensets):

Números, números, números…

Em minha humilde opinião, acho que faltaram números e estatísticas na palestra. Por exemplo, durante a comparação entre listas e sets ele cita a seguinte função:

def remove_dups(seq):
    seen = set()
    items = []
    for item in seq:
        if item not in seen:
            seen.add(item)
            items.append(item)
    return items

Ele cita também, que se você trocar o set seen por uma lista, o funcionamento seria o mesmo porem, o desempenho seria inferior. Como provar isso? Simples, basta criar a segunda função sugerida por ele:

def bad_remove_dups(seq):
    seen = []
    items = []
    for item in seq:
        if item not in seen:
            seen.append(item)
            items.append(item)
    return items

Além disso, precisamos de dois módulos (random e time), de uma função de bechmark e de uma massa de dados, conforme abaixo:

from random import random
from time import time

def bench(func):
    results = []
    for i in range(10):
        ini = time()
        func(data)
        results.append(time() - ini)
    print "Mean time:", sum(results)/10

data = [int(random()*50)for i in range(900000)]

Após isso, basta chamar a função de benchmark e passar as funções a serem testadas, conforme abaixo:

bench(remove_dups)
bench(bad_remove_dups)

Apesar de estarmos calculando a média de dez execuções, ainda ocorre uma leve variação nos tempos, mas todos sempre estão muito próximos. Abaixo segue a saída de uma execução que realizei:

Mean time: 0.0723000049591
Mean time: 0.580800008774

Podemos ver que o a função remove_dups é pouco além de 8 vezes mais rápida que a função bad_remove_dups.

Faça Você Mesmo

Uma dos pontos mais importantes para mim nessa palestra foi a utilização das classes abstratas do módulo collections. Eu já cometi várias vezes o erro de estender os tipos padrões do Python. Nunca façam isso… Nunca!