---
# System prepended metadata

title: python Iterator and generator
tags: [iterable, generator, python, iterator]

---

# python Iterator and generator
> Lee Tsung-Tang
{%hackmd @88u1wNUtQpyVz9FsQYeBRg/r1vSYkogS %}
###### tags: `python` `iterator` `generator` `iterable`

疊代器這個概念在很多語言中（比如 C++，Java）都是存在的，但是不同語言實現疊代器的方式各不相同。在 Python 中，疊代器是指遵循疊代器協議（iterator protocol）的對象。


## 疊代的範例

Iterating with a for loop
```python=
employees = ['Nick', 'Lore', 'Hugo'] 
for employee in employees: 
    print(employee)
```
![](https://i.imgur.com/gqdCSGu.png)

python的基本數據結構
* a container 容器
* an iterable 可疊代的對象
* an iterator 疊代器
* a generator 生成器
* a generator expression 
* a {list, set, dict} comprehension 串列綜合表達式

![](https://i.imgur.com/SJr3IjN.png)

## 容器 containers
容器是一種把多個元素組織在一起的數據結構，容器中的元素可以逐個地迭代獲取，可以用in, not in關鍵字判斷元素是否包含在容器中。通常這類數據結構把所有的元素存儲在內存中（也有一些特例，並不是所有的元素都放在內存，比如迭代器和生成器對象）在Python中，常見的容器對像有：
* list, deque, …
* set, frozensets, …
* dict, defaultdict, OrderedDict, Counter, …
* tuple, namedtuple, …
* str
簡單來說，可以把containers想成是一個盒子(box)，從技術角度來說，當它可以用來詢問某個元素是否包含在其中時，那麼這個對象就可以認為是一個容器，比如 list，set，tuples都是容器對象：
```python=
assert 1 in [1, 2, 3]      # lists
assert 4 not in [1, 2, 3]
assert 1 in {1, 2, 3}      # sets
assert 4 not in {1, 2, 3}
assert 1 in (1, 2, 3)      # tuples
assert 4 not in (1, 2, 3
```
dict: 檢查dict的key是否包含某元素:
```python=
d = {1: 'foo', 2: 'bar', 3: 'qux'}
assert 1 in d
assert 4 not in d
assert 'foo' not in d  # 'foo' is not a _key_ in the dict
```
str:
```python=
s = 'foobar'
assert 'b' in s
assert 'x' not in s
assert 'foo' in s  # a string "contains" all its substrings
```
NOTE:
儘管絕大多數容器都提供了某種方式來獲取其中的每一個元素，但這並不是容器本身提供的能力，而是可迭代對象賦予了容器這種能力，當然並不是所有的容器都是可迭代的，比如：Bloom filter，雖然Bloom filter可以用來檢測某個元素是否包含在容器中，但是並不能從容器中獲取其中的每一個值，因為Bloom filter壓根就沒把元素存儲在容器中，而是通過一個散列函數映射成一個值保存在數組中。

## 可疊代對象iterable
很多容器都是可迭代對象，此外還有更多的對象同樣也是可迭代對象，比如處於打開狀態的files，sockets等等。但凡是可以返回一個迭代器的對像都可稱之為可疊代對象

可疊代對象的精準定義為：*含有 __iter__() 方法或 __getitem__() 方法的對象稱之為可疊代對象*
```python=
x = [1, 2, 3]
y = iter(x)
z = iter(x)
next(y)  # 1
next(y)  # 2
next(z)  # 1
type(x) 
type(y)
```
![](https://i.imgur.com/jZsA6uJ.png)
這裡x是一個可疊代對象，可疊代對象和容器一樣是一種通俗的叫法，並不是指某種具體的數據類型，list是可疊代對象，dict是可疊代對象，set也是可疊代對象。 y和z是兩個獨立的疊代器，疊代器內部持有一個狀態，該狀態用於記錄當前疊代所在的位置，以方便下次疊代的時候獲取正確的元素。疊代器有一種具體的疊代器類型，比如list_iterator，set_iterator。可疊代對象實現了__iter__方法，該方法(method)返回一個疊代器對象。
當code為：
```python=
for x in [1, 2, 3]:
    print i
```
等價於：
```python=
# 獲得 Iterator 對象 
it = iter([1, 2, 3]) 
# 循環 
while True:     
    try:         
        # 獲得下一個值         
        x = next(it)         
        print x     
    except StopIteration:         
    # 沒有後續元素，退出循環         
        break
```
因此其實際上的情況為：
![](https://i.imgur.com/vnAvHzv.png)

## 疊代器iterator
疊代器是一個帶狀態的對象，他能在你調用next()方法的時候返回容器中的下一個值，任何實現了__iter__和__next__()方法的對像都是疊代器，\__iter__返回疊代器自身，\__next__返回容器中的下一個值，如果容器中沒有更多元素了，則拋出StopIteration error。所以，疊代器就是實現了工廠模式的對象，它在你每次詢問要下一個值的時候給你返回。有很多關於疊代器的例子，比如itertools函數返回的都是疊代器對象。

生成無限序列：
```python=
from itertools import count
counter = count(start=13)
next(counter)   # 13
next(counter)   # 14
```
從一個有限序列中生成無限序列：
```python=
>>> from itertools import cycle
>>> colors = cycle(['red', 'white', 'blue'])
>>> next(colors)
'red'
>>> next(colors)
'white'
>>> next(colors)
'blue'
>>> next(colors)
'red'
```
從無限的序列中生成有限序列：
```python=
>>> from itertools import islice
>>> colors = cycle(['red', 'white', 'blue'])  # infinite
>>> limited = islice(colors, 0, 4)            # finite
>>> for x in limited:                         
...     print(x)
red
white
blue
red
```
為了更直觀地感受疊代器內部的執行過程，我們自定義一個疊代器，以斐波那契數列為例：
```python=
class Fib:
    def __init__(self):
        self.prev = 0
        self.curr = 1
        
    # 返回疊代器對象本身
    def __iter__(self):
        return self
    
    # 返回容器下一個元素
    def __next__(self):
        value = self.curr
        self.curr += self.prev
        self.prev = value
        return value

>>> f = Fib()
>>> list(islice(f, 0, 10))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
```
Fib既是一個可疊代對象（因為它實現了__iter__方法），又是一個疊代器（因為實現了__next__method）。實例變量prev和curr用以維護疊代器內部的狀態。每次調用next()方法的時候做兩件事： 
1. 為下一次調用next()方法修改狀態
2. 為當前這次調用生成返回結果

疊代器就像一個懶加載的工廠，等到有人需要的時候才給它生成值返回，沒調用的時候就處於休眠狀態等待下一次調用。

Python中的迭代器協議和 for 循環是緊密相連的：
```python=
# iterator protocol and for loop
for x in something:
    print(x)
```
Python 處理 for 循環時，首先會調用內建函數 iter(something)，它實際上會調用 something.\_\_iter__()，返回 something 對應的迭代器。而後，for 循環會調用內建函數 next()，作用在迭代器上，獲取迭代器的下一個元素，並賦值給 x。此後，Python 才開始執行循環

## 生成器generator
生成器其實是一種特殊的迭代器，不過這種疊代器更加優雅。它不需要再像上面的類一樣寫__iter__()和__next__()方法了，只需要一個yiled關鍵字。生成器一定是疊代器（反之不成立），因此任何生成器也是以一種懶加載的模式生成值。用生成器來實現斐波那契數列的例子是：
```python=
def fib():
    prev, curr = 0, 1
    while True:
        yield curr
        prev, curr = curr, curr + prev

>>> f = fib()
>>> list(islice(f, 0, 10))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
```
fib就是一個普通的python函數，它特殊的地方在於函數體中沒有return關鍵字，函數的返回值是一個生成器對象。表面上看來，yield就像是return會傳回值，但又不中斷函式的執行。當執行f=fib()返回的是一個生成器對象，此時函數體中的代碼並不會執行，只有顯示或隱示地調用next的時候才會真正執行里面的代碼。

實際上，在def所定義的本體中，若包括yield運算式，則Python會將之編譯為一個產生器（Generator）。例如：
```python=
>>> dir(f)
['__class__',
 '__del__',
 '__delattr__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__init_subclass__',
 '__iter__',
 '__le__',
 '__lt__',
 '__name__',
 '__ne__',
 '__new__',
 '__next__',
 '__qualname__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 'close',
 'gi_code',
 'gi_frame',
 'gi_running',
 'gi_yieldfrom',
 'send',
 'throw']
```
產生器物件是個具有迭代器（Iterator）介面的物件，也就是說，它具有__next__()方法，可以使用next()函式來取出下一個值，若無法產生下一個值，則會丟出StopIteration物件。

生成器在Python中是一個非常強大的編程結構，可以用更少地中間變量寫流式代碼，此外，相比其它容器對象它更能節省內存和CPU，當然它可以用更少的代碼來實現相似的功能。現在就可以動手重構你的代碼了，但凡看到類似：
```python=
def something():
    result = []
    for ... in ...:
        result.append(x)
    return result
```
可以用生成器改寫為：
```python=
def iter_something():
    for ... in ...:
        yield x
```
例如：
```python=
def square():
    for x in range(4):
        yield x ** 2
square_gen = square()
>>> for x in square_gen:
...    print(x)
0
1
4
9
```
前面說到，for 循環會調用 iter() 函數，獲取一個生成器；而後調用 next() 函數，將生成器中的下一個值賦值給 x；再執行循環體。因此，上述 for 循環基本等價於：
```python=
genitor = square_gen.__iter__()
while True:
    try:
        x = genitor.__next__()
        print(x)
    except:
        print('End')
        break
```
注意到，square 是一個生成器函數；作為它的返回值，square_gen 已經是一個迭代器；迭代器的 \_\_iter__() 返回它自己。因此 geniter 對應的生成器函數，即是 square。

每次執行到```x = genitor.__next__()``` 時，square 函數會從上一次暫停的位置開始，一直執行到下一個yield 表達式，將yield 關鍵字後的表達式列表返回給調用者，並再次暫停。注意，每次從暫停恢復時，生成器函數的內部變量、指令指針、內部求值棧等內容和暫停時完全一致。

## 生成器表達式generator expression
生成器表達式是[列表推導式list comprehensions](https://hackmd.io/IzkdbWIkSmy8uRzPpiTjzg)的生成器版本，看起來像list comprehensions，但是它返回的是一個生成器對象而不是列表對象
```python=
>>> a = (x*x for x in range(10))
>>> a
<generator object <genexpr> at 0x401f08>
>>> sum(a)
285
```

## 總結
1. 容器是一系列元素的集合，str、list、set、dict、file、sockets對像都可以看作是容器，容器都可以被迭代（用在for，while等語句中），因此他們被稱為可迭代對象。 
2. 1. 可迭代對象實現了`__iter__`方法，該方法返回一個迭代器對象。 
3. 迭代器持有一個內部狀態的字段，用於記錄下次迭代返回值，它實現了`__next__`和`__iter__`方法，迭代器不會一次性把所有元素加載到內存，而是需要的時候才生成返回結果。 
4. 生成器是一種特殊的迭代器，它的返回值不是通過```return```而是用```yield```。

## 參考資料
[迭代器 (Iterator)](https://wiki.jikexueyuan.com/project/explore-python/Advanced-Features/iterator.html)
[完全理解Python迭代对象、迭代器、生成器](https://foofish.net/iterators-vs-generators.html)
[yield產生器](https://openhome.cc/Gossip/Python/YieldGenerator.html)
[Python 中的黑暗角落（一）：理解 yield 关键字](https://liam.page/2017/06/30/understanding-yield-in-python/)