Python使用timeit测试字典key删除时间时key出错

Question

我越来越厌倦和困惑地试图让这段代码工作。这是来自 "Problem Solving with Data Structures and Algorithms" 网络教科书的算法分析作业。它要求比较删除列表元素和字典元素所花费的时间。列表删除时间的测试工作正常，但无论我尝试删除字典元素，它都会给我一个关键错误。谁能解释为什么会这样？

import timeit 
import pylab

x_list = []
delList_list = []
delDictionary_list = []

delDictionary = timeit.Timer("del x[0]",
                      "from __main__ import x")
delList = timeit.Timer("del x[100]",
              "from __main__ import x")
for i in range(10000,100001,20000):

    x_list.append(i)

    x = list(range(i))
    delListTime = delList.timeit(number=1000) 
    delList_list.append(delListTime)

    x = {j:None for j in range(i)}


    delDictTime = delDictionary.timeit(number = 1000) 
    delDictionary_list.append(delDictTime) 


pylab.xlabel('Size')
pylab.ylabel('Time to complete contains operation')
pylab.plot(x_list, delList_list, 'c')
pylab.plot(x_list, delDictionary_list, 'm')
pylab.show()

Answer 1

timeit 重复被测代码，但您的词典不是该代码的一部分。因此，在第一次删除后，您将得到 KeyError.

您必须预先生成足够多的字典副本，然后在测试代码中选择下一个字典。对列表对象执行相同的操作以保持平稳：

delDictionary = timeit.Timer("del next(xiter)[0]",
                      "from __main__ import xiter")
delList = timeit.Timer("del next(xiter)[100]",
              "from __main__ import xiter")

# ... and in the loop

x = [list(range(i)) for _ in range(1000)]  # 1000 identical lists
xiter = iter(x)
delListTime = delList.timeit(number=1000) 
delList_list.append(delListTime)

x = [dict.fromkeys(range(i)) for _ in range(1000)]  # 1000 identical dictionaries
xiter = iter(x)

delDictTime = delDictionary.timeit(number = 1000) 
delDictionary_list.append(delDictTime)

所以每个测试都被赋予一个新鲜列表或字典对象，使比较公平。

请注意，我用更快的 dict.fromkeys(range(i)) 替换了 {j:None for j in range(i)}；后者在 C 代码中循环，默认值为 None（但在将 dict.fromkeys() 用于可变对象时要注意，不会创建副本）。

Python使用timeit测试字典key删除时间时key出错

Python key error when using timeit to test dictionary key deletion time

python

dictionary

timer

timeit

python-3.x