Почему метод разностного метода Python требует времени с пустым набором?

Вот что я имею в виду:

> python -m timeit "set().difference(xrange(0,10))"   
1000000 loops, best of 3: 0.624 usec per loop

> python -m timeit "set().difference(xrange(0,10**4))"
10000 loops, best of 3: 170 usec per loop

Очевидно, python выполняет итерацию по всему аргументу, даже если результат известен как пустой набор заранее. Есть ли веская причина для этого? Код выполнялся в python 2.7.6.

(Даже для непустых множеств, если вы обнаружите, что вы удалили все элементы первого набора на середине итерации, имеет смысл сразу остановиться.)

Ответ 1

Есть ли веская причина для этого?

Наличие специального пути для пустого набора раньше не возникало.

Даже для непустых множеств, если вы обнаружите, что вы удалили все первые элементы набора на полпути через итерацию, имеет смысл сразу остановиться.

Это разумный запрос оптимизации. Я сделал патч и применит его в ближайшее время. Ниже приведены новые тайминги с применяемым патчем:

 $ py -m timeit -s "r = range(10 ** 4); s = set()" "s.difference(r)"
10000000 loops, best of 3: 0.104 usec per loop
 $ py -m timeit -s "r = set(range(10 ** 4)); s = set()" "s.difference(r)"
10000000 loops, best of 3: 0.105 usec per loop
 $ py -m timeit -s "r = range(10 ** 4); s = set()" "s.difference_update(r)"
10000000 loops, best of 3: 0.0659 usec per loop
 $ py -m timeit -s "r = set(range(10 ** 4)); s = set()" "s.difference_update(r)"
10000000 loops, best of 3: 0.0684 usec per loop

Ответ 2

ИМО это вопрос специализации, рассмотрим:

In [18]: r = range(10 ** 4)

In [19]: s = set(range(10 ** 4))

In [20]: %time set().difference(r)
CPU times: user 387 µs, sys: 0 ns, total: 387 µs
Wall time: 394 µs
Out[20]: set()

In [21]: %time set().difference(s)
CPU times: user 10 µs, sys: 8 µs, total: 18 µs
Wall time: 16.2 µs
Out[21]: set()

По-видимому, разница имеет специализированную реализацию для set - set.

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

Per @wim реализуется на https://github.com/python/cpython/blob/master/Objects/setobject.c#L1553-L1555

Ответ 3

Когда основные разработчики Python добавляют новые функции, первым приоритетом является правильный код с тщательным тестированием. Это само по себе достаточно сложно. Ускорение часто приходит позже, поскольку у кого-то есть идея и склонность. Я открыл проблему с трекером 28071, в котором излагаются предложения и аргументы, которые обсуждаются здесь. Я попытаюсь обобщить его расположение здесь.

UPDATE: для элементов, начинающих пустую, было добавлено раннее начало для 3.6.0b1, из-за примерно одного дня.