Usando List Comprehension

Diferente do meu costume, esse post vai ser mais curto, só pra fixar alguns conceitos e formalizar algumas coisas que eu tenho usado mais frequentemente nos últimos tempos.

Como entusiasta da linguagem Python, tento extrair ao máximo as facilidades que a linguagem me proporciona. Todo mundo que conhece mesmo que seja um pouquinho sabe que uma das grandes vantagens da linguagem são as funções built in que proporcionam, entre outras muitas facilidades, uma simplificação do tratamento de listas.

Trabalhar com listas em Python é extremamente simples (pra quem já usou a STL do C++ sabe bem o trabalho que uma lista pode nos dar!). Mas quando eu comecei a trabalhar com a linguagem (há uns três anos), eu carregava comigo muitos vícios providos dos meus muitos anos programando em C e C++. Veja no exemplo abaixo, o que eu cheguei a fazer no meu início pela linguagem:

vetor []
cont = 0
while cont < 10:
    vetor.append(cont)
    cont += 1

Bem, não precisa ser nenhum sênior na linguagem pra ver que a construção anterior é completamente, digamos, não-pythônica. Isso poderia ser facilmente substituido por um:

vetor = range(10)

Enfim, antes que alguém pense que isso é um post sobre como usar listas em Python (não, isso não um post sobre isso. Caso queira aprender mais sobre o assunto eu sugiro este texto aqui), vamos ao que eu quero falar hoje: List Comprehension.

Em Teoria dos Conjuntos nós temos algumas notações que nos permitem criar conjuntos de elementos, como por exemplo

é  a representação do conjunto de todos os elementos reais maiores que zero, ou seja, todos números reais positivos. Ou por exemplo o conjunto dado por

que é composto por todos os números naturais pares.

De certa maneira, a função Python vetor=range(10) pode ser escrita na notação de conjuntos por

ou seja, k pertence aos naturais e k é menor que 10.

List Comprehension é uma maneira de trazer para a linguagem de programação a notação de conjuntos. Um set de elementos criados por uma list comprehension obedece uma série de parâmetros previamente estipulados. Esses parâmetros têm como princípo impor condições para o nosso set de elementos, a fim de compor, baseado em regras, a nossa lista. Não expliquei nada né?? Então vamos por exemplos. Imagine uma set S que é dada por:

Assim, temos que S é composto por todos os elementos x pertencentes aos números naturais, tal que X<20. Porém, apareceu mais um componente aí na minha lista. Esse componente que aparece antes do pipe é a saída da minha função, ou seja, para cada valor de x que existir, ele inluirá no meu set o valor 2*x. A expressão do exemplo anterior pode ser dividida nos seguintes elementos:

De um forma simplificada, podemos dizer que dado um conjunto de entrada, a variável denotada recebe cada elemento deste conjunto que atende à condição imposta pelo predicado (ou seja, nesse caso, verificar se a variável retirada do conjunto é menor que 20). Uma vez atribuído um valor à variável, é aplicado a essa variável a função de saída, que dá o valor que será colocado na minha list. Simples não? Então qual seria o resultado de S ? Todos os números naturais, menores que 20 e multiplicados por 2…

Ok, muito interessante mas… como coloco isso no código? Se estivessemos falando de linguagem C pura (a qual eu aprendi a programar, e carreguei muitos vícios por muito tempo), o nosso código ficaria parecido com:

int i;
int *v = (int*)malloc(sizeof(int)*20);
for(i=0; i<20; i++)
    v[i] = 2*i;

Programadores em geral costumam carregar vícios, costumes que aprenderam em outras linguagens. Se eu fosse escrever o código anterior em Python nas primeiras semanas em que comecei a aprender a linguagem eu provavelmente não estaria tirando o máximo da linguagem, mas sim simplesmente transcrevendo uma lógica em código.

Escrevendo esse mesmo código, agora em Python, e usando list comprehension teríamos:

S = [2*i for i in range(20)]

O leitor pode facilmente identificar os elementos citados anteriormente no código Python. Por exemplo, o pipe | foi substituído pela cláusula for enquanto o símbolo pertence foi substituído pela cláusula in. Como a função range já nos devolve os números naturais menores que 20, não foi necessário utilizar a cláusula do predicado, mas caso isso seja necessário, basta adicionar um comparador à variável com um if ao final da sentença. Mostrando por exemplos, que fica mais fácil, digamos que em algum momento hipotético possuamos uma lista com os seguintes valores:

S = [2,5,7,98,108]

e desejamos selecionar apenas os valores menores que 50. Para isso podemos fazer:

K = [x for x in S if x < 50]

Note que nesse exemplo o meu conjunto de dados de entrada é a própria lista S, e assim aplicamos um filter no nosso conjunto de elementos. Ora pois, para este fim é mais viável utilizar realmente a função built-in filter que nos dará o mesmo resultado. Mas se repararmos bem, uma list comprehension nada mais é que um gerador de lista que compreende também uma função filter além de uma função map em sua construção. Com essas duas utilidades, você pode, ao construir uma lista, filtrar os dados que você deseja e aplicar alguma função à lista.

Aplicando list comprehension

Uma aplicação que eu achei bem legal de se fazer com list comprehension é a implementação do algoritmo Quick Sort. Apenas para relembrar o funcionamento do algoritmo (caso precise de mais detalhes dê um pulo em alguma referência mais completa), o algoritmo basicamente consiste em estipular um pivot que é um elemento aleatório do meu set e separar este set em dois grupos: um contendo todos os elementos maiores que o meu pivot e outro contendo os elementos menores. Uma vez feito isso, a função é chamada recursivamente para cada sub-set de elementos.

Como list comprehension nos permite facilmente filtrar os elementos de uma lista, criando assim uma nova lista, se eu quiser, por exemplo, selecionar todos os elementos x da minha lista que são maiores que um valor pivot (ou também selecionar os elementos que são menores) eu poderia proceder da seguinte forma:

K = [8, 4, 1, 2, 3, 9, 6, 5, 7] #vetor com elementos dispostos em ordem aleatória
pivot = k.pop() #remove um elemento aleatório de K
less_than_pivot = [x for x in K if x < pivot]
greater_than_pivot = [x for x in K if x > pivot]

Agora bastaria eu chamar recursivamente esta função para os sub-sets obtidos, e concactenar os resultados. O código final ficaria da seguinte forma:

def qsort(v): return [] if v == [] else qsort([x for x in v if x < v[0]]) + [v[0]] \
    + qsort([y for y in v if y > v[0]])

if __name__ == "__main__":
    K = [4, 5, 3, 7, 6, 1, 2, 9, 8]
    print qsort(K)

Poh, legal, bacana, então quer dizer que apenas o Python implementa list comprehension não é? Na verdade várias outras linguagens (principalmente linguagens de alto nível) implementam esta função. O mesmo código acima pode ser implementado, por exemplo, em Erlang usando list comprehension:

-module(sort).
-export([quick/1]).
quick([]) ->
    [];
quick([Pivot|Rest]) ->
    quick([X || X <- Rest, X < Pivot]) ++ [Pivot] ++ quick([Y || Y <- Rest, Y >= Pivot]).

Como podem ver, list comprehension podem nos ajudar em várias ocasiões, basta conhecer um pouco mais as funcionalidades que cada linguagem nos provê, e saber quando usá-las.

Complexidade Algorítmica na Prática 2 – Recursões

Depois do post sobre complexidade algorítmica, algumas pessoas me perguntaram como resolver quando o algoritmo é recursivo. Bem, eu me lembrei imediatamente do livro Concrete Mathematics do Donald Knuth. Este livro traz um capítulo que trata somente de recursões, trazendo junto algumas ferramentas que facilitam nossa vida na hora de analizar a complexidade de uma função recursiva.

Então, baseando nas soluções dadas por Knuth, vamos analizar aqui dois casos clássicos de recursão:

Torre de Hanoy

Um algoritmo clássico e que está presente na maioria dos cursos de computaçãp/programação quando é apresentado ao aluno o conceito de recursão é o algoritmo que resolve o problema da Torre de Hanoy.  Esse algoritmo é usado em cursos de computação devido a sua extrema simplicidade e facilidade de compreensão por parte do estudante.

A sua idéia básica é enxergar a torre de discos como duas torres distintas: uma sub-torre formada por n-1 elementos e uma segunda torre formada pelo n-ésimo (último) disco. Assim devemos mover esta sub-torre para uma casa auxiliar, mover o n-ésimo elemento para o destino e, por fim, mover a sub torre da casa auxiliar para a casa de destino. Cada sub-torre pode ser enxergada como uma nova torre, e aplicada, recursivamente, o mesmo algoritmo, até que cheguemos a uma torre com n=1 elementos. O código a seguir ilustra a sequência de passos necessária para se resolver o problema da torre de Hanoy:

def hanoy(n, origem, destino, aux):
    if n== 1:
        print "Mova disco %i de %c para %c" % (n, origem, destino)
    else:
        hanoy(n-1, origem, aux, destino)
        print "Mova disco %i de %c para %c" % (n, origem, destino)
        hanoy(n-1, aux, destino, origem)
if __name__=="__main__":
    hanoy(3, "A", "C", "b")    #exemplo de como usar

Como eu disse anteriormente, a simplicidade desse código é um dos grandes atrativos para se ensinar recursão.

Porém aqui a nossa questão é outra (tanto porque estamos assumindo que todo leitor que deseja aferir a complexidade de um algoritmo que utilize recursão domine essa técnica). A nossa pergunta é: Qual a complexidade temporal desse algoritmo, ou em outras palavras, A medida que eu aumento a quantidade n de disco, em quanto eu aumento o tempo T(n) de execução do meu código?

A primeira solução, e a mais simples possível, é a aferição empírica: coloco uma variável contanto o número de chamadas que a minha função têm e traço um gráfico da relação número-de-discos X número-de-movimentos:

Uma coisa podemos aferir com total certeza sobre o comportamento deste gráfico: a função que ele representa não é linear! Mas, enfim, qual a função que representa a complexidade deste algorítmo?

Todo algoritmo recursivo tem uma característica comum: um ponto de final de execução. Para a função da torre de Hanoy, o fim da execução é dado para sempre que n=1, assim temos que:

ou

Agora analizemos como se comporta o algoritmo para n=2. Primeiramente o código vai chamar a função (de forma recursiva) para n=1 [linha #5], essa entrada da função faz um movimento [linha #3] e, saindo da função, fazemos mais um movimento [linha #6] e novamente chamamos a função de forma recursiva [linha #7]. Essa segunda chamada recursiva também vai passar como parâmetro o valor n=1, assim mais uma vez será feito um movimento [linha #3, dentro da chamada segunda chamada].

Resumindo, para n=2 fizemos duas chamadas recursivas [linhas #5 e #7]. Como em cada chamada um movimento é feito, temos aí dois movimentos dentro das chamadas recursivas. Além desses dois movimentos, um terceiro movimento é executado entre as chamadas das linha #5 e #7. Assim temos um total de 3 movimentos, ou:

Generalizando a quantidade de movimentos para n=2 temos que ele realiza 1 movimento, mais duas vezes a qauntidade de movimentos para n=1 (devido as duas chamadas recursivas). Assim temos:

Generalizando para qualquer valor de n temos:

Ótimo, retiramos assim a relação da quantidade de movimentos pela quantidade de discos existente no problema. Mas há um porém: e se eu quiser saber quantos movimentos são necessários para mover uma torre com 64 discos por exemplo? Teríamos que calcular , com isso obter e assim por diante até . Um tanto braçal não? Agora imagine que desejamos procurar para um n ainda maior? Assim precisamos colocar essa equação em sua forma fechada:

Por enquanto temos:

Somando 1 em cada lado da equação temos:

Assim podemos dizer que:

Que por extensão também é válido dizer:

Da segunda equação temos:

Assim:

Que por fim nos dá:

Depois de toda essa manipulação ainda não temos uma forma fechada que solucione o nosso problema, mas perceba agora que a relação entre um elemento e o seu antecessor é dada pelo dobro do antecessor. Parafraseando o Donald Knuth: Não é preciso ser nenhum gênio para notar que

Como

Temos então que:

Que, por fim, nos dá a complexidade temporal do algoritmo:

Sim, a ordem do nosso algoritmo é exponencial. Isso explica o porque do nosso gráfico explodir para valores [nem tão] elevados de n.

Recordadno os passos que fizemos para chegar ao resultado, primeiro nós encontramos o ponto de parada do algoritmo, em seguida aferimos quantos movimentos [aqui figurado como o nosso custo] são feitos para o caso mais simples (n=1). A partir disso encontramos a solução iterativa do custo computacional do nosso algoritmo. Com a solução iterativa em mãos, lançamos mão de técnicas de manipulação para encontrar a forma fechada da função que corresponde ao seu custo. E assim chegamos finalmente na complexidade relacionada ao método.

Perceba que por momentos lançamos mão de induções para chegar a forma fechada da solução.

Algoritmo de Ordenação QuickSort

Um outro algoritmo que é muito estudado pelos iniciantes de computação é a solução de ordenação Quick Sort. Existem pelo menos dois bons motivos para se estudar o Quick Sort: 1 – ele é um algoritmo bastante eficiente de ordenação, 2 – é um algoritmo relativamente simples de se implementar e de entender e 3 – é mais uma oportunidade de se mostrar o funcionamento de recursão, desta vez em um algoritmo que é bastante usado em diversas aplicações.

A idéia básica do quicksort está em subdividir os valores do set de elementos a serem ordenados em duas partes: uma inferior a um valor denominado pivo e outra maior que este valor. Em seguida, o set de valores é disposto de uma maneira em que os valores a direita deste pivot sejam de valor inferior a ele, e os a esquerda de valor superior. Por fim a função é novamente chamada (de forma recursiva, note) para estes dois grupos de elementos. Note aí a recursão, que é o nosso alvo neste momento (para mais informações sobre o funcionamento do algoritmo Quick Sort consulte seu livro de algoritmos preferido!).

Existem várias maneiras de se aferir a complexidade de um algoritmo como esse. Vamos apresentar duas, cada uma assumindo certas particularidades na implementação do algoritmo.

Solução #1:

Como no primeiro exemplo (Hanoy) vamos primeiramente estipular qual seria o custo para um valor n trivial. Assim, não é difícil enxergar que:

Neste caso, o primeiro custo é, dado o pivo, fazer a partição do meu set de dados em duas partes. Ora, dado um conjunto de n valores, para dividi-lo em duas partes eu preciso fazer até n+1 comparações:

Como o valor do pivo pode ser qualquer um dos elementos do set, temos que estimar a média de todas as possibilidades de partições possíveis. Por exemplo, se o meu set contém 10 elementos, temos as seguintes opções de partição: (5,0),(1,4), (2,3), (3,2), (1,4) e (0,5). Note que cada uma dessas partições vai chamar, recursivamente, a função para cad um dos subsets criados. Cada um desses subsets têm um custo proporcional a quantidade de valores que ele contém. Assim temos que o valor médio entre todas as possibilidades é dada por:

Explicando um pouco melhor o que fizemos anteriormente, note que a quantidade de elementos de cada subset é que determina qual vai ser o custo de processar cada um destes. Emfim, tirando a média entre todas as possibilidades temos o valor médio do custo para todas as possibilidades.

Por fim, somando as duas partes temos que o custo C(n) para executar esse código é dado por:

Uhm, bacana, agora além de ser iterativo, temos um somatório aí dentro. Bem, vamos com calma. A primeira coisa a fazermos é retirar a recursão desta expressão. Para isto temos que sumir com a variável n dentro de C(n-k+1). Para isto vamos abrir o somatório para um valor dado de n como por exemplo n=3. Assim temos:

Uhm, agora ficou fácil. Perceba que cada elemento repete duas vezes, assim podemos simplificar para:

Que nos dá:

Retirando a constante 2 de dentro do somatório, e reescrevendo a função temos:

Bem, agora que conseguimos retirar a recursão que estava dentro do somatório, temos que dar um jeito de sumir com esse somatório. Vamos para isso tentar manipular a função a fim de tira-la. Multiplicamos primeiro ambos os lados por n:

Agora substituindo n por n-1:

Subtraindo uma pela outra a fim de eliminar o somatório:

Assim temos:

Voltando agora ao nosso querido Donald Knuth, no livro Concrete Mathematics ele nos passa uma maneira de reduzir uma sentença da forma

em

[para mais detalhes sobre essa transformação vide o livro Concrete Mathematics, Donald Knuth, pág 27]

Assim, reescrevendo a nossa função nesta forma temos:

Mas somatório denovo??? Sim, mas note desta vez que não temos mais uma recursão dentro da nossa função. Note também que essa somatória tem uma cara de alguma série harmônica.

Assim, vamos manipular esse somatório para deixa-lo como uma série harmonica:

Da série harmônica temos que:

Assim, tomando apenas o elemento de maior índice (para conta da notação Big O):

Que, finalmente, nos dá:

Solução #2:

Depois de provarmos matematicamente a ordem deste algoritmo, ficamos mais a vontade de inferir uma análize um pouco menos formal. Vamos analizar agora com base apenas no fluxo do algoritmo, sem demais formalidades.

Uma escolha aleatória do pivo divide em duas partes o nosso set de elementos. Supunhamos agora, num caso ótimo, que o elemento escolhido como pivo seja o elemento central. Assim dividimos o set em dois grupos de iguais quantidades. Dividindo constantemente cada subset em duas partes iguais, fica fácil calcular o número máximo de divisões que teríamos.

Por indução, suponha que nosso set tenho 32 elementos. Se seguirmos constantemente dividindo-o por dois temos: 1*32, 2*16, 4*8, 8*4, 16*2 e por fim 32*1. Note que o crescimento é similar a uma árvore binária, onde cada nó se divide em dois ramos, e o custo total é análogo a altura desta árvore.

Como a altura de uma árvore é dada, em aproximação livre, por , e sendo este valor análogo à quantidade de chamadas recursivas que o algoritmo irá fazer, e sendo também que, para cada chamada, toda a execução dentro da chamada é executada em O(n), temos:

Que, por fim, nos dá:

Assim concluimos a análize da complexidade de dois algoritmos recursivos. Espero que tenha sido útil o post.