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
