09月17, 2020
0 comments

41. Dict.keys() 的顺序是如何确定的？

最近在网上看到这样一个问题，大意是：

is dic.items() == zip(dict.keys(), dict.values()) ?

这是一个有意思的问题，类似的问题还有：

  • dict.keys() 和 dict.values() 的顺序一致吗？
  • 与 dict.items() 的顺序一致吗？

这些问题的答案与 dict.keys()、dict.values()、dict.items() 的实现有关。首先我们从最简单的 dict.keys() 开始。

我预先创建了一个简单的字典 a，它的结构是：

>>> a
{1: 'a', 2: 'b'}

为了方便，我使用整数作为 key。 此时 a.keys() 为：

>>> a.keys()
dict_keys([1, 2])

如果再观察一下 a.keys() 返回值的类型：

>>> type(a.keys())
<class 'dict_keys'>

在 Python 3.8 中，a.keys() 返回的是一个 dict_keys 对象，同样的，dict.values() 和 dict.items() 返回的是 dict_values 和 dict_items 对象。

>>> type(a.values())
<class 'dict_values'>
>>> type(a.items())
<class 'dict_items'>

这与 Python 2（也许 3 的一些早期版本也有）不同，Python 2 中这些方法返回的是 list 对象，这也意味着在不同时期，Dict.keys() 的顺序的决定因素是不同的！需要注意，这里仅研究 Python 3.8 的实现，切记！！！。

只要简单尝试几次就会发现，3.8 版本的 Key 顺序是根据添加顺序确定的，比如：

>>> a
{1: 'a', 2: 'b'}
>>> a.keys()
dict_keys([1, 2])
>>> del a[1]
>>> a[1] = 'A'
>>> a.keys()
dict_keys([2, 1])

其他两个方法的行为也是类似，基本上可以给出回答：

dict.keys()、dict.values()、dict.items() 的顺序是一致的，且按照添加顺序排列。

但是，dic.items() == zip(dict.keys(), dict.values()) ？ 这个问题比较复杂。简单的说，通过一些转换，它们的值是一样的，这个逻辑式不成立。

我们需要在源码中确认一下，顺便看看 Dict.keys() 之类的实现。

找到入口

特定类型的所有信息都在其类型定义中可以找到，PyDict_Type 也不例外：

// Objects/dictobject.c:3327

PyTypeObject PyDict_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "dict",
    // ··· ···

    mapp_methods,                               /* tp_methods */

    // ··· ···
};

可以看到其中的成员 mapp_methods，表示的是该类型所有的内置方法，这是一个数组，下面是它的定义：

// Objects/dictobject.c:3201

static PyMethodDef mapp_methods[] = {
    DICT___CONTAINS___METHODDEF
    {"__getitem__", (PyCFunction)(void(*)(void))dict_subscript,        METH_O | METH_COEXIST,
     getitem__doc__},
    {"__sizeof__",      (PyCFunction)(void(*)(void))dict_sizeof,       METH_NOARGS,
     sizeof__doc__},
    DICT_GET_METHODDEF
    DICT_SETDEFAULT_METHODDEF
    DICT_POP_METHODDEF
    DICT_POPITEM_METHODDEF
    {"keys",            dictkeys_new,                   METH_NOARGS,
    keys__doc__},
    {"items",           dictitems_new,                  METH_NOARGS,
    items__doc__},
    {"values",          dictvalues_new,                 METH_NOARGS,
    values__doc__},
    {"update",          (PyCFunction)(void(*)(void))dict_update, METH_VARARGS | METH_KEYWORDS,
     update__doc__},
    DICT_FROMKEYS_METHODDEF
    {"clear",           (PyCFunction)dict_clear,        METH_NOARGS,
     clear__doc__},
    {"copy",            (PyCFunction)dict_copy,         METH_NOARGS,
     copy__doc__},
    DICT___REVERSED___METHODDEF
    {NULL,              NULL}   /* sentinel */
};

如果你有 Python 经验的话，一眼可以看出来，所有 Dict 类型的内置方法都在这里了，当然，keys、values、items 也在。可以看到：

{"keys",            dictkeys_new,                   METH_NOARGS,  keys__doc__},

几乎可以猜到，Python 在解析源码的时候，看到 a.keys 就会先查找 "a" 的类型，然后找到 PyDict_Type 的 mapp_methods 数组，然后在里面找到 "keys" 这一项，定位到真正要调用的函数指针 dictkeys_new。后面的 METH_NOARGS 表示这个方法不需要参数，keys__doc__ 是一个静态文档字符串。

看来这个 dictkeys_new 函数就是我们要找的那个 “入口” 了！

视图对象

继续深入 dictkeys_new 函数，相信很快就可以找到答案了。

// Objects/dictobject.c:4376
static PyObject *
dictkeys_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
{
    return _PyDictView_New(dict, &PyDictKeys_Type);
}

// Objects/dictobject.c:4006
PyObject *
_PyDictView_New(PyObject *dict, PyTypeObject *type)
{
    _PyDictViewObject *dv;
    // ··· ···

    dv = PyObject_GC_New(_PyDictViewObject, type);
    // ··· ···
    dv->dv_dict = (PyDictObject *)dict;

    // ··· ···
    return (PyObject *)dv;
}

dictkeys_new 实际上只是创建了一个 PyDictKeys_Type 对象，其本质是 _PyDictViewObject ，在这个视图中的 dv_dict 保存着真正的 dict 对象引用。创建完这个 PyDictKeys_Type 视图对象后，Dict.keys() 方法貌似就结束了。

我绘制了一张图将 Dict.keys() 发生的转换表示出来：

image.png

在这个过程中，创建了一个新的 _PyDictViewObject，类型正好是 PyDictKeys_Type，与前面 type(a.keys()) 对照一下会更清楚。

输出 Dict.keys()

上面的过程太简单了，只不过创建了一个新的视图对象，这与最终观察到

dict_keys([1, 2])

相去深远！这其中一定还隐藏了什么细节等待我们发现，确实如此！这个过程发生在视图的输出过程中。既然 Dict.keys() 返回的是一个视图对象，当然可以被保存在变量中，对前面的代码稍作调整：

# 将一行代码，拆分为两行，为了更清晰，显式使用 print 函数
>>> keys = a.keys()
>>> print(keys)
dict_keys([1, 2])

image.png

变量 keys 实际上就是图中黄色对象。那么下面发生了什么，视图在什么时候确定了最终 key 输出的顺序呢？

虽然 PyDictKeys_Type 是一个内置类型，但是 Python 绝大多数内置类型也遵循 Python 的类型设计，提供了一些通用方法，其中 tp_repr 被用于显示。

// Objects/dictobject.c:4343

PyTypeObject PyDictKeys_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "dict_keys",                                /* tp_name */
    // ··· ···
    (reprfunc)dictview_repr,                    /* tp_repr */
    // ··· ···
    (getiterfunc)dictkeys_iter,                 /* tp_iter */
    // ··· ···
};

PyDictKeys_Type 的显示方法实现是 dictview_repr， 实际上你可以用下面的方法显示调用这个方法。对了，注意这里的 “dict_keys” 很快我们会再见到它。另外剧透一下，我们最终还会研究 dictkeys_iter，先有个印象。

>>> keys.__repr__()
'dict_keys([1, 2])'

我们顺藤摸瓜，看看 dictview_repr 里发生了什么。

static PyObject *
dictview_repr(_PyDictViewObject *dv)
{
    // ··· ···

    // 由视图 dv 生成一个 list 对象
    seq = PySequence_List((PyObject *)dv);

    // 格式化输出，格式为 类型名 + list 对象
    result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);

    // ··· ···
    return result;
}

逻辑非常清晰：

  • 将视图转换为 list 对象；
  • 格式化输出。

终于，在这里视图对象转换成了序列，也就是 list，key 的顺序也是在 PySequence_List 被确定下来的。注意格式化输出的时候：

  • Py_TYPE(dv)->tp_name 其实就是前面 PyDictKeys_Type 中的 tp_name: "dict_keys";
  • seq 是一个 list，输出类似 [xx, xx, xx]' 完全符合实际输出。

确定 key 的顺序

更进一步，深入 PySequence_List 看看 key 顺序是如何确定的。在开始之前，需要先对视图对象有一些基本概念：

视图是可迭代对象，这也是视图少数支持的访问方式。

其核心逻辑在：

// Objects/listobject.c:877

   // ··· ···
   /* 这里 iterable 是视图对象，先获得迭代器。
    * PyObject_GetIter 的实现： 
    *   t = iterable->ob_type
    *   f = t->tp_iter
    *   it = (*f)(iterable)
    */
   it = PyObject_GetIter(iterable);

   // ··· ···
   // 取出 iternext 函数
   iternext = *it->ob_type->tp_iternext;

   for (;;) {
        // 取出下一个元素
        PyObject *item = iternext(it);

        // ··· ···
        // 追加到 list 尾部
        PyList_SET_ITEM(self, Py_SIZE(self), item);

        // ···
    }

看来就在这里完成从视图中遍历取出元素，添加到 list 中。遍历操作通过视图的迭代器实现，那么只需要知道 PyDictKeys_Type 如何 iternext，就知道它是如何取出 key 的了。

还是要回到 PyDictKeys_Type 的定义，其 tp_iter 实现是 dictkeys_iter，它由创建了一个视图迭代器，最终，其定义在：

PyTypeObject PyDictIterKey_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "dict_keyiterator",                         /* tp_name */
    // ··· ···
    (iternextfunc)dictiter_iternextkey,         /* tp_iternext */
    dictiter_methods,                           /* tp_methods */
    0,
};

可以看到它的 tp_iternext 是 dictiter_iternextkey，从名字也看的出来，这是一个专门的字典 key 迭代器，想必还有 dictiter_iternextvalue、dictiter_iternextitem，你可以在源码中搜索到它们。

// Objects/dictobject.c:3538

static PyObject*
dictiter_iternextkey(dictiterobject *di)
{
    // ··· ··· 

    // 下面的代码做了简化
    // splited mode
    if (d->ma_values) {
        key = DK_ENTRIES(k)[i].me_key;
    }
    else {
        Py_ssize_t n = k->dk_nentries;
        PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
        // 跳过那些被删掉的旧值
        while (i < n && entry_ptr->me_value == NULL) {
            entry_ptr++;
            i++;
        }
        key = entry_ptr->me_key;
    }
    // ··· ···
    return key;

fail:
    // ··· ···
}

显然，key 的取出是从 DK_ENTRIES 按顺序取出的，至于那些先前被删除的 entry 的 value 被设置为 null，在 indcies 中对应位置被设置为 dummy。

总结

image.png

Dict.keys() 返回的是一个视图，只有在输出的时候，才会临时生成一个 list，按照 Entries 顺序依次插入，而 Entries 里的有效值是按插入先后排列的，所以 Dict.keys() 的顺序与插入顺序一致，Dict.values()、Dict.items() 同理。

本文链接：http://www.thinkinpython.com/post/deep_python_vm_41.html

-- EOF --

作者 admin 发表于 2020-09-17 23:45:32 ，添加在分类 Deep in python VM 下 ，最后修改于 2022-01-07 16:07:28

版权归作者所有，如需转载，请保留版权声明。
给作者发送 email: [email protected]
我的公众号：