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

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

Nenhum comentário: