在 dict.items() 中检查成员资格的时间复杂度是多少？

Question

在 dict.items() 中检查成员资格的时间复杂度是多少？

根据文档：

键视图是类似设置的，因为它们的条目是唯一且可散列的。 如果所有值都是可散列的，因此 (key, value) 对是唯一且可 散列的，那么项目视图也是类似集合的。（值视图不被视为类集合，因为条目通常不是唯一的。）对于类集合视图，为抽象基类 collections.abc.Set 定义的所有操作都可用（例如，==、< , 或 ^)。

所以我用下面的代码做了一些测试：

from timeit import timeit

def membership(val, container):
    val in container

r = range(100000)
s = set(r)
d = dict.fromkeys(r, 1)
d2 = {k: [1] for k in r}
items_list = list(d2.items())

print('set'.ljust(12), end='')
print(timeit(lambda: membership(-1, s), number=1000))
print('dict'.ljust(12), end='')
print(timeit(lambda: membership(-1, d), number=1000))
print('d_keys'.ljust(12), end='')
print(timeit(lambda: membership(-1, d.keys()), number=1000))
print('d_values'.ljust(12), end='')
print(timeit(lambda: membership(-1, d.values()), number=1000))
print('\n*With hashable dict.values')
print('d_items'.ljust(12), end='')
print(timeit(lambda: membership((-1, 1), d.items()), number=1000))
print('*With unhashable dict.values')
print('d_items'.ljust(12), end='')
print(timeit(lambda: membership((-1, 1), d2.items()), number=1000))
print('d_items'.ljust(12), end='')
print(timeit(lambda: membership((-1, [1]), d2.items()), number=1000))
print('\nitems_list'.ljust(12), end='')
print(timeit(lambda: membership((-1, [1]), items_list), number=1000))

随着输出：

set         0.00034419999999998896
dict        0.0003307000000000171
d_keys      0.0004200000000000037
d_values    2.4773092

*With hashable dict.values
d_items     0.0004413000000003109
*With unhashable dict.values
d_items     0.00042879999999989593
d_items     0.0005549000000000248

items_list  3.5529328

如您所见，当dict.values都是可散列的 ( int)
时，成员资格的执行时间与 a setor相似d_keys，
因为items 视图是 set-like。
最后两个例子是关于dict.values不可散列的对象 ( list)。
所以我假设执行时间将类似于list.
但是，它们仍然类似于set.

这是否意味着即使dict.values是不可散列的对象，项目视图
的实现仍然非常高效， 导致检查成员资格的时间复杂度为O(1)？

我在这里错过了什么吗？

EDITED 每@ chepner的评论：dict.fromkeys(r, [1])- > {k: [1] for k in r}
EDITED 每@ MarkRansom的评论：另一个测试案例list(d2.items())

Answer 1

简答

项目视图中成员资格测试的时间复杂度为O(1).

用于查找的伪代码

这是成员资格测试的工作原理：

def dictitems_contains(dictview, key_value_pair):
    d = dictview.mapping
    k, v = key_value_pair
    try:
        return d[k] == v
    except KeyError:
        return False

实际代码

这是C 源代码：

static int
dictitems_contains(_PyDictViewObject *dv, PyObject *obj)
{
    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);
    found = PyDict_GetItemWithError((PyObject *)dv->dv_dict, key);
    if (found == NULL) {
        if (PyErr_Occurred())
            return -1;
        return 0;
    }
    Py_INCREF(found);
    result = PyObject_RichCompareBool(found, value, Py_EQ);
    Py_DECREF(found);
    return result;
}

O(1) 复杂度的时间证据

无论字典大小如何（在这些情况下：100、1,000 和 10,000），我们都会获得相同的恒定查找时间。

$ python3.8 -m timeit -s 'd = dict.fromkeys(range(100))'  '(99, None) in d.items()'
5000000 loops, best of 5: 92 nsec per loop

$ python3.8 -m timeit -s 'd = dict.fromkeys(range(1_000))'  '(99, None) in d.items()'
5000000 loops, best of 5: 92.2 nsec per loop

$ python3.8 -m timeit -s 'd = dict.fromkeys(range(10_000))'  '(99, None) in d.items()'
5000000 loops, best of 5: 92.1 nsec per loop

查找调用 hash() 的证据

我们可以通过修补_ hash _()来监控哈希调用：

class Int(int):
    def __hash__(self):
        print('Hash called')
        return hash(int(self))

应用监控工具显示，在创建字典时会发生散列，并在对项目视图进行成员资格测试时再次发生散列：

>>> d = {Int(1): 'one'}
Hash called
>>> (Int(1), 'one') in d.items()
Hash called
True

Answer 2

在 的实例中查找dict_items是一个 O(1) 操作（尽管具有任意大的常数，与比较值的复杂性有关。）

dictitems_contains 不只是尝试散列元组并在类似集合的键/值对集合中查找它。

（注意：以下所有链接仅指向 的不同行dictitems_contain，如果您不想单独单击它们。）

评估

(-1, [1]) in d2.items()

它首先从元组中提取键，然后尝试在底层dict. 如果查找失败，它会立即返回 false。只有找到了键，它才会将元组中的值与映射到 dict 中的键的值进行比较。

在任何时候都不dictitems_contains需要散列元组的第二个元素。

这不是用什么方法清除的一个实例dict_items是不设置喜欢当值是非可哈希，如文档中提到的。

一个简化的纯 Python 实现dict_items.__contains__可能看起来像

class DictItems:
    def __init__(self, d):
        self.d = d

    def __contains__(self, t):
        key = t[0]
        value = t[1]
        try:
            dict_value = self.d[key]  # O(1) lookup
        except KeyError:
            return False
    
        return value == dict_value  # Arbitrarily expensive comparison

    ...

哪里d.items()返回DictItems(d)。