为什么 dict.items() 可以快速查找？

Question

假设我们有一个字典

d

定义如下

d = {i:i for i in range(1,1000001)}

然后我们将

d.items()

存储在

x

中。因此，

x

是一个元组集合，其中包含

d

的每个元素的键值对。我创建了一个包含相同元组的列表，定义如下：

l = [(i, i) for i in range(1,1000001)]

现在，我比较了执行

(1000001, 1000001) in x

和

(1000001, 1000001) in l

所需的时间。时间差异非常显着。我认为这是因为

x

具有类似集合的行为并在元组上实现了哈希表，因为元组也是可哈希的。

但是，包含列表的元组是不可散列的，所以我用这本字典尝试了同样的事情：

d = {i:[i,i+1] for i in range(1,1000001)}

与我预想的不同，它仍然启用了快速查找。

这是如何运作的？

PS：这是我的时间比较代码

import time

def for_dict_items(n):
    #d = {i:i for i in range(1, n+1)}
    d = {i:[i, i+1] for i in range(1, n+1)}
    di = d.items()
    st = time.time()
    x = (n, [n, n+1]) in di
    et = time.time()
    return (et - st)


def for_tuples_list(n):
    #l = [(i, i) for i in range(1, n+1)]
    l = [(i,[i, i+1]) for i in range(1, n+1)]
    st = time.time()
    x = (n, [n, n+1]) in l
    et = time.time()
    return (et - st)


k = 1000000

t1 = for_dict_items(k)
t2 = for_tuples_list(k)

print(t1, t2, t2/t1, sep = "\n")

Answer 1

由于 dict 是最重要的核心对象之一，因此它是用 C 实现的，还有

dict_values

、

dict_keys

和

dict_items

。这是 dictitems_contains 的 CPyton

实现

：

static int
dictitems_contains(PyObject *self, PyObject *obj)
{
    _PyDictViewObject *dv = (_PyDictViewObject *)self;
    int result;
    PyObject *key, *value, *found;
    if (dv->dv_dict == NULL)
        return 0;
    if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
        return 0;
    key = PyTuple_GET_ITEM(obj, 0);
    value = PyTuple_GET_ITEM(obj, 1);
    result = PyDict_GetItemRef((PyObject *)dv->dv_dict, key, &found);
    if (result == 1) {
        result = PyObject_RichCompareBool(found, value, Py_EQ);
        Py_DECREF(found);
    }
    return result;
}

如果您不会说 C，它的作用如下：

• 检查视图是否正确 - 即它具有对底层字典的引用（如果不正确，则由于某种原因返回 False）
• 检查输入：如果不是2元组，则返回False。
• 在底层字典中查找键。
• 如果找到，检查值是否匹配。如果是，则返回 True。
• 否则，返回False。

其核心是

dict.items

返回的不是一个列表，而是一个特殊的

dict_items

view。这里的术语“视图”意味着它不代表副本，而只是以某种特定方式检索底层项目的代理。这同样适用于 dict_keys 和

dict_values

，您可以在有关此主题的优秀

文档页面

中阅读更多内容。 请注意，这是特定于 CPython 实现的，对于其他实现可能是错误的。