在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())