## sexta-feira, 13 de abril de 2012

### 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




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