Блог

Я работаю filter с interable и хочу сохранить результат в последовательности (мне нужна последовательность, чтобы я мог использовать random.choice ее). Я заметил, что создание набора из объекта filter намного быстрее, чем создание списка или кортежа. Почему это? Сначала я подумал, что тип фильтра является подтипом set , что могло бы объяснить это, но filter функция фактически идентична выражению генератора, поэтому она не может быть внутренним набором.

Я выполнил следующий тест, чтобы проверить скорость:

 import time

def test ( n, seq ):
    for method in ( set, list, tuple ):
        t = time.time()
        for i in range( n ):
            method( seq )
        print( method.__name__, ( time.time() - t ) )

someFilter = filter( lambda x: x % 3 == 0, range( 1000 ) )
test( 10000000, someFilter )
  

И результаты ясно говорили в пользу использования набора:

 set 1.9240000247955322
list 8.82200002670288
tuple 7.031999826431274
  

Итак, почему создание набора из фильтра происходит намного быстрее? Разве обычно это не должно занимать столько же времени, сколько создание набора из последовательности, где каждый элемент должен быть хэширован? Или это каким-то образом улучшается благодаря представлению внутреннего фильтра?

Для сравнения, при выполнении теста для range выражения set требуется примерно в два раза больше времени, чем для list и tuple (которые оба почти идентичны по скорости).

Редактировать:

Ответ Sven абсолютно правильный, но для полноты картины обновленный тест, который будет выполняться на реальном фильтре:

 import time

def testFilter ( n, test, rangeSize ):
    for method in ( set, list, tuple ):
        t = time.time()
        for i in range( n ):
            method( filter( test, range( rangeSize ) ) )
        print( method.__name__, ( time.time() - t ) )

testFilter( 100000, lambda x: x % 3 == 0, 1000 )
  

Результат на самом деле показывает, что имеет больше смысла, когда list и tuple оба являются самыми быстрыми, хотя set на самом деле не медленнее, так что не будет иметь никакого значения, что использовать:

 set 27.868000030517578
list 27.131999969482422
tuple 27.138000011444092
  

filter() возвращает итератор в Python 3, и этот итератор будет использован при первом запуске внутреннего цикла for. После этого вы только измеряете скорость конструктора — вот почему вам приходится повторять это так часто, чтобы это заняло хотя бы немного времени.

Итак, кажется, что конструктор set() является самым быстрым при работе с пустым итератором.

Когда тайминги предполагают нелогичные результаты, часто виноват сам набор таймингов 😉

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

В этом случае это, по крайней мере, сделало бы временные интервалы сопоставимыми (все они использовали бы новый итератор, возвращаемый версией *filter в Python 3) и показало бы невероятно быстрые временные интервалы (потому что только method(iterator) код был бы синхронизирован в цикле).

FWIW, pypy будет еще сложнее по времени, потому что чрезмерно простые циклы полностью оптимизируются.

[Отредактированный ответ на вопрос] Ваши новые тайминги сопоставимы (хорошее улучшение), но результаты по-прежнему показывают сочетание времени настройки и времени цикла, что затрудняет обнаружение различий, которые могут быть существенными. Вы должны ожидать, что списки и кортежи превзойдут наборы, потому что наборам приходится выполнять больше работы (хэшировать каждый из входных данных, а не просто сохранять их).