время Python не инициализирует список в коде установки

Я измеряю время удаления элемента из python set по сравнению с list. Мой код timeit для списка вызывает ValueError: ... x not in list, но только когда я запускаю более одной итерации с timeit !??

Похоже, что для списка переменная, созданная в коде установки, повторно используется в последующей итерации (как если бы код установки не запускался во второй раз??).

Вот мой код:

In [1]: import timeit

In [2]: timeit.timeit(stmt='a.discard(10**5)', setup='a = set(range(10**6))', number=100000)
Out[2]: 0.02187999989837408

In [3]: timeit.timeit(stmt='a.remove(10**5)', setup='a = list(range(10**6))', number=1)
Out[3]: 0.023419374600052834

In [4]: timeit.timeit(stmt='a.remove(10**5)', setup='a = list(range(10**6))', number=2)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: list.remove(x): x not in list

В чем дело??


python list set timeit
person drevicko    schedule 08.08.2018    source источник
comment
@Laurent H. С удовольствием использую правописание США/Великобритании с -ize, но я австралиец, а -ise здесь допустимое написание   -  person drevicko    schedule 08.08.2018
comment
Я действительно извиняюсь перед австралийским народом. Вы меня кое-чему научили, спасибо!   -  person Laurent H.    schedule 08.08.2018

Ответы (3)


arrow_upward
3
arrow_downward

Ключевым моментом является то, что setup выполняется один раз, даже если number >1 (отсюда и ValueError при попытке вызвать list.remove с уникальным значением, которое уже было удалено из списка). Из документов (выделено мной):

Время выполнения основного оператора. Этот оператор setup выполняется один раз, а затем возвращает время, необходимое для выполнения основного оператора несколько раз, измеряемое в секундах как число с плавающей запятой. Аргумент — это количество проходов цикла, по умолчанию равное одному миллиону. Оператор main, оператор setup и функция таймера передаются конструктору.

Итак, если вы хотите выполнить несколько таймингов фрагмента кода, подобного этому (скажем, чтобы получить более точные тайминги), вам нужно использовать number=1, но вместо этого вы можете использовать аргумент repeat с timeit.repeat():

>>> timeit.repeat(stmt='a.remove(10**5)', setup='a = list(range(10**6))', number=1, repeat=2)
[0.002321417909115553, 0.0023121219128370285]
person Chris_Rands    schedule 08.08.2018
comment
между прочим, удаление из sets всегда быстрее, и особенно для длинных lists, где это намного быстрее (для 10k элементов, 10x для удаления первого элемента, 200x для последнего элемента). - person drevicko; 08.08.2018
comment
@dreviko Верно, это имеет смысл с точки зрения временной сложности, поскольку set.remove обычно является операцией O (1) (просто вычисление хэша), а list.remove - операцией O (n) (потенциально проверяя каждый элемент во всем списке) - person Chris_Rands; 08.08.2018
comment
Кроме того, удаление первого элемента имеет успех, так как оставшиеся элементы должны быть перемещены в память afaik (хотя на самом деле это довольно эффективно) - person drevicko; 09.08.2018

arrow_upward
2
arrow_downward 

In [4]: timeit.timeit(stmt='a.remove(10**5)', setup='a = list(range(10**6))', number=2)

a.remove(10**5) выполняется дважды, а 10**5 можно удалить только один раз. setup вызывается только ОДИН РАЗ, поэтому вы всегда работаете с одним и тем же списком или набором.

Это эквивалентно

a = list(range(10**6))
a.remove(10**5)  # works
a.remove(10**5)  # fails with ValueError: list.remove(x): x not in list

Это не приводит к сбою для набора, поскольку сброс набора и удаление списка ведут себя по-разному. Если вы используете метод set remove, вы также получите сообщение об ошибке (KeyError)

a = set(range(10**6))
a.discard(10**5)  # works
a.discard(10**5)  # works

но

a = set(range(10**6))
a.remove(10**5)  # works
a.remove(10**5)  # KeyError 10**5
person smagnan    schedule 08.08.2018

arrow_upward
0
arrow_downward

Операция discard() над наборами ничего не делает, если отбрасываемый элемент не находится в наборе. Однако операция remove() для списков вызывает ValueError, когда элемент не существует. Когда вы инициализируете свой список с помощью range(10**6), значение 10**5 появляется только один раз; в наборе это не проблема, но в списке его можно удалить только один раз и выдаст ошибку при последующих попытках удалить то же значение.

person hbgoddard    schedule 08.08.2018