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 xGreater = 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 lGreater 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:
Postar um comentário