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

Vamos ver como isso funciona na prática. Primeiramente, vamos criar uma lista com 10 elementos e depois bagunçá-la usando a função shuffle, do módulo random.

>>> lista = range(10)
>>> lista
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> import random
>>> random.shuffle(lista)
>>> lista
[2, 5, 4, 1, 3, 6, 9, 7, 0, 8]

Tudo que precisamos fazer para ordenar uma lista desordenada é:

>>> lista.sort()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Barbada! Também podemos ordená-la de forma descendente:

>>> lista.sort(reverse=True)
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

A ordenação de inteiros ou de valores de tipos de dados simples é bem trivial. Porém, se quisermos ordenar uma lista que contém instâncias de uma classe, precisaremos utilizar o parâmetro key do sort.

O parâmetro key

O parâmetro key do método sort espera uma função que será chamada uma vez para cada um dos elementos da lista e o retorno dessa função será utilizado na comparação com os outros elementos da lista.

Considere que temos uma classe Aluno, conforme o código abaixo:

class Aluno:
	def __init__(self, nome, matricula):
		self.nome = nome
		self.matricula = matricula

	def __str__(self):
		return "%s - %s" % (str(self.nome), str(self.matricula))

Dada uma lista chamada alunos contendo n objetos do tipo Aluno, como ordená-la? Se chamarmos alunos.sort(), sem especificar como queremos que ela seja ordenada, o sort irá ordená-la através de comparações dos endereços de memória dos objetos contidos na lista alunos. Se quisermos que a ordenação se dê por algum dos atributos da classe, devemos especificar isso através do parâmetro key.

Vamos primeiramente criar uma lista com objetos de conteúdo aleatório:

>>> alunos = [Aluno("".join(random.sample(string.ascii_letters, 5)), random.randint(0, 100)) for i in range(10)]
>>> for aluno in alunos:
		print aluno

zfbnu - 12
sxbIX - 77
vJCIN - 33
aBjZA - 70
fNLeS - 19

Bonitos os nomes deles, né? Agora, vamos ordená-los:

>>> alunos.sort(key=lambda a: a.nome)
>>> for aluno in alunos:
        print aluno

aBjZA - 70
fNLeS - 19
sxbIX - 77
vJCIN - 33
zfbnu - 12

O que fizemos foi especificar como queremos que os elementos sejam comparados.  Para isso, criamos uma função anônima que recebe como parâmetro um objeto e retorna o elemento a ser usado na comparação (o atributo nome). O mesmo poderia ser feito com uma função nomeada, como:

>>> def key_func(aluno):
...     return aluno.nome
>>> alunos.sort(key=key_func)
>>> for aluno in alunos:
...     print aluno

Porém, ter que criar uma função (anônima ou não) somente para indicar qual atributo deverá ser usado na ordenação é um pouco inconveniente. Por isso, vamos utilizar o outro mecanismo que permite que façamos a mesma coisa. Ao invés de criarmos uma função que recebe um objeto e retorna o atributo nome daquele objeto, vamos usar a função attrgetter do módulo operator, que retorna o valor do atributo solicitado no objeto em questão.

>>> from operator import attrgetter
>>> alunos.sort(key=attrgetter("nome"))

A função attrgetter irá retornar uma outra função que quando chamada sobre cada objeto x contido na lista alunos, irá retornar x.nome.

Ou seja, para cada objeto Aluno contido na lista, será chamado o método attrgetter, solicitando o atributo nome.

Ordenando uma lista de listas

Já vi muito código que utiliza lista ou tupla como mecanismo para agrupar dados. Ao invés de criar uma classe ou uma namedtuple, o cara vai lá e empacota os dados que deseja em uma tupla. Por exemplo, ao invés de criar uma classe Aluno, poderíamos ter empacotado os dados referentes a cada aluno em uma tupla. Veja:

>>> alunos = [("Jose", 12345), ("Maria", 28374), ("Joao", 11119), ("Joana", 12346)]

Para ordenar uma lista desse tipo, podemos continuar usando o método sort e o parâmetro key, e agora vamos especificar qual elemento das tuplas que compõem a lista será utilizado na comparação para definir qual elemento precede qual na ordem. No exemplo abaixo, estamos ordenando os alunos pelo número da matrícula.

>>> alunos.sort(key=lambda x: x[1])
>>> print alunos
[('Joao', 11119), ('Jose', 12345), ('Joana', 12346), ('Maria', 28374)]

A função anônima poderia ser evitada novamente usando a função itemgetter:

>>> from operator import itemgetter
>>> alunos.sort(key=itemgetter(1))

O itemgetter é bem parecido com o attrgetter, com a diferença de que passamos para ele o índice do elemento que queremos que seja usado na comparação que será feita ao ordenar a lista.

Mas fique atento, o método sort está presente somente nas listas. Para ordenar outros objetos iteráveis, dê uma olhada na função builtin sorted.

Por exemplo, se você tem uma lista [1, 3, 5, 7, 9] você pode usar o each_cons para percorrer de 2 em 2 elementos:

(1, 3), (3, 5), (5, 7), (7, 9)

ou de 3 em 3 elementos de cada vez:

(1, 3, 5), (3, 5, 7), (5, 7, 9)


Ele ajuda a criar operações que envolvem uma espécie de “janela deslizante” (sliding window), um conjunto de elementos da sequência sobre o qual podemos inferir alguma informação.

Essa abstração se revela bem útil na hora de escrever certos algoritmos e por isso é interessante tê-la como carta na manga.

Implementando em Python

Python não tem um método ou função equivalente ao each_cons na API padrão, mas encontrei algumas sugestões de implementação nas respostas a uma pergunta no StackOverflow. Eis uma delas, que funciona para listas e tuplas:

import itertools
def each_cons(xs, n):
    return itertools.izip(*(xs[i:] for i in xrange(n)))

Para entender como esse código funciona, vamos por partes. Acompanhe:

>>> xs = [1, 2, 3, 4, 5]
>>> xs[0:] # primeiro slice
[1, 2, 3, 4, 5]
>>> xs[1:] # segundo slice
[2, 3, 4, 5]
>>> xs[2:] # terceiro slice
[3, 4, 5]
>>> zip(xs[0:], xs[1:], xs[2:]) # zip dos slices
[(1, 2, 3), (2, 3, 4), (3, 4, 5)]

Os passos acima delineiam o algoritmo dessa implementação do each_cons. Basicamente, obtemos slices da lista na quantidade de elementos que queremos na nossa janela deslizante, e aplicamos zip() neles.

O código mostrado usa uma generator expression para gerar os slices, o truque da estrela nos argumentos para passar os argumentos pro zip e a função izip do módulo itertools que é o equivalente da builtin zip() para generators.

Exemplos de utilidade

1) Encontrar os pares de números com distância entre si maior que 1:

>>> numeros = [1, 2, 3, 5, 9, 10]
>>> [(a, b) for a, b in each_cons(numeros, 2) if b - a > 1]
[(3, 5), (5, 9)]

2) Descobrir se os números de uma lista formam uma sequência:

>>> all([a + 1 == b for a, b in
                        each_cons([1, 2, 3, 4, 5], 2)])
True
>>> all([a + 1 == b for a, b in
                        each_cons([1, 3, 5, 7], 2)])
False

3) Calcular as médias das vendas de cada trimestre:

>>> totais_mensais = [123.45, 54.3, 428, 144.2, 245.45]
>>> [float(a+b+c)/3 for a, b, c in
                        each_cons(totais_mensais, 3)]
[201.91666666666666, 208.83333333333334, 272.55]

Esse tipo de média é conhecido por média móvel, é comum em aplicações financeiras e também é útil para amaciar as linhas de um gráfico.

4) Percorrer as linhas de um arquivo procurando por duplicatas:

>>> linhas = open('arquivo.txt').readlines()
>>> [(num, a) for num,(a,b) in
                  enumerate(each_cons(linhas, 2), 1)
                  if a == b]
[(3, 'tres\n'), (5, 'quatro\n')]

Para um arquivo.txt contendo o texto:

um
dois
tres
tres
quatro
quatro
cinco


Generalizando para generators

A função each_cons que apresentamos acima, apesar de funcionar bem para listas e tuplas, não funciona para generators nem para objetos xrange(). Veja o erro que acontece quando tentamos rodar com um generator:

>>> each_cons((a for a in xrange(10)), 2) # testando com um generator
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in each_cons
TypeError: type object argument after * must be a sequence, not generator

É interessante termos uma solução que funcione também para generators, para o caso de estarmos lidando com um grande volume de dados vindo de um banco de dados, por exemplo.

Para obter isso, basta usar mais algumas funções do módulo itertools na brincadeira:

import itertools
def each_cons(xs, n):
    return itertools.izip(*(itertools.islice(g, i, None)
                          for i,g in
                          enumerate(itertools.tee(xs, n))))

A implementação mostrada acima funciona com sequências (listas, tuplas, strings), generators e objetos xrange() também.

# python 2:
lista = range(100)
# python 3:
lista = list(range(100))

Criando uma lista com list comprehensions:

lista = [x*2 for x in range(100)]

Percorrendo uma lista com for in:

for x in lista:
    # faça algo com x

Percorrendo uma lista, obtendo os valores e seus índices:

for indice, valor in enumerate(lista):
    print "lista[%d] = %d" % (indice, valor)

Percorrendo um pedaço de uma lista usando slicing:

for x in lista[40:60]:
    # faça algo com x

Percorrendo uma lista de trás pra frente definindo o passo do slicing como -1:

for x in lista[::-1]:
    # faça algo com x

Ou:

for x in reversed(lista):
    # faça algo com x

Percorrendo uma lista ordenada:

for x in sorted(lista):
    # faça algo com x

Acessando o último elemento de uma lista com o índice -1:

print lista[-1]

Copiando uma referência para uma lista:

>>> nova_ref = lista
>>> nova_ref is lista
True

Copiando de verdade uma lista:

>>> nova_lista = lista[:]
>>> nova_lista is lista
False

Ou, usando o módulo copy:

>>> import copy
>>> nova_lista = copy.copy(lista)
>>> nova_lista is lista
False

Ou caso lista contivesse listas aninhadas e quiséssemos fazer com que estas também fossem completamente copiadas, e não somente referenciadas, usaríamos a função deepcopy():

>>> nova_lista = copy.deepcopy(lista)
>>> nova_lista is lista
False

Embaralhando os elementos de uma lista (in-place):

>>> import random
>>> random.shuffle(lista)  # altera a própria lista

Obtendo uma amostra aleatória (de 10 elementos) de uma lista:

>>> print random.sample(lista, 10)
[729, 9025, 2401, 8100, 5776, 784, 1444, 484, 6241, 7396]

Obtendo um elemento aleatório de uma lista:

>>> random.choice(lista)
7744

Gerando uma lista com 10 números aleatórios, com valores entre 0 e 99:

>>> lista_aleatoria = random.sample(range(0, 100), 10)

Obtendo o maior elemento de uma lista:

>>> lista = range(0, 10)
>>> print max(lista)
9

O menor:

>>> print min(lista)
0

Pegando somente os elementos de índice par:

>>> print lista[::2]
[0, 2, 4, 6, 8]

Os de índice ímpar:

>>> print lista[1::2]
[1, 3, 5, 7, 9]

Somando todos os elementos de uma lista:

>>> print sum([1, 2, 3, 4])
10

Juntando duas listas, formando pares de elementos:

>>> lista = zip(range(0, 5), range(5, 10))
>>> print lista
[(0, 5), (1, 6), (2, 7), (3, 8), (4, 9)]

Separando os elementos de uma lista de forma intercalada:

>>> lista = range(0, 10)
>>> intercaladas = lista[::2], lista[1::2]
>>> print intercaladas
([0, 2, 4, 6, 8], [1, 3, 5, 7, 9])

Transformando uma lista de strings em uma string CSV:

>>> lista = ["ola", "mundo", "aqui", "estamos"]
>>> csv_values = ','.join(lista)
>>> print csv_values
ola,mundo,aqui,estamos

Aplicando uma função (neste caso, anônima) a todos elementos de uma lista:

>>> lista = range(1, 11)
>>> print map(lambda x: x*-1, lista)
[-1, -2, -3, -4, -5, -6, -7, -8, -9, -10]

Filtrando os elementos de uma lista de acordo com um critério:

>>> def criterio(x): return x >= 0
>>> print range(-5, 5)
[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4]
>>> print filter(criterio, range(-5, 5))
[0, 1, 2, 3, 4]

Retirando os elementos cujo valor é zero (ou melhor, cujo valor é avaliado como False):

>>> print filter(None, range(-2, 2))
[-2, -1, 1]

E você, tem alguma dica que poderia ser inserida aqui no post? Poste sua sugestão nos comentários.

Hoje percebi que o blog já tratou sobre listas, dicionários, tuplas; mas até agora não escrevi texto algum sobre os conjuntos (também conhecidos por sets).

Sets: o que são?

Sets (ou, como iremos chamar daqui para a frente, conjuntos) são estruturas disponíveis como builtins do Python, utilizadas para representar coleções desordenadas de elementos únicos. É importante sempre lembrar dos conjuntos por suas duas principais características:

1. Os elementos não são armazenados em uma ordem específica e confiável;
2. Conjuntos não contém elementos repetidos.

A característica número 1 é importante, porque o desenvolvedor jamais deve confiar na ordenação de um conjunto, visto que a ordem em que os elementos são mantidos nos conjuntos varia de implementação para implementação do interpretador Python. Não é a toa que conjuntos não suportam indexação nem fatiamento (slicing). Bom, chega de papo e vamos ver alguns exemplos de conjuntos.

Mãos na massa

Vamos começar definindo um conjunto, usando a sintaxe para literais de conjuntos (introduzida há pouco tempo nas versões 3.1 e 2.7):

>>> s = {1, 2, 3, 4}
>>> print s
set([1, 2, 3, 4])

Existem várias operações disponíveis nos conjuntos através de métodos, como as operações mais conhecidas de teoria dos conjuntos, como união, interseção e diferença.

União

A U B (Crédito da imagem: Wikipedia)

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> print a.union(b)
set([1, 2, 3, 4, 5, 6])

Interseção

A ∩ B (Crédito da imagem: Wikipedia)

>>> print a.intersection(b)
set([3, 4])

Essa operação é muito útil quando precisamos descobrir elementos que duas listas possuem em comum:

>>> l1 = [1, 2, 3]
>>> l2 = [2, 4, 3]
>>> print set(l1).intersection(l2)
set([2, 3])

Perceba que convertemos l1 para conjunto para podermos usar o método intersection; já l2 não precisou ser convertida, pois esses métodos exigem que apenas o primeiro argumento seja um conjunto. Poderíamos obter o resultado da interseção como uma lista também:

>>> l3 = list(set(l1).intersection(l2))
>>> print l3
[2, 3]

O método intersection não modifica os conjuntos recebidos como parâmetro. Se quisermos que o resultado da interseção seja gravado como novo valor do primeiro conjunto, ao invés de retornar o novo conjunto como resultado, podemos usar o método intersection_update:

>>> a.intersection_update(b)
>>> print a
set([2, 3])

Diferença

B \ A (Crédito da imagem: Wikipedia)

A diferença entre dois conjuntos A e B retorna somente os elementos de A que não estão em B, ou seja, retira de A todos os elementos comuns a ambos os conjuntos:

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> print a.difference(b)
set([1, 2])
>>> print b.difference(a)
set([5, 6])

Observe que a.difference(b) é o mesmo que a \ b e que b.difference(a) é o mesmo que b \ a.

Assim como o método anterior, difference também não altera o conjunto sobre o qual é chamado. Para alterá-lo, é necessário usar o método difference_update().

Diferença simétrica

Diferença simétrica é uma operação sobre os dois conjuntos, que retorna todos os elementos (de ambos os conjuntos a e b) que pertencem a somente um dos conjuntos.

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> print a.symmetric_difference(b)
set([1, 2, 5, 6])

A △ B (Crédito da imagem: Wikipedia)

Pertinência

Além das operações tradicionais de união, interseção e diferença, também temos operações de verificação de pertinência. A seguir veremos algumas.

Para verificar se um determinado elemento pertence a um conjunto, podemos usar o já conhecido operador de pertinência in:

>>> a = {1, 2, 3, 4}
>>> b = {3, 4, 5, 6}
>>> 1 in a
True
>>> 5 in a
False

Também podemos verificar se um conjunto é um subconjunto de outro:

>>> a = {1, 2, 3, 4}
>>> c = {1, 2}
>>> c.issubset(a)
True
>>> a.issubset(c)
False

Além disso, podemos verificar se um conjunto é superconjunto de outro:

>>> a.issuperset(c)
True

Outra relação importante que podemos checar é a disjunção entre dois conjuntos. Dois conjuntos são disjuntos se tiverem interseção nula. Exemplo:

>>> c = {1, 2}
>>> d = {3, 4}
>>> c.isdisjoint(d)
True

Removendo elementos duplicados de uma sequência

Por definição, um conjunto é uma coleção de valores únicos (e desordenados). Assim sendo, se passarmos ao construtor de conjuntos uma lista com valores repetidos, esses valores serão eliminados de forma a permanecer apenas um deles. Exemplo:

>>> lista = [1, 1, 2, 3, 5, 8]
>>> conjunto = set(lista)
>>> print conjunto
set([8, 1, 2, 3, 5])

Ou, se quisermos ter de volta uma lista:

>>> lista = list(set(lista))

ATENÇÃO: a operação acima pode (e, com grandes chances, irá) bagunçar a lista. Ou seja, a ordem original irá se perder.

>>> print lista
[8, 1, 2, 3, 5]

Leia mais

• Documentação oficial

lista = ['algumas', 'palavras', '', 'e', 'nada', 'mais', '']
lista = filter(None, lista)
# lista fica: ['algumas', 'palavras', 'e', 'nada', 'mais']

Legal, não? Pois é, isso está na documentação da função:

filter(function, iterable)
Construct a list from those elements of iterable for which function returns true. iterable may be either a sequence, a container which supports iteration, or an iterator. If iterable is a string or a tuple, the result also has that type; otherwise it is always a list. If function is None, the identity function is assumed, that is, all elements of iterable that are false are removed.

Note that filter(function, iterable) is equivalent to [item for item in iterable if function(item)] if function is not None and [item for item in iterable if item] if function is None.

. . .

Ou seja, se passarmos None como valor para o parâmetro function, filter irá retornar uma nova lista contendo somente os elementos da lista original que não forem avaliados como False.

Filas

Tenho certeza que você já sabe como uma fila funciona. Pense na fila que você pega toda vez que vai ao supermercado. Para que você seja atendido, é preciso que todas as pessoas que estiverem na sua frente na fila sejam atendidas ou desistam para que você seja atendido, certo? Por isso, podemos dizer que a idéia da fila é que o último a entrar na fila seja o último a sair.

                                     _________
                                    | o caixa |
------------------------------------|_________|
 o    ~o    @    &     Q    0    O     0
/|\    []  {0\  /|\   /|\  /||  /-\   /0|
/ \    |\   |\  / \    |\  /|   |-|   / \
você   p6   p5  p4     p3  p2    p1   p0
-------------------------------------------

No exemplo acima, é preciso que p0, p1, p2, p3, p4, p5 e p6 sejam atendidas para que seja a sua vez de passar as compras e pagar por elas. Uma estrutura de dados Fila funciona da mesma maneira. Uma fila é uma estrutura utilizada especificamente para armazenamento temporário de dados na memória. Diferentemente de uma lista, que também serve para esse fim, uma fila possui regras quanto a qual elemento será retirado e onde será inserido um novo elemento. Em uma lista, é possível inserir elementos em qualquer posição e retirar quaisquer elementos, não importando sua posição. Em uma fila, os novos elementos que são inseridos são sempre posicionados ao final dela. Quando se faz a retirada de um elemento de uma fila, sempre iremos retirar o elemento que há mais tempo está nela (o primeiro). Imagine um servidor Webque é capaz de atender a, no máximo, 2 requisições simultâneas. O que acontece quando chega uma terceira requisição no momento em que o servidor já está ocupado atendendo a 2 requisições? A solução mais óbvia seria colocar a nova requisição em uma área de espera. Assim, quando o servidor terminar de atender uma das atuais 2 requisições, ele poderá retirar a nova requisição da área de espera e atendê-la. E se, enquanto o servidor estiver ocupado atendendo a 2 requisições, chegarem em sequência 5 novas requisições?

   ______              
  |  r0  |       [ r6  r3]
  |  r1  |       [  r5   ]
  |______|       [r4  r2 ]
    /  \  
Servidor Web    Área de espera

O servidor poderia colocar as novas requisições em uma área de espera, e sempre que houver disponibilidade, retirar uma de lá e processá-la, até que não hajam mais requisições a serem processadas. A solução é boa, mas para ser justo com as solicitações que chegam dos usuários, o servidor deve processar primeiro as que já estão esperando há mais tempo, correto? Assim, o melhor a se fazer é utilizar uma filapara armazenar as requisições que estão em espera.

        ______    
       |  r0  |           
       |  r1  |      saída  -----------------------  entrada
       |______|      <----   r2  r3  r4  r5  r6     <------
         /  \               -----------------------
     Servidor Web                 Fila de espera

Dessa forma, a requisição que está há mais tempo esperando é a primeira a sair da fila quando o servidor tiver disponibilidade.

Implementando uma fila

Uma fila nada mais é do que uma estrutura de armazenamento com políticas de ordem de entrada e saída de elementos. Assim, ela pode ser implementada usando uma lista, por exemplo. Como poderíamos fazer? Sabemos que as listas oferecem alguns métodos conhecidos para inserção/remoção de elementos:

• .append(elemento): adiciona elemento ao final da lista;
• .insert(índice, elemento): insere elemento após a posição índice;
• .pop(índice): remove e retorna o elemento contido na posição índice.

Para inserir elementos, podemos usar o método append(), que insere um elemento ao final de uma lista. Para a retirada de elementos, podemos utilizar o método pop(x), que retira e retorna um elemento da posição x. Em se tratando de uma fila em que estamos inserindo elementos no final, de qual posição devemos retirar os elementos? Acertou quem pensou “da primeira”. Isso mesmo vamos remover o primeiro elemento utilizando pop(0). Veja:

>>> fila = [10, 20, 30, 40, 50]
>>> fila.append(60)  # insere um elemento no final da fila
>>> print fila
[10, 20, 30, 40, 50, 60]
>>> print fila.pop(0) # remove o primeiro elemento da lista
10
>>> print fila
[20, 30, 40, 50, 60]
>>> print fila.pop(0) # remove o primeiro elemento da lista
20
>>> print fila
[30, 40, 50, 60]
>>> print fila.pop(0) # remove o primeiro elemento da lista
30
>>> print fila
[40, 50, 60]

Você deve estar se perguntando: “e se eu fizesse o contrário, inserindo no início e removendo do final, funcionaria também como uma fila?” Sim, funcionaria. Pois, da mesma forma, teríamos a política do primeiro a entrar, primeiro a sair também conhecida como First-In, First-Out, ou simplesmente FIFO. Agora, para criar uma forma consistente de usar filas em Python, vamos criar uma classe para encapsular as operações da fila. Podemos definir uma classe Filaque internamente tenha uma lista representando o local onde serão armazenados os elementos. Essa classe deverá ter dois métodos principais:

• insere(elemento): recebe como entrada um elemento a ser inserido na fila.
• retira(): remove um elemento da fila e o retorna para o chamador.

Complete a implementação de fila abaixo, de acordo com o que foi explicado acima. O código completo se encontra no final deste texto, para que você possa comparar.

class Fila(object):
    def __init__(self):
        self.dados = []

    def insere(self, elemento):
        __________________________________

    def retira(self):
        __________________________________

Tendo a classe acima definida em um arquivo fila.py, poderíamos importar o módulo e usar tal classe:

>>> import fila
>>> f = fila.Fila()
>>> f.insere(10)
>>> f.insere(20)
>>> f.insere(30)
>>> print f.retira()
10
>>> print f.retira()
20

Importante: segundo a própria documentação oficial Python, uma lista não é a estrutura mais recomendada para a implementação de uma fila, porque a inserção ou remoção de elementos do início da lista é lenta, se comparada à inserção/remoção do final da lista. Assim, é sugerido que seja usado um deque (collections.deque).

Só isso?

Não, nós vimos apenas as filas “comuns”. Voltando ao exemplo da fila do supermercado, imagine que você está chegando aos caixas e ainda não decidiu qual deles vai usar. Aí você vê que o caixa de atendimento preferencial para idosos/gestantes/deficientes possui apenas 3 pessoas na fila, enquanto que os outros caixas têm filas com no mínimo 10 pessoas. Como o caixa não é exclusivo para idosos, você vai lá e entra na fila. Outras pessoas percebem a sua “sagacidade” (:P) e fazem o mesmo. Fica tudo certo até que chega um idoso para entrar na fila e todas as pessoas que estão na fila são obrigados a ceder sua vez para o idoso. E eis que chega o clube da terceira idade inteiro para ser atendido logo em seguida. O que acontece? As pessoas que estão na fila cedem sua vez para os idosos, e assim, seu atendimento vai sendo postergado cada vez mais. Enfim, esse é um exemplo de uma fila de prioridades. Elementos (as pessoas) que possuem maior prioridade, saem antes da fila. Se quiser saber mais, veja aqui.

Pilhas

Assim como as filas, aposto que você sabe exatamente como funciona uma pilha. Pense em uma pilha de papéis sobre uma mesa. Se você precisar adicionar um papel a essa pilha, você o adiciona sobre a pilha, ou seja, no topo dela, certo? E quando vai retirar um papel da pilha, você começa pelo que estiver no topo, certo? Ou seja, diferentemente da fila (FIFO), em uma pilha o último a entrar nela, é o primeiro a sair (Last-In, First-Out — LIFO). Veja abaixo uma ilustração de como funciona uma pilha. No primeiro item da ilustração (1), temos uma pilha composta por 5 elementos, que foram inseridos cronologicamente na seguinte ordem: p0, p1, p2, p3, e, por fim, p4. A segunda parte da ilustração (2) mostra o estado da pilha p após ter sido realizada a inserção de um novo elemento (p5). A terceira parte (3) mostra a pilha p após haver a retirada de um elemento. Como você pode ver, o elemento retirado foi o último a ter sido inserido (p5). Na última parte da ilustração (4), é apresentada mais uma retirada de elemento da pilha, desta vez p4. Se houvessem mais operações de retirada, teríamos a retirada, em ordem, dos elementos: p3, p2, p1 e p0.

|          |    |----p5----|    |          |    |          |
|----p4----|    |----p4----|    |----p4----|    |          |
|----p3----|    |----p3----|    |----p3----|    |----p3----|
|----p2----|    |----p2----|    |----p2----|    |----p2----|
|----p1----|    |----p1----|    |----p1----|    |----p1----|
|----p0----|    |----p0----|    |----p0----|    |----p0----|
============    ============    ============    ============
  Pilha p       p.insere(p5)     p.retira()      p.retira()
    (1)             (2)              (3)            (4)

Tranquilo, né? O que você deve lembrar sobre as pilhas é que ela usa uma política LIFO (Last-In, First-Out) para inserção/retirada de elementos.

Onde as pilhas são usadas?

Talvez a mais famosa utilização de pilhas em computação esteja no gerenciamento de chamadas de função de um programa. Uma pilha pode ser usada para manter informações sobre as funções de um programa que estejam ativas, aguardando por serem terminadas. Considere o seguinte exemplo:

def ola():
    print "olá, "
    mundo()

def mundo():
    print "mundo!"

def olamundo():
    ola()

olamundo()

A primeira função a ser chamada é a olamundo(), que por sua vez chama a função ola(), então a função olamundo() é empilhada, pois seu término depende do término da função ola(). Essa, por sua vez, chama a função mundo() e é empilhada. Ao terminar a execução da função mundo(), a função ola() é desempilhada e sua execução termina de onde havia parado (chamada à função mundo()). Como não há mais nada a ser executado nessa função, sua execução termina, e a função olamundo()é desempilhada e sua execução continua, encerrando assim o programa.

                 ola()
olamundo()  -->  olamundo()  --> olamundo() -->   Fim do programa.

Outra utilização de pilhas é a verificação do balanceamento de parênteses. Como saber se os seguintes parênteses estão balanceados, isto é, se para cada abre-parênteses, existe um fecha-parênteses correspondente?

(((((((((((((((((()()()()))))))())))()))()))()))((()))))

Uma forma bem simples de resolver esse problema é ler a sequência de parênteses, um por um e, a cada abre-parênteses que encontrarmos, vamos empilhá-lo. Quando encontrarmos um fecha-parênteses, devemos desempilhar um abre-parênteses, pois encontramos um fecha-parênteses correspondente a ele. Assim, ao final da avaliação da sequência acima, se ela estiver balanceada corretamente, não restarão elementos na pilha. Vejamos um exemplo mais simples:

(())()

                (
Pilha       (   (   (       (

Leitura     (   (   )   )   (   )   FIM

Repare agora em uma sequência desbalanceada:

(())(

                (
Pilha       (   (   (       (   (

Leitura     (   (   )   )   (   FIM

Perceba que a leitura de parênteses da entrada terminou, mas a pilha não estava mais vazia.

Implementação

Agora eu lhe pergunto: o que muda da implementação da fila para a implementação da pilha? A diferença é pouca, mas é muito importante. Assim como para as filas, para a implementação de pilhas podemos utilizar uma lista como estrutura para armazenamento dos dados. Basta agora definir como será o funcionamento:

1. Iremos inserir e retirar elementos do início da lista?
2. Ou iremos inserir e retirar elementos do final da lista?

Sabendo que em Python a inserção e remoção de elementos no final de uma lista é menos custoso do que fazer as mesmas operações no início dela, vamos adotar a segunda opção. Então, complete o código abaixo e teste em seu computador.

class Pilha(object):
    def __init__(self):
        self.dados = []

    def empilha(self, elemento):
        __________________________________

    def desempilha(self):
        __________________________________

p = Pilha()
p.empilha(10)
p.empilha(20)
p.empilha(30)
p.empilha(40)
print p.desempilha(),
print p.desempilha(),
print p.desempilha(),
print p.desempilha(),

O programa acima, se implementado corretamente, deverá mostrar o seguinte resultado na tela:

40 30 20 10

Para adicionar um elemento no final de uma lista, basta usar o método append(). E para remover o último elemento da lista? .pop(tamanho_da_lista-1) é o que devemos fazer. E para obter o tamanho da lista, podemos usar a função len(). Então:

def desempilha(self):
    return self.dados.pop(len(dados)-1)

Ou então, podemos usar self.dados.pop(-1). O acesso ao índice -1é a forma pythônica de se referir ao último elemento de uma sequência.

def desempilha(self):
    return self.dados.pop(-1)

Mais alguma operação?

Outra operação fundamental que deve estar disponível em uma Pilha, é um método que retorne um booleano indicando se a pilha está vazia. Um jeito bem simples seria usando a builtin len() sobre a nossa lista interna self.dados e verificando se ela retorna 0como resultado.

def vazia(self):
    return len(self.dados) == 0

Finalizando…

Tanto a fila quanto a pilha são estruturas importantes pra caramba e sua implementação deve fornecer um bom desempenho, visto que elas são amplamente usadas nos programas que compõem o nosso dia-a-dia. As implementações vistas aqui nesse post possuem fins didáticos apenas. Embora funcionem de forma adequada para serem utilizadas, elas não utilizam os recursos mais adequados para obter o melhor desempenho. Para usar na prática, existem soluções prontas e muito mais recomendadas, como por exemplo o módulo python queue, que pode ser usado tanto para implementação de Filas quanto para a implementação de Pilhas.

Códigos completos

Abaixo, seguem os códigos completos para a Fila e para a Pilha.

Fila

class Fila(object):
    def __init__(self):
        self.dados = []

    def insere(self, elemento):
        self.dados.append(elemento)

    def retira(self):
        return self.dados.pop(0)

    def vazia(self):
        return len(self.dados) == 0

Pilha

class Pilha(object):
    def __init__(self):
        self.dados = []

    def empilha(self, elemento):
        self.dados.append(elemento)

    def desempilha(self):
        if not self.vazia():
            return self.dados.pop(-1)

    def vazia(self):
        return len(self.dados) == 0

map() é uma função builtin de Python, isto é, uma função que é implementada diretamente no interpretador Python, podendo ser utilizada sem a importação de um módulo específico. Essa função, em Python, serve para aplicarmos uma função a cada elemento de uma lista, retornando uma nova lista contendo os elementos resultantes da aplicação da função. Considere o exemplo abaixo:

>>> import math
>>> lista1 = [1, 4, 9, 16, 25]
>>> lista2 = map(math.sqrt, lista1)
>>> print lista2
[1.0, 2.0, 3.0, 4.0, 5.0]

Ao chamar a função map(math.sqrt, lista1), estamos solicitando ao interpretador para que execute a função math.sqrt (raiz quadrada – square root) usando como entrada cada um dos elementos de lista1, e inserindo o resultado na lista retornada como resultado da função map().

É uma forma bem interessante e expressiva de denotar a aplicação de uma função a cada elemento de uma lista (ou sequência). Mas, podemos facilmente substituir uma chamada a map() por list comprehensions. O código recém listado poderia ser substituído por:

>>> lista2 = [math.sqrt(x) for x in lista1]
>>> print lista2
[1.0, 2.0, 3.0, 4.0, 5.0]

O código acima produz o mesmo resultado que map(), pois, para cada elemento de lista1, executa a função math.sqrt e inclui o resultado dessa execução na lista de retorno.

O fato de a função map() ser tão facilmente substituída pelo uso de comprehensions, já criou até mesmo algumas discussões sobre manter ou não map() entre as funções builtin do Python 3000 [1].

reduce()

reduce() é outra função builtin do Python (deixou de ser builtin e passou a estar disponível no módulo functools a partir da versão 3000). Sua utilidade está na aplicação de uma função a todos os valores do conjunto, de forma a agregá-los todos em um único valor. Por exemplo, para aplicar a operação de soma a todos os elementos de uma sequência, de forma que o resultado final seja a soma de todos esses elementos, poderíamos fazer o seguinte:

>>> import operator #necessário para obter a função de soma
>>> valores = [1, 2, 3, 4, 5]
>>> soma = reduce(operator.add, valores)
>>> print soma
15

É claro que, para realizar a soma de todos os elementos de uma sequência, é muito mais claro utilizarmos a função sum():

>>> print sum(valores)
15

Como falei anteriormente, reduce() foi retirada do conjunto de builtins de Python, em parte devido à obscuridade que pode acabar gerando [1].

filter()

Como o próprio nome já deixa claro, filter() filtra os elementos de uma sequência. O processo de filtragem é definido a partir de uma função que o programador passa como primeiro argumento da função. Assim, filter() só “deixa passar” para a sequência resultante aqueles elementos para os quais a chamada da função que o usuário passou retornar True. Vejamos um exemplo:

>>> def maior_que_zero(x):
...     return x > 0
...
>>> valores = [10, 4, -1, 3, 5, -9, -11]
>>> print filter(maior_que_zero, valores)
[10, 4, 3, 5]

No exemplo acima, filter() chamou a função maior_que_zero para cada um dos elementos contidos em valores. Se a função retornar True, o elemento é inserido na lista de resultado. Caso contrário, não o é. Ou seja, é feita a filtragem e só passam aqueles elementos que são maiores que zero.

Assim, como no exemplo da builtin map(), aqui também podemos escrever com facilidade uma comprehension com a mesma funcionalidade:

>>> print [x for x in valores if x > 0]
[10, 4, 3, 5]

Devido a essa fácil substituição, filter() também já esteve na mira para ser retirada do conjunto de builtins, embora tenha acabado permanecendo.

lambda

No exemplo da função filter(), tivemos que definir uma nova função (chamada maior_que_zero) para usar somente dentro da função filter(), sendo chamada uma vez para cada elemento. Ao invés de definir uma nova função dessa forma, poderíamos definir uma função válida somente enquanto durar a execução do filter. Não é necessário nem dar um nome a tal função, sendo portanto chamada de função anônima ou função lambda. Considere o exemplo abaixo:

>>> valores = [10, 4, -1, 3, 5, -9, -11]
>>> print filter(lambda x: x > 0, valores)
[10, 4, 3, 5]

Definimos uma função anônima (portanto, não tem nome), que recebe uma entrada (a variável x) e retorna o resultado da operação x > 0, True ou False.

Poderíamos também usar uma função lambda no exemplo da função reduce():

>>> valores = [1, 2, 3, 4, 5]
>>> soma = reduce(lambda x, y: x + y, valores)
>>> print soma
15

No código acima, definimos uma função anônima que recebe duas entradas e retorna a soma dessas entradas.

[1] Guido Van Rossum. The fate of reduce() in Python 3000

int i;
for (i = 0; i < 10; i++) {
        // código a ser repetido
}

O código é bastante claro:

Para i, cujo valor inicial é 0 (i = 0), repita a execução do código que está entre { e } enquanto o valor de i for menor que 10 (i < 10), e ao final de cada execução do código entre { e } incremente o valor de i em uma unidade (i++).

Temos três declarações bem explícitas em nosso for:

1. O que vai ser executado inicialmente, antes de começarmos a execução da repetição em si (setup);
2. O que vai ser verificado antes de cada repetição, para decidir se o código fará ou não mais uma repetição (condição);
3. O que vai ser executado ao final de cada uma das repetições que forem executadas.

Em Python, como usamos o for?

for i in range(0, 10):
        # código a ser repetido

E aí? Cadê o valor inicial de i? Cadê a condição? Cadê a instrução que altera o valor de i ao final de cada repetição?

Antes de mais nada, precisamos entender o que faz a função range() isoladamente. Abra um console Python e faça o teste:

>>> range(0, 10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>

Isso mesmo, range(x, y) gera e retorna uma lista de números de x até y, sem incluir o y. Vamos confirmar então:

>>> l = range(0, 10)
>>> type(l)
<type 'list'>

Agora que sabemos que range() gera e retorna uma lista de números, vamos voltar à questão do for. Poderíamos então reescrever o for da seguinte forma:

for i in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
    # código a ser repetido

Esse código poderia ser lido como:

Para cada elemento da lista de números, faça algo (o código a ser repetido).

Assim, em um primeiro momento, o valor de i será o valor do primeiro elemento da lista (0). Então, o código a ser repetido é executado e o valor de i passa a ser o valor do próximo elemento da lista, se houver próximo, caso contrário, encerra a repetição. No caso do exemplo, i passa a ter o valor 1. Então o código a ser repetido é executado e os passos anteriores são repetidos até que não existam mais elementos na lista.

A sequẽncia de passos também poderia ser descrita como:

1. O valor de i é setado para o valor do primeiro elemento da lista (valor 0).
2. O código a ser repetido é executado.
3. O valor de i passa a se o valor do elemento seguinte da lista, se houver um próximo elemento. Se não houver, encerra a execução do for. Se houver, volta ao passo 2, com o valor de i já atualizado.

Tudo parece meio automágico, não? Mas não é. Só podemos fazer isso com as listas porque elas são iteráveis (iterables). Objetos desse tipo retornam um elemento seu de cada vez, permitindo esse mecanismo automático do for. Veja o que o glossário da documentação Python [1] fala sobre Iterable:

iterable

An object capable of returning its members one at a time. Examples of iterables include all sequence types (such as list, str, and tuple) and some non-sequence types like dict and file and objects of any classes you define with an __iter__() or __getitem__() method. Iterables can be used in a for loop and in many other places where a sequence is needed (zip(), map(), …). When an iterable object is passed as an argument to the built-in function iter(), it returns an iterator for the object. This iterator is good for one pass over the set of values. When using iterables, it is usually not necessary to call iter() or deal with iterator objects yourself. The for statement does that automatically for you, creating a temporary unnamed variable to hold the iterator for the duration of the loop. See also iterator, sequence, and generator.

Espero que o “for i in range(x, y):” tenha ficado mais claro, principalmente para aqueles que, assim como eu, aprenderam programação com uma linguagem na qual a estrutura do for é diferente.

[1] http://docs.python.org/glossary.html

l = ['hello', 'world', 'hi', 'earth']
for word in l:
    print word

Outra forma de fazermos uma travessia em uma lista é através do acesso via índices.

l = ['hello', 'world', 'hi', 'earth']
for i in range(0, len(l)):
    print l[i]

O que é semelhante a:

l = ['hello', 'world', 'hi', 'earth']
i = 0
while i < len(l):
    print l[i]
    i = i + 1

Qual é a diferença básica entre os dois últimos códigos (que utilizam for i in range e while) para o primeiro trecho de código apresentado? É o acesso ao índice, à posição do elemento na lista. Utilizando a estrutura for elem in, não sabemos qual é a posição do item atual. Isso poderia ser necessário, por exemplo, se precisarmos escrever uma função que retorne uma lista contendo os índices das palavras que começam pelo caractere ‘a‘.

Para contornar esse problema, existe a função enumerate(). Essa função pode receber como entrada uma lista e irá retornar um objeto do tipo enumerate, que poderá ser percorrido pelo for. Vejamos um exemplo simples:

l = ['hello', 'world', 'hi', 'earth']
for i, word in enumerate(l):
    print i, word

Isso irá gerar a seguinte saída:

0 hello
1 world
2 hi
3 earth

E se quisermos escrever a função que retorna uma lista contendo as posições das palavras de uma lista que começam com a letra ‘a’?

def posicoesQueIniciamCom(lista, letra='a'):
    result = []
    for i, palavra in enumerate(lista):
        if palavra.startswith(letra):
            result.append(i)
    return result

nomes = ['abc', 'hua', 'aaa', 'asdfg', 'bnm']
print posicoesQueIniciamCom(nomes)

O resultado da execução do código acima será:

[0, 2, 3]

Assim, sempre que precisarmos dos índices dos elementos das listas (ou outros iteráveis) que estivermos percorrendo, podemos utilizar a função enumerate() para construir uma estrutura composta por pares índice-elemento.