[ Python 文章收集 ] Iterators & Generators

Source From Here
Iterators
We use for statement for looping over a list:

view plaincopy to clipboardprint?

1. >>> for i in [1,2,3,4]:  
2. ...     print i,  
3. ...  
4. 1 2 3 4  

If we use it with a string, it loops over its characters:

view plaincopy to clipboardprint?

1. >>> for c in 'python':  
2. ...     print c  
3. ...  
4. p  
5. y  
6. t  
7. h  
8. o  
9. n  

If we use it with a dictionary, it loops over its keys:

view plaincopy to clipboardprint?

1. >>> for k in {"x": 1, "y": 2}:  
2. ...     print k  
3. ...  
4. y  
5. x  

If we use it with a file, it loops over lines of the file:

view plaincopy to clipboardprint?

1. >>> for line in open("a.txt"):  
2. ...     print line,  
3. ...  
4. first line  
5. second line  

So there are many types of objects which can be used with a for loop. These are called iterable objects.

There are many functions which consume these iterables:

view plaincopy to clipboardprint?

1. >>> ",".join(["a", "b", "c"])  
2. 'a,b,c'  
3. >>> ",".join({"x": 1, "y": 2})  
4. 'y,x'  
5. >>> list("python")  
6. ['p', 'y', 't', 'h', 'o', 'n']  
7. >>> list({"x": 1, "y": 2})  
8. ['y', 'x']  

The Iteraton Protocol
The built-in function iter takes an iterable object and returns an iterator.

view plaincopy to clipboardprint?

1. >>> x = iter([1, 2, 3])  
2. >>> x  
3. 0x1004ca850>  

>>> x.next()  

1  

>>> x.next()  

2  

>>> x.next()  

3  

>>> x.next()  

Traceback (most recent call last):  

  File "", line 1, in   

StopIteration  

Each time we call the next method on the iterator gives us the next element. If there are no more elements, it raises a StopIteration.

Iterators are implemented as classes. Here is an iterator that works like built-in xrange function.

view plaincopy to clipboardprint?

1. class yrange:  
2.     def __init__(self, n):  
3.         self.i = 0  
4.         self.n = n  
5.   
6.     def __iter__(self):  
7.         return self  
8.   
9.     def next(self):  
10.         if self.i < self.n:  
11.             i = self.i  
12.             self.i += 1  
13.             return i  
14.         else:  
15.             raise StopIteration()  

The __iter__ method is what makes an object iterable. Behind the scenes, the iter function calls __iter__ method on the given object. The return value of __iter__is an iterator. It should have a next method and raise StopIteration when there are no more elements:

view plaincopy to clipboardprint?

1. >>> y = yrange(3)  
2. >>> y.next()  
3. 0  
4. >>> y.next()  
5. 1  
6. >>> y.next()  
7. 2  
8. >>> y.next()  
9. Traceback (most recent call last):  
10.   File "", line 1, in   
11.   File "", line 14, in next  
12. StopIteration  

Many built-in functions accept iterators as arguments.

view plaincopy to clipboardprint?

1. >>> list(yrange(5))  
2. [0, 1, 2, 3, 4]  
3. >>> sum(yrange(5))  
4. 10  

In the above case, both the iterable and iterator are the same object. Notice that the __iter__ method returned self. It need not be the case always.

view plaincopy to clipboardprint?

1. class zrange:  
2.     def __init__(self, n):  
3.         self.n = n  
4.   
5.     def __iter__(self):  
6.         return zrange_iter(self.n)  
7.   
8. class zrange_iter:  
9.     def __init__(self, n):  
10.         self.i = 0  
11.         self.n = n  
12.   
13.     def __iter__(self):  
14.         # Iterators are iterables too.  
15.         # Adding this functions to make them so.  
16.         return self  
17.   
18.     def next(self):  
19.         if self.i < self.n:  
20.             i = self.i  
21.             self.i += 1  
22.             return i  
23.         else:  
24.             raise StopIteration()  

If both iteratable and iterator are the same object, it is consumed in a single iteration.

>>> y = yrange(5)
>>> list(y)
[0, 1, 2, 3, 4]
>>> list(y)
[]
>>> z = zrange(5)
>>> list(z)
[0, 1, 2, 3, 4]
>>> list(z)
[0, 1, 2, 3, 4]

Problem 1: Let's practice what we learn so far. Please write an iterator class reverse_iter, that takes a list and iterates it from the reverse direction.

view plaincopy to clipboardprint?

1. >>> it = reverse_iter([1, 2, 3, 4])  
2. >>> it.next()  
3. 4  
4. >>> it.next()  
5. 3  
6. >>> it.next()  
7. 2  
8. >>> it.next()  
9. 1  
10. >>> it.next()  
11. Traceback (most recent call last):  
12.   File "", line 1, in   
13. StopIteration  

Answer1: 

view plaincopy to clipboardprint?

1. class reverse_iter:  
2.     def __init__(self, list):  
3.         self.data = list  
4.           
5.     def __iter__(self):  
6.         return rIter(self.data)  
7.           
8. class rIter:  
9.     def __init__(self, list):  
10.         self.data = list  
11.         self.i = len(list)  
12.           
13.     def next(self):  
14.         self.i=self.i-1  
15.         if self.i >= 0:              
16.             return self.data[self.i]  
17.         else:  
18.             raise StopIteration()  
19.       
20.       
21. ri = reverse_iter([1,2,3,4,5])  
22. for i in ri:  
23.     print i,  
24. print ""  
25.   
26. ri = reverse_iter("Hello")      
27. for i in ri:  
28.     print i,  

Execution result:

5 4 3 2 1
o l l e H

Generators
Generators simplifies creation of iterators. A generator is a function that produces a sequence of results instead of a single value. For example:

view plaincopy to clipboardprint?

1. def yrange(n):  
2.     i = 0  
3.     while i < n:  
4.         yield i  
5.         i += 1  

Each time the yield statement is executed the function generates a new value.

view plaincopy to clipboardprint?

1. >>> y = yrange(3)  
2. >>> y  
3. 0x401f30>  

>>> y.next()  

0  

>>> y.next()  

1  

>>> y.next()  

2  

>>> y.next()  

Traceback (most recent call last):  

  File "", line 1, in   

StopIteration  

So a generator is also an iterator. You don’t have to worry about the iterator protocol.

The word “generator” is confusingly used to mean both the function that generates and what it generates. In this chapter, I’ll use the word “generator” to mean the genearted object and “generator function” to mean the function that generates it.

Can you think about how it is working internally?

When a generator function is called, it returns an generator object without even beginning execution of the function. When next` method is called for the first time, the function starts executing until it reaches yield statement. The yielded value is returned by the next call.

The following example demonstrates the interplay between yield and call to next method on generator object:

view plaincopy to clipboardprint?

1. >>> def foo():  
2. ...     print "begin"  
3. ...     for i in range(3):  
4. ...         print "before yield", i  
5. ...         yield i  
6. ...         print "after yield", i  
7. ...     print "end"  
8. ...  
9. >>> f = foo()  
10. >>> f.next()  
11. begin  
12. before yield 0  
13. 0  
14. >>> f.next()  
15. after yield 0  
16. before yield 1  
17. 1  
18. >>> f.next()  
19. after yield 1  
20. before yield 2  
21. 2  
22. >>> f.next()  
23. after yield 2  
24. end  
25. Traceback (most recent call last):  
26.   File "", line 1, in   
27. StopIteration  
28. >>>  

Lets see an example:

view plaincopy to clipboardprint?

1. def integers():  
2.     """Infinite sequence of integers."""  
3.     i = 1  
4.     while True:  
5.         yield i  
6.         i = i + 1  
7.   
8. def squares():  
9.     for i in integers():  
10.         yield i * i  
11.   
12. def take(n, seq):  
13.     """Returns first n values from the given sequence."""  
14.     seq = iter(seq)  
15.     result = []  
16.     try:  
17.         for i in range(n):  
18.             result.append(seq.next())  
19.     except StopIteration:  
20.         pass  
21.     return result  
22.   
23. print take(5, squares()) # prints [1, 4, 9, 16, 25]  

Generator Expressions
Generator Expressions are generator version of list comprehensions. They look like list comprehensions, but returns a generator back instead of a list:

>>> a = (x*x for x in range(10))
>>> a
<generator object  at 0x7ffea13ae3c0>
>>> sum(a)
285

When there is only one argument to the calling function, the parenthesis around generator expression can be omitted:

>>> sum(x*x for x in range(10))
285

Another fun example, lets say we want to find first 10 (or any n) pythogorian triplets. A triplet (x, y, z) is called pythogorian triplet if x*x + y*y == z*z.

It is easy to solve this problem if we know till what value of z to test for. But we want to find first n pythogorian triplets:

>>> pyt = ((x, y, z) for z in integers() for y in xrange(1, z) for x in range(1, y) if x*x + y*y == z*z)
>>> take(10, pyt)
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20), (15, 20, 25), (7, 24, 25), (10, 24, 26), (20, 21, 29)]

Example: Reading multiple files
Lets say we want to write a program that takes a list of filenames as arguments and prints contents of all those files, like cat command in unix. The traditional way to implement it is:

view plaincopy to clipboardprint?

1. def cat(filenames):  
2.     for f in filenames:  
3.         for line in open(f):  
4.             print line,  

Now, lets say we want to print only the line which has a particular substring, like grep command in unix:

view plaincopy to clipboardprint?

1. def grep(pattern, filenames):  
2.     for f in filenames:  
3.         for line in open(f):  
4.             if pattern in line:  
5.                 print line,  

Both these programs have lot of code in common. It is hard to move the common part to a function. But with generators makes it possible to do it.

view plaincopy to clipboardprint?

1. def readfiles(filenames):  
2.     for f in filenames:  
3.         for line in open(f):  
4.             yield line  
5.   
6. def grep(pattern, lines):  
7.     return (line for line in lines if pattern in lines)  
8.   
9. def printlines(lines):  
10.     for line in lines:  
11.         print line,  
12.   
13. def main(pattern, filenames):  
14.     lines = readfiles(filenames)  
15.     lines = grep(pattern, lines)  
16.     printlines(lines)  

The code is much simpler now with each function doing one small thing. We can move all these functions into a separate module and reuse it in other programs.
Problem 2: Write a program that takes one or more filenames as arguments and prints all the lines which are longer than 40 characters.
Answer 2:

view plaincopy to clipboardprint?

1. import random, string  
2.   
3. def readfiles(filenames):  
4.     for f in filenames:  
5.         for line in f:  
6.             yield line  
7.               
8.               
9. def printlines(lines):  
10.     for line in lines:  
11.         print("{0} ({1})".format(line, len(line)))  
12.           
13. # Generate testing random files          
14. filenames = []  
15. for i in range(10): # Generate 10 temple files  
16.     f=[]  
17.     for j in range(random.randint(10,20)):  
18.         f.append(''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(random.randint(30,50))))  
19.     filenames.append(f)  
20.   
21. lines = readfiles(filenames)  
22. u40=(line for line in lines if len(line)>40)  
23. printlines(u40)  

Problem 3: Write a function to compute the number of python files (.py extension) in a specified directory recursively.
Answer 3:

view plaincopy to clipboardprint?

1. import random, string, os  
2. from os.path import *  
3. from os import listdir  
4.   
5. def traverse_file(file):  
6.     if isfile(file):  
7.         yield abspath(file)          
8.     elif isdir(file):  
9.         yield "{0} (dir)".format(file)               
10.         for f in listdir(file):              
11.             f = "{0}\{1}".format(file, f)              
12.             for sf in traverse_file(f):  
13.                 yield sf  
14.     else:  
15.         yield abspath(file)    
16.   
17. def num_of_pyfile(path):  
18.     tf = traverse_file(path)  
19.     pylist = [f for f in tf if f.endswith(".py")]  
20.     for py in pylist: print py  
21.     return len(pylist)  
22.           
23. print "Total {0} .py files!".format(num_of_pyfile("C:\\John\\EclipseBase\\PyLab"))  

Problem 4: Write a function to compute the total number of lines of code in all python files in the specified directory recursively.

Problem 5: Write a function to compute the total number of lines of code, ignoring empty and comment lines, in all python files in the specified directory recursively.

Problem 6: Write a program split.py, that takes an integer n and a filename as command line arguments and splits the file into multiple small files with each having n lines.

Itertools
The itertools module in the standard library provides lot of intersting tools to work with iterators. Lets look at some of the interesting functions.
chain – chains multiple iterators together.

view plaincopy to clipboardprint?

1. >>> it1 = iter([1, 2, 3])  
2. >>> it2 = iter([4, 5, 6])  
3. >>> itertools.chain(it1, it2)  
4. [1, 2, 3, 4, 5, 6]  

izip – iterable version of zip

view plaincopy to clipboardprint?

1. >>> for x, y in itertools.izip(["a", "b", "c"], [1, 2, 3]):  
2. ...     print x, y  
3. ...  
4. a 1  
5. b 2  
6. c 3  

Problem 8: Write a function peep, that takes an iterator as argument and returns the first element and an equivalant iterator.

view plaincopy to clipboardprint?

1. >>> it = iter(range(5))  
2. >>> x, it1 = peep(it)  
3. >>> print x, list(it1)  
4. 0 [0, 1, 2, 3, 4]  

Problem 9: The built-in function enumerate takes an iteratable and returns an iterator over pairs (index, value) for each value in the source.

view plaincopy to clipboardprint?

1. >>> list(enumerate(["a", "b", "c"])  
2. [(0, "a"), (1, "b"), (2, "c")]  
3. >>> for i, c in enumerate(["a", "b", "c"]):  
4. ...     print i, c  
5. ...  
6. 0 a  
7. 1 b  
8. 2 c  

Write a function my_enumerate that works like enumerate.

Problem 10: Implement a function izip that works like itertools.izip.

Supplement
* Python Gossip - yield 產生器
* Python: List Comprehensions