Ошибка ключа Python при использовании timeit для проверки времени удаления ключа словаря

Question

Я стал все более уставшим и озадаченным, пытаясь заставить этот код работать. Это задание анализа алгоритма из веб-учебника "Решение проблем со структурами данных и алгоритмами". Он просит сравнить время, необходимое для удаления элемента списка и элемента словаря. Тест на время удаления списка работает нормально, но если я пытаюсь удалить элемент словаря, это дает мне ключевую ошибку. Кто-нибудь может объяснить, почему это так?

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) 

Таким образом, каждому тесту присваивается новый список или словарь, что делает сравнение справедливым.

Обратите внимание, что я заменил {j:None for j in range(i)} с гораздо быстрее dict.fromkeys(range(i)); последний цикл в коде C, значение по умолчанию None (но будьте осторожны при использовании dict.fromkeys() с изменяемым объектом копии не создаются).