在dict.items()中判断成员身份的时间复杂度是多少?

根据documentation人的说法:

键视图的设置类似于,因为它们的条目是唯一且可散列的.

因此,我使用以下代码进行了一些测试:

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

As you can see, when the dict.values are all hashable (int),
the execution time for the membership is similar to that of a set or d_keys,
because items view is set-like.
The last two examples are on the dict.values with unhashable objects (list).
So I assumed the execution time would be similar to that of a list.
However, they are still similar to that of a set.

Does this mean that even though dict.values are unhashable objects,
the implementation of items view is still very efficient,
resulting O(1) time complexity for checking the membership?

我错过什么了吗?

EDITED per @chepner's comment: dict.fromkeys(r, [1]) -> {k: [1] for k in r}
EDITED per @MarkRansom's comment: another test case list(d2.items())

推荐答案

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


dictitems_contains并不是简单地try 对元组进行散列,然后在一组类似于键/值对的集合中查找它.

(注意:如果您不想单独单击,以下所有链接仅指向dictitems_contain行中的不同行.)

判断

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

它先是extracts the key from the tuple,然后再try find that key in the underlying dict.如果查找fails,则立即查找returns false.只有找到了 keys ,它才能继续工作.

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

正如文档中提到的,当值不可散列时,dict_items的实例是如何设置的,目前尚不清楚.


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

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).

Python-3.x相关问答推荐

我有个问题继承遗产合伙人

如何创建多个日志(log)文件

Django 3.2/Django-cms 3.11:查找错误:型号帐户.客户用户未注册

如何使用TensorFlow Keras子类化来构建和训练模型

基于另一个数据帧计算总和

将自动文本转换为 DataFrame

在 Python 中实现 COM 接口

使用 Python 在特定组的列中设置上限

将两列合并为一列,将它们制成字典 - pandas - groupby

Python Regex 查找给定字符串是否遵循交替元音、辅音或辅音、元音的连续模式

合并问卷中多列中的稀疏问题 - Pandas

Python:如何从句子/段落中提取地址(非正则表达式方法)?

如何并行化文件下载?

如何使用pandas python获取数据框中每列的最大长度

django - 值更改后自动更新日期

TypeError:列表索引必须是整数或切片,而不是列表

混合全局/参数和名为top的函数的奇怪python行为

如何在python中创建代码对象?

异常被忽略是什么类型的消息?

在 Python 中生成马尔可夫转移矩阵