List comprehension e Generator Expressions

A linguagem Python possui diversos recursos interessantes. Nesse post, vamos falar de dois recursos: List comprehension e Generator Expressions.

List comprehension é uma construção sintática que permite a criação de lista muito parecida com a forma de definir conjuntos na teoria dos conjuntos. Na teoria de conjuntos, podemos definir um conjunto através de uma propriedade que caracteriza os seus elementos.

S = {2x | x Î N e 1<=x<=3}

Na linguagem Python, podemos definir uma lista com os mesmo elementos de S da seguinte maneira:

S = [2*x for x in range(1,4)]

Essa maneira de definir lista permite implementar algoritmos de maneira mais clara e direta. O algoritmo quicksort pode ser definido da seguinte maneira:

def qsort(list):
    if list == []: 
        return []
    else:
        pivot = list[0]
        lesser = qsort([x for x in list[1:] if x < pivot])
        greater = qsort([x for x in list[1:] if x >= pivot])
        return lesser + [pivot] + greater

A partir de uma lista, podemos criar duas listas: lesser e greater. A lista lesser é formada pelos elementos menores que o pivô e a lista greater formada pelos elementos maiores que o pivô. Essas duas listas são ordenadas recursivamente e depois são unidas novamente.


A versão com escolha do pivô dinâmica pode ser definida facilmente da seguinte maneira:

from random import randrange 
def qsortrand(list):
    if list == []: 
        return []
    else:
        pivot = list.pop(randrange(len(list)))
        lesser = qsortrand([l for l in list if l < pivot])
        greater = qsortrand([l for l in list if l >= pivot])
        return lesser + [pivot] + greater

Código: http://ideone.com/5mtoj

import random
import time
from quick import qsort, qsortrand

numElements = int( raw_input("Entre com o tamanho do vetor:") ) 
testlist = random.sample(xrange(999999999), numElements)
for q in qsort, qsortrand:
    print "# elements: %d"%numElements
    list = testlist[:]
    start = time.clock()
    result = q(list)
    elapsed = (time.clock() - start)
    print "%.3f secs"%(elapsed)

Resultados dos Testes:

	100	1000	10000
qsort	0.001 secs	0.008 secs	0.043 secs
qsortrand	0.001 secs	0.011 secs	0.052 secs

Apesar de ser uma boa ideia, o uso de list comprehension têm alguns problemas relacionados com perfomance e uso eficiente de memória. Então, a linguagem Python introduziu o conceito de expressões geradoras e geradores.

Em alguns casos, a experiência mostra que não precisamos ter toda a lista criada na memória. Precisamos apenas saber iterar sobre os elementos um por um. Para realizar a soma de todos os números em um certo intervalo não precisamos de todo o intervalo criado a priori. Considere o seguinte exemplo:

import time
start = time.clock()
#usando list compreenhension
print sum( [x for x in range(1,1000000)] ) 
elapsed = (time.clock() - start)
print "%.3f secs"%(elapsed)

start = time.clock()
#usando generator expression
print sum( x for x in range(1,1000000) )
elapsed = (time.clock() - start)
print "%.3f secs"%(elapsed)

Resultado:
499999500000
0.340 secs
499999500000
0.224 secs

A semântica de uma generator expression é que os elementos são gerados quando necessários.

g = ( x for x in range(1,1000000) )
print g.next() 
print g.next()
print g.next()

Saída
1
2
3

A semântica de uma expressão geradora é equivalente a uma função geradora anônima usando yield.

def __f(exp):
    for x in exp:
        yield x
        
g = __f(iter(range(1,1000000)))
print g.next()
print g.next()
print g.next()

Saída 
1
2
3

Um exemplo interessante é utilizar a expressão geradora para fazer um programa que exibe os números de Fibonacci menores que 100.

def fib():
    a,b = 0,1
    while 1:
        yield b
        a,b = b,a+b

for x in fib():
    if x < 100:
        print x