# 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)
```
python的基本數據結構
* a container 容器
* an iterable 可疊代的對象
* an iterator 疊代器
* a generator 生成器
* a generator expression
* a {list, set, dict} comprehension 串列綜合表達式
## 容器 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)
```
這裡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
```
因此其實際上的情況為：
## 疊代器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/)
Sign in with Wallet
Connect another wallet