Python迭代器的實(shí)現(xiàn)原理

更新時(shí)間：2022年05月11日 17:18:03 作者：??編程學(xué)習(xí)網(wǎng)????

這篇文章主要介紹了Python迭代器的實(shí)現(xiàn)原理，文章基于python的相關(guān)資料展開(kāi)對(duì)Python迭代器的詳細(xì)介紹，需要的小伙伴可以參考一下

前言：

在Python里面，只要類型對(duì)象實(shí)現(xiàn)了__iter__，那么它的實(shí)例對(duì)象就被稱為可迭代對(duì)象(Iterable)，比如字符串、元組、列表、字典、集合等等。而整數(shù)、浮點(diǎn)數(shù)，由于其類型對(duì)象沒(méi)有實(shí)現(xiàn)__iter__，所以它們不是可迭代對(duì)象。

from typing import Iterable
print(
    isinstance("", Iterable),
    isinstance((), Iterable),
    isinstance([], Iterable),
    isinstance({}, Iterable),
    isinstance(set(), Iterable),
)  # True True True True True

print(
    isinstance(0, Iterable),
    isinstance(0.0, Iterable),
)  # False False

可迭代對(duì)象的一大特點(diǎn)就是它可以使用for循環(huán)進(jìn)行遍歷，但是能被for循環(huán)遍歷的則不一定是可迭代對(duì)象。

我們舉個(gè)栗子：

class A:
    def __getitem__(self, item):
        return f"參數(shù)item: {item}"
a = A()
#內(nèi)部定義了 __getitem__
#首先可以讓實(shí)例對(duì)象像字典一樣訪問(wèn)屬性
print(a["name"])  # 參數(shù)item: name
print(a["satori"])  # 參數(shù)item: satori

# 此外還可以像可迭代對(duì)象一樣被for循環(huán)
# 循環(huán)的時(shí)候會(huì)自動(dòng)給item傳值，0 1 2 3...
# 如果內(nèi)部出現(xiàn)了StopIteration，循環(huán)結(jié)束
# 否則會(huì)一直循環(huán)下去。這里我們手動(dòng)break
for idx, val in enumerate(a):
    print(val)
    if idx == 5:
        break
"""
參數(shù)item: 0
參數(shù)item: 1
參數(shù)item: 2
參數(shù)item: 3
參數(shù)item: 4
參數(shù)item: 5
"""

所以實(shí)現(xiàn)了__getitem__的類的實(shí)例，也是可以被for循環(huán)的，但它并不是可迭代對(duì)象。

from typing import Iterable
print(isinstance(a, Iterable))  # False

打印的結(jié)果是 False。

總之判斷一個(gè)對(duì)象是否是可迭代對(duì)象，就看它的類型對(duì)象有沒(méi)有實(shí)現(xiàn)__iter__?？傻鷮?duì)象我們知道了，那什么是迭代器呢？很簡(jiǎn)單，調(diào)用可迭代對(duì)象的__iter__方法，得到的就是迭代器。

迭代器的創(chuàng)建

不同類型的對(duì)象，都有自己的迭代器，舉個(gè)栗子：

lst = [1, 2, 3]
#底層調(diào)用的其實(shí)是list.__iter__(lst)
#或者說(shuō)PyList_Type.tp_iter(lst)
it = lst.__iter__()
print(it)  # <list_iterator object at 0x000001DC6E898640>
print(
    str.__iter__("")
)  # <str_iterator object at 0x000001DC911B8070>
print(
    tuple.__iter__(())
)  # <tuple_iterator object at 0x000001DC911B8070>

迭代器也是可迭代對(duì)象，只不過(guò)迭代器內(nèi)部的__iter__返回的還是它本身。當(dāng)然啦，在創(chuàng)建迭代器的時(shí)候，我們更常用內(nèi)置函數(shù)iter。

lst = [1, 2, 3]
# 等價(jià)于 type(lst).__iter__(lst)
it = iter(lst)

但是iter函數(shù)還有一個(gè)鮮為人知的用法，我們來(lái)看一下：

val = 0
def foo():
    global val
    val += 1
    return val
# iter可以接收一個(gè)參數(shù): iter(可迭代對(duì)象)
# iter也可以接收兩個(gè)參數(shù): iter(可調(diào)用對(duì)象, value)
for i in iter(foo, 5):
    print(i)
"""
1
2
3
4
"""

進(jìn)行迭代的時(shí)候，會(huì)不停地調(diào)用接收的可調(diào)用對(duì)象，直到返回值等于傳遞第二個(gè)參數(shù)value，在底層被稱為哨兵，然后終止迭代。

我們看一下iter函數(shù)的底層實(shí)現(xiàn)：

static PyObject *
builtin_iter(PyObject *self, PyObject *const *args, Py_ssize_t nargs)
{
    PyObject *v;
  
    // iter函數(shù)要么接收一個(gè)參數(shù), 要么接收兩個(gè)參數(shù)
    if (!_PyArg_CheckPositional("iter", nargs, 1, 2))
        return NULL;
    v = args[0];
    //如果接收一個(gè)參數(shù)
    //那么直接使用 PyObject_GetIter 獲取對(duì)應(yīng)的迭代器即可
    //可迭代對(duì)象的類型不同，那么得到的迭代器也不同
    if (nargs == 1)
        return PyObject_GetIter(v);
    // 如果接收的不是一個(gè)參數(shù), 那么一定是兩個(gè)參數(shù)
    // 如果是兩個(gè)參數(shù), 那么第一個(gè)參數(shù)一定是可調(diào)用對(duì)象
    if (!PyCallable_Check(v)) {
        PyErr_SetString(PyExc_TypeError,
                        "iter(v, w): v must be callable");
        return NULL;
    }
    // 獲取value(哨兵)
    PyObject *sentinel = args[1];
    //調(diào)用PyCallIter_New
    //得到一個(gè)可調(diào)用的迭代器, calliterobject 對(duì)象
    /*
    位于 Objects/iterobject.c 中
    typedef struct {
        PyObject_HEAD
        PyObject *it_callable; 
        PyObject *it_sentinel; 
  } calliterobject;
    */
    return PyCallIter_New(v, sentinel);
}

以上就是iter函數(shù)的內(nèi)部邏輯，既可以接收一個(gè)參數(shù)，也可以接收兩個(gè)參數(shù)。這里我們只看接收一個(gè)可迭代對(duì)象的情況，所以核心就在于PyObject_GetIter，它是根據(jù)可迭代對(duì)象生成迭代器的關(guān)鍵，我們來(lái)看一下它的邏輯是怎么樣的？該函數(shù)定義在Objects/abstract.c中。

PyObject *
PyObject_GetIter(PyObject *o)
{  
    //獲取可迭代對(duì)象的類型對(duì)象
    PyTypeObject *t = Py_TYPE(o);
    //我們說(shuō)類型對(duì)象定義的操作，決定了實(shí)例對(duì)象的行為
    //實(shí)例對(duì)象調(diào)用的那些方法都是定義在類型對(duì)象里面的
    //還是那句話：obj.func()等價(jià)于type(obj).func(obj)
    getiterfunc f;
    //所以這里是獲取類型對(duì)象的tp_iter成員
    //也就是Python中的 __iter__
    f = t->tp_iter;
    //如果 f 為 NULL
    //說(shuō)明該類型對(duì)象內(nèi)部的tp_iter成員被初始化為NULL
    //即內(nèi)部沒(méi)有定義 __iter__ 
    //像str、tuple、list等類型對(duì)象，它們的tp_iter成員都是不為NULL的
    if (f == NULL) {
      //如果 tp_iter 為 NULL，那么解釋器會(huì)退而求其次
      //檢測(cè)該類型對(duì)象中是否定義了 __getitem__
      //如果定義了，那么直接調(diào)用PySeqIter_New
      //得到一個(gè)seqiterobject對(duì)象
      //下面的PySequence_Check負(fù)責(zé)檢測(cè)類型對(duì)象是否實(shí)現(xiàn)了__getitem__
      //__getitem__ 對(duì)應(yīng) tp_as_sequence->sq_item
        if (PySequence_Check(o))
            return PySeqIter_New(o);
        // 走到這里說(shuō)明該類型對(duì)象既沒(méi)有__iter__、也沒(méi)有__getitem__
        // 因此它的實(shí)例對(duì)象不具備可迭代的性質(zhì)，于是拋出異常
        return type_error("'%.200s' object is not iterable", o);
    }
    else {
        // 否則說(shuō)明定義了__iter__，于是直接進(jìn)行調(diào)用
        // Py_TYPE(o)->tp_iter(o) 返回對(duì)應(yīng)的迭代器
        PyObject *res = (*f)(o);
        // 但如果返回值res不為NULL、并且還不是迭代器
        // 證明 __iter__ 的返回值有問(wèn)題，于是拋出異常
        if (res != NULL && !PyIter_Check(res)) {
            PyErr_Format(PyExc_TypeError,
                         "iter() returned non-iterator "
                         "of type '%.100s'",
                         Py_TYPE(res)->tp_name);
            Py_DECREF(res);
            res = NULL;
        }
        // 返回 res
        return res;
    }
}

所以我們看到這便是 iter 函數(shù)的底層實(shí)現(xiàn)，但是里面提到了__getitem__。我們說(shuō)如果類型對(duì)象內(nèi)部沒(méi)有定義 __iter__，那么解釋器會(huì)退而求其次檢測(cè)內(nèi)部是否定義了 __getitem__。

因此以上就是迭代器的創(chuàng)建過(guò)程，每個(gè)可迭代對(duì)象都有自己的迭代器，而迭代器本質(zhì)上只是對(duì)原始數(shù)據(jù)的一層封裝罷了。

迭代器的底層結(jié)構(gòu)

由于迭代器的種類非常多，字符串、元組、列表等等，都有自己的迭代器，這里就不一一介紹了。所以我們就以列表的迭代器為例，看看迭代器在底層的結(jié)構(gòu)是怎么樣的。

typedef struct {
    PyObject_HEAD
    Py_ssize_t it_index;
    //指向創(chuàng)建該迭代器的列表
    PyListObject *it_seq;
} listiterobject;

顯然對(duì)于列表而言，迭代器就是在其之上進(jìn)行了一層簡(jiǎn)單的封裝，所謂元素迭代本質(zhì)上還是基于索引，并且我們每迭代一次，索引就自增 1。一旦出現(xiàn)索引越界，就將it_seq設(shè)置為NULL，表示迭代器迭代完畢。

我們實(shí)際演示一下：

from ctypes import *

class PyObject(Structure):
    _fields_ = [
        ("ob_refcnt", c_ssize_t),
        ("ob_size", c_void_p)
    ]

class ListIterObject(PyObject):
    _fields_ = [
        ("it_index", c_ssize_t),
        ("it_seq", POINTER(PyObject))
    ]

it = iter([1, 2, 3])
it_obj = ListIterObject.from_address(id(it))

# 初始的時(shí)候，索引為0
print(it_obj.it_index)  # 0
# 進(jìn)行迭代
next(it)
# 索引自增1，此時(shí)it_index等于1
print(it_obj.it_index)  # 1
# 再次迭代
next(it)
# 此時(shí)it_index等于2
print(it_obj.it_index)  # 2
# 再次迭代
next(it)
# 此時(shí)it_index等于3
print(it_obj.it_index)  # 3

當(dāng)it_index為3的時(shí)候，如果再次迭代，那么底層發(fā)現(xiàn)it_index已超過(guò)最大索引，就知道迭代器已經(jīng)迭代完畢了。然后會(huì)將it_seq設(shè)置為NULL，并拋出StopIteration。如果是for循環(huán)，那么會(huì)自動(dòng)捕獲此異常，然后停止循環(huán)。

所以這就是迭代器，真的沒(méi)有想象中的那么神秘，甚至在知道它的實(shí)現(xiàn)原理之后，還覺(jué)得有點(diǎn)low。

就是將原始的數(shù)據(jù)包了一層，加了一個(gè)索引而已。所謂的迭代仍然是基于索引來(lái)做的，并且每迭代一次，索引自增1。當(dāng)索引超出范圍時(shí)，證明迭代完畢了，于是將it_seq設(shè)置為NULL，拋出StopIteration。

迭代器是怎么迭代元素的？

我們知道在迭代元素的時(shí)候，可以通過(guò)next內(nèi)置函數(shù)，當(dāng)然它本質(zhì)上也是調(diào)用了對(duì)象的__next__方法。

static PyObject *
builtin_next(PyObject *self, PyObject *const *args, Py_ssize_t nargs)
{
    PyObject *it, *res;
  
    // 同樣接收一個(gè)參數(shù)或者兩個(gè)參數(shù)
    // 因?yàn)檎{(diào)用next函數(shù)時(shí)，可以傳入一個(gè)默認(rèn)值
    // 表示當(dāng)?shù)鳑](méi)有元素可以迭代的時(shí)候，會(huì)返回指定的默認(rèn)值
    if (!_PyArg_CheckPositional("next", nargs, 1, 2))
        return NULL;

    it = args[0];
    //第一個(gè)參數(shù)必須是一個(gè)迭代器
    if (!PyIter_Check(it)) {
        //否則的話, 拋出TypeError
        //表示第一個(gè)參數(shù)傳遞的不是一個(gè)迭代器
        PyErr_Format(PyExc_TypeError,
            "'%.200s' object is not an iterator",
            it->ob_type->tp_name);
        return NULL;
    } 
    //it->ob_type表示獲取類型對(duì)象，也就是該迭代器的類型
    //可能是列表的迭代器、元組的迭代器、字符串的迭代器等等
    //具體是哪一種不重要，因?yàn)閷?shí)現(xiàn)了多態(tài)
    //然后再獲取tp_iternext成員，相當(dāng)于__next__
    //拿到函數(shù)指針之后，傳入迭代器進(jìn)行調(diào)用
    res = (*it->ob_type->tp_iternext)(it);
    
    // 如果 res 不為 NULL, 那么證明迭代到值了, 直接返回
    if (res != NULL) {
        return res;
    } else if (nargs > 1) {
        //否則的話，說(shuō)明 res == NULL，也就是有可能出錯(cuò)了
        //那么看nargs是否大于1, 如果大于1, 說(shuō)明設(shè)置了默認(rèn)值
        PyObject *def = args[1];
        // 如果出現(xiàn)異常
        if (PyErr_Occurred()) {
        // 那么就看該異常是不是迭代完畢時(shí)所產(chǎn)生的StopIteration異常
            if(!PyErr_ExceptionMatches(PyExc_StopIteration))
            // 如果不是，說(shuō)明Python程序的邏輯有問(wèn)題
            // 于是直接return NULL，結(jié)束執(zhí)行
            // 然后在 Python 里面我們會(huì)看到打印到stderr中的異常信息
                return NULL;
            // 如果是 StopIteration，證明迭代完畢了
            // 但我們?cè)O(shè)置了默認(rèn)值，那么就應(yīng)該返回默認(rèn)值
            // 而不應(yīng)該拋出 StopIteration，于是將異?；厮輻＝o清空
            PyErr_Clear();
        }
        // 然后增加默認(rèn)值的引用計(jì)數(shù), 并返回
        Py_INCREF(def);
        return def;
    } else if (PyErr_Occurred()) {
        //走到這里說(shuō)明 res == NULL，并且沒(méi)有指定默認(rèn)值
        //那么當(dāng)發(fā)生異常時(shí)，將異常直接拋出
        return NULL;
    } else {
        // 都不是的話，直接拋出 StopIteration
        PyErr_SetNone(PyExc_StopIteration);
        return NULL;
    }
}

以上就是next函數(shù)的背后邏輯，實(shí)際上還是調(diào)用了迭代器的__next__方法。

lst = [1, 2, 3]
it = iter(lst)
# 然后迭代，等價(jià)于next(it)
print(type(it).__next__(it))  # 1
print(type(it).__next__(it))  # 2
print(type(it).__next__(it))  # 3
# 但是next可以指定默認(rèn)值
# 如果不指定默認(rèn)值，或者還是type(it).__next__(it)
# 那么就會(huì)報(bào)錯(cuò)，會(huì)拋出StopIteration
print(next(it, 666))  # 666

以上就是元素的迭代，但是我們知道內(nèi)置函數(shù)next要更強(qiáng)大一些，因?yàn)樗€可以指定一個(gè)默認(rèn)值。當(dāng)然在不指定默認(rèn)值的情況下，next(it)和type(it).__next__(it)最終是殊途同歸的。

我們?nèi)砸粤斜淼牡鳛槔?，看看__next__的具體實(shí)現(xiàn)。但是要想找到具體實(shí)現(xiàn)，首先要找到它的類型對(duì)象。

//迭代器的類型對(duì)象
PyTypeObject PyListIter_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list_iterator",                            /* tp_name */
    sizeof(listiterobject),                     /* tp_basicsize */
    0,                                          /* tp_itemsize */
    /* methods */
    (destructor)listiter_dealloc,               /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    0,                                          /* tp_repr */
    0,                                          /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    0,                                          /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
    0,                                          /* tp_doc */
    (traverseproc)listiter_traverse,            /* tp_traverse */
    0,                                          /* tp_clear */
    0,                                          /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    PyObject_SelfIter,                          /* tp_iter */
    (iternextfunc)listiter_next,                /* tp_iternext */
    listiter_methods,                           /* tp_methods */
    0,                                          /* tp_members */
};

我們看到它的tp_iternext成員指向了listiter_next，證明迭代的時(shí)候調(diào)用的是這個(gè)函數(shù)。

static PyObject *
listiter_next(listiterobject *it)
{
    PyListObject *seq;  //列表
    PyObject *item;     //元素
    assert(it != NULL);
    //拿到具體對(duì)應(yīng)的列表
    seq = it->it_seq;
    //如果seq為NULL，證明迭代器已經(jīng)迭代完畢
    //否則它不會(huì)為NULL
    if (seq == NULL)
        return NULL;
    assert(PyList_Check(seq));
    //如果索引小于列表的長(zhǎng)度，證明尚未迭代完畢
    if (it->it_index < PyList_GET_SIZE(seq)) {
      //通過(guò)索引獲取指定元素
        item = PyList_GET_ITEM(seq, it->it_index);
      //it_index自增1
        ++it->it_index;
      //增加引用計(jì)數(shù)后返回
        Py_INCREF(item);
        return item;
    }
    //否則的話，說(shuō)明此次索引正好已經(jīng)超出最大范圍
    //意味著迭代完畢了，將it_seq設(shè)置為NULL
    //并減少它的引用計(jì)數(shù)，然后返回
    it->it_seq = NULL;
    Py_DECREF(seq);
    return NULL;
}

顯然這和我們之前分析的是一樣的，以上我們就以列表為例，考察了迭代器的實(shí)現(xiàn)原理和元素迭代的具體過(guò)程。當(dāng)然其它對(duì)象也有自己的迭代器，有興趣可以自己看一看。

小結(jié)

到此，我們?cè)俅误w會(huì)到了Python的設(shè)計(jì)哲學(xué)，通過(guò)PyObject

和ob_type實(shí)現(xiàn)了多態(tài)。原因就在于它們接收的不是對(duì)象本身，而是對(duì)象的PyObject

泛型指針。

不管變量obj指向什么樣的可迭代對(duì)象，都可以交給iter函數(shù)，會(huì)調(diào)用類型對(duì)象內(nèi)部的__iter__，底層是tp_iter，得到對(duì)應(yīng)的迭代器。不管變量it指向什么樣的迭代器，都可以交給next函數(shù)進(jìn)行迭代，會(huì)調(diào)用迭代器的類型對(duì)象的__next__，底層是tp_iternext，將值迭代出來(lái)。

至于__iter__和__next__本身，每個(gè)迭代器都會(huì)有，我們這里只以列表的迭代器為例。

所以這是不是實(shí)現(xiàn)了多態(tài)呢？

這就是Python的設(shè)計(jì)哲學(xué)，變量只是一個(gè)指針，傳遞變量的時(shí)候相當(dāng)于傳遞指針（將指針拷貝一份），但是操作一個(gè)變量的時(shí)候會(huì)自動(dòng)操作變量（指針）指向的內(nèi)存。

比如：a = 123; b = a，相當(dāng)于把 a 拷貝了一份給 b，但 a 是一個(gè)指針，所以此時(shí) a 和 b 保存的地址是相同的，也就是指向了同一個(gè)對(duì)象。但 a+b 的時(shí)候則不是兩個(gè)指針相加，而是將a、b指向的對(duì)象進(jìn)行相加，也就是操作變量會(huì)自動(dòng)操作變量指向的內(nèi)存。

因此在Python中，說(shuō)傳遞方式是值傳遞或者引用傳遞都是不準(zhǔn)確的，應(yīng)該是變量的賦值傳遞，對(duì)象的引用傳遞。

到此這篇關(guān)于Python迭代器的實(shí)現(xiàn)原理的文章就介紹到這了,更多相關(guān)Python迭代器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: