List comprehension and Generator Expressions

Python language has several interesting features. In this post, let's talk about two features: List comprehension and generator expressions.

List comprehension is a syntactic construct that allows creation of lists very similar to the way of defining sets in set theory. In set theory, we can define a set through a property that characterizes its  elements .

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

In Python, we can define a list with the same elements of S as follows:

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

This way of defining the list allows you to implement algorithms more clear and direct. The quicksort algorithm can be defined as follows:

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

From a list, we can create two lists: lesser and greater. The lesser list is formed by  elements smaller than the pivot .  The last list is formed by elements greater than the pivot. These two lists are sorted recursively and then are joined again. 


The version dynamic choice of pivot can be easily set as follows: 

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

Code: http://ideone.com/5mtoj 

import random
 import time
 quick import from qsort, qsortrand

 numElements = int (raw_input ("Enter array size:")) 
 testlist = random. sample (xrange (999999999), numElements)
 q is in qsort, qsortrand:
     print "# elements:% d"% numElements
     testlist list = [:]
     start = time. clock ()
     result = q (list)
     elapsed = (time. clock () - start)
     print "% .3 f secs"% (elapsed)

Test Results: 

	100	1000	10000
qsort	0001 secs	0008 secs	0043 secs
qsortrand	0001 secs	0011 secs	0052 secs

Although it is a good idea to use list comprehension have some problems with performance and efficient use of memory. So, the Python language introduced the concept of generators and generator expressions.

In some cases, experience shows that need not have all the list created in memory. We just need to know to iterate over the elements one by one. To perform the sum of all numbers in a certain range does not need the entire range created a priori.Consider the following example: 

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

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

Result: 
499999500000 
0340 secs 
499999500000 
0224 secs 

The semantics of a generator expression is that the elements are generated when needed. 

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

 Output
 1
 2
 3

The semantics of an  generating  expression is equivalent to  anonymous  generating  function  using  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 t of 
 A
 2
 3

An interesting example is to use the generating expression to make a program that displays the Fibonacci numbers less than 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

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