Почему создание набора из фильтра намного быстрее, чем создание списка или кортежа? - PullRequest
Новая
       14

Почему создание набора из фильтра намного быстрее, чем создание списка или кортежа?

5 голосов
/ 11 ноября 2011

Я запускаю filter для целого числа и хочу сохранить результат в последовательности (мне нужна последовательность, чтобы я мог использовать random.choice для нее). Я заметил, что создание set из filter объекта намного быстрее, чем создание list или tuple . Это почему? Сначала я понял, что тип фильтра является подтипом набора, что объясняет это, но функция 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 (оба по скорости почти идентичны).

редактирование:

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

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 27.868000030517578
list 27.131999969482422
tuple 27.138000011444092

Ответы [ 2 ]

11 голосов
/ 11 ноября 2011

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

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

4 голосов
/ 11 ноября 2011

Когда время подсказывает, что результаты являются нелогичными, часто виноват сам набор времени; -)

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

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

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

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

...