python - 为什么从 dict.keys() 初始化 Set 比使用 set.add() 更快？

Question

代码

total_exc_time = 0
for _ in range(10):
    start = time.time()
    set_a = set()
    dict_a = dict()
    add = set_a.add
    for index in range(1000000):
        dict_a[index] = index
        add(index)
    total_exc_time += ((time.time() - start) * 1000)

total_exc_time = 0
for _ in range(10):
    start = time.time()
    dict_a = dict()
    for index in range(1000000):
        dict_a[index] = index
    set_a = set(dict_a.keys())
    total_exc_time += ((time.time() - start) * 1000)

结果

332.3066234588623 ms
283.2982540130615 ms

第一个代码的时间复杂度不是 O(n)，后面的代码是 O(n) 的 2 倍吗？

标签： pythonpython-3.xtime-complexity

Answer 1

它们是等价的。这里的繁重工作是计算密钥哈希。在这两种情况下，它都会发生两次：添加到字典，然后添加到集合。其他程序应该很轻。您可以使用调试器显示 C 调用以进行验证。

除了 Carcigenicate 提到的函数调用开销之外，内存管理也可能发挥作用。如果集合知道长度，它可能会避免在预定义空间不够时复制数据。