Использование цикла for против понимания списка для оптимизации кода - PullRequest
Новая
       7

Использование цикла for против понимания списка для оптимизации кода

0 голосов
/ 01 марта 2019

Почему near_all_a более эффективен, чем near_all_b, который использует цикл for против использования списка?Конечно, они оба O (n)?РЕДАКТИРОВАТЬ: ответы на другой вопрос не являются конкретными и в основном говорят, что один может быть быстрее, чем другой, в зависимости от случая.Так что тогда с этим делом? 

def almost_all_a(numbers):
    sumall = sum(numbers)
    rangelen = range(len(numbers))
    return [sumall - numbers[i] for i in rangelen]

def almost_all_b(numbers):
    sumall = sum(numbers)
    for i in range(len(numbers)):
        numbers[i] = sumall - numbers[i]

Ответы [ 2 ]

0 голосов
/ 05 марта 2019

Ваш анализ сложности верен: n операций для вычисления суммы плюс n операций для вычисления списка в обоих случаях составляет O(n).

Но прежде чем говорить о скорости, вы наверняказаметил, что almost_all_b имеет побочный эффект, тогда как almost_all_a не имеет побочных эффектов.Хуже того, almost_all_b не идемпотент.При повторном вызове almost_all_b аргумент numbers будет изменяться каждый раз. Если у вас нет очень веских причин, вы должны предпочесть almost_all_a, чем almost_all_b, так как это легче понять и меньше подвержено ошибкам .

Тест 1

Я будупопробуйте подтвердить свое утверждение (almost_all_a [более эффективно], чем almost_all_b) с помощью timeit: 

>>> from timeit import timeit
>>> ns=list(range(100))
>>> timeit(lambda: almost_all_a(ns), number=10000)
0.06381335399782984
>>> timeit(lambda: almost_all_b(ns), number=10000)
2.3228586789991823

Вау!almost_all_a примерно в 35 раз быстрее, чем almost_all_b !!!Это была шуткаВы можете видеть, что произошло: almost_all_b был применен 10000 раз к [1,...,90] с побочным эффектом, следовательно, цифры выросли безумно: 

>>> len(str(ns[0])) # number of digits of the first element!
19959

Хорошо, это было просто, чтобы убедить вас избегать функций спобочные эффекты.

Бенчмарк 2

Теперь настоящий тест: 

>>> timeit('ns=list(range(100));almost_all(ns)', globals={'almost_all':almost_all_a})
5.720672591000039
>>> timeit('ns=list(range(100));almost_all(ns)', globals={'almost_all':almost_all_b})
5.937547881

Обратите внимание, что эталонный тест может дать другие результаты с другим списком или на другой платформе.(Подумайте, что произойдет, если список займет 90% доступной оперативной памяти.) Но давайте предположим, что мы можем обобщить.

Байт-код Python

Давайте посмотрим на байт-код: 

>>> import dis
>>> dis.dis(almost_all_a)
  2           0 LOAD_GLOBAL              0 (sum)
              2 LOAD_DEREF               0 (numbers)
              4 CALL_FUNCTION            1
              6 STORE_DEREF              1 (sumall)

  3           8 LOAD_GLOBAL              1 (range)
             10 LOAD_GLOBAL              2 (len)
             12 LOAD_DEREF               0 (numbers)
             14 CALL_FUNCTION            1
             16 CALL_FUNCTION            1
             18 STORE_FAST               1 (rangelen)

  4          20 LOAD_CLOSURE             0 (numbers)
             22 LOAD_CLOSURE             1 (sumall)
             24 BUILD_TUPLE              2
             26 LOAD_CONST               1 (<code object <listcomp> at 0x7fdc551dee40, file "<stdin>", line 4>)
             28 LOAD_CONST               2 ('almost_all_a.<locals>.<listcomp>')
             30 MAKE_FUNCTION            8
             32 LOAD_FAST                1 (rangelen)
             34 GET_ITER
             36 CALL_FUNCTION            1
             38 RETURN_VALUE

И: 

>>> dis.dis(almost_all_b)
  2           0 LOAD_GLOBAL              0 (sum)
              2 LOAD_FAST                0 (numbers)
              4 CALL_FUNCTION            1
              6 STORE_FAST               1 (sumall)

  3           8 SETUP_LOOP              36 (to 46)
             10 LOAD_GLOBAL              1 (range)
             12 LOAD_GLOBAL              2 (len)
             14 LOAD_FAST                0 (numbers)
             16 CALL_FUNCTION            1
             18 CALL_FUNCTION            1
             20 GET_ITER
        >>   22 FOR_ITER                20 (to 44)
             24 STORE_FAST               2 (i)

  4          26 LOAD_FAST                1 (sumall)
             28 LOAD_FAST                0 (numbers)
             30 LOAD_FAST                2 (i)
             32 BINARY_SUBSCR
             34 BINARY_SUBTRACT
             36 LOAD_FAST                0 (numbers)
             38 LOAD_FAST                2 (i)
             40 STORE_SUBSCR
             42 JUMP_ABSOLUTE           22
        >>   44 POP_BLOCK
        >>   46 LOAD_CONST               0 (None)
             48 RETURN_VALUE

Начало почти одинаковое.Затем у вас есть понимание списка, как черный ящик.Если мы откроем окно, мы увидим: 

>>> dis.dis(almost_all_a.__code__.co_consts[1])
  4           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                16 (to 22)
              6 STORE_FAST               1 (i)
              8 LOAD_DEREF               1 (sumall)
             10 LOAD_DEREF               0 (numbers)
             12 LOAD_FAST                1 (i)
             14 BINARY_SUBSCR
             16 BINARY_SUBTRACT
             18 LIST_APPEND              2
             20 JUMP_ABSOLUTE            4
        >>   22 RETURN_VALUE

У вас есть два различия:

  • в понимании списка, sumall и numbers загружены с LOAD_DEREFа не LOAD_FAST (это нормально для замыкания) и должно быть немного медленнее;
  • в понимании списка, LIST_APPEND заменяет присвоение numbers[i] (LOAD_FAST(numbers)/LOAD_FAST(i)/STORE_SUBSCR в строках 36-40).

Я предполагаю, что накладные расходы связаны с этим назначением.

Еще один тест

Вы можете переписать almost_all_a, чтобы быть еще аккуратнее, потому что вы неиндекс не нужен: 

def almost_all_c(numbers):
    sumall = sum(numbers)
    return [sumall - n for n in numbers]

Эта версия быстрее (на моем примере + платформа), чем almost_all_a: 

>>> timeit('ns=list(range(100));almost_all(ns)', globals={'almost_all':almost_all_a})
5.755438814000172
>>> timeit('ns=list(range(100));almost_all(ns)', globals={'almost_all':almost_all_b})
5.93645353099987
>>> timeit('ns=list(range(100));almost_all(ns)', globals={'almost_all':almost_all_c})
4.571863283000084

(Обратите внимание, что, как это часто бывает в Python, аккуратнееверсия самая быстрая.) Разница между almost_all_a и almost_all_c заключается в использовании доступа к i -ому элементу numbers (вы можете декомпилировать almost_all_c того, что хотите проверить).

Заключение

Мне кажется, что узким местом здесь является доступ к i -ому элементу numbers:

  • один раз в almost_all_a;
  • два раза в almost_all_b;
  • никогда в almost_all_c.

Вот почему almost_all_a быстрее, чем almost_all_b.

0 голосов
/ 01 марта 2019

Ответ на связанный вопрос содержал все, но он был каким-то образом скрыт.

Давайте посмотрим, что almost_all_a: он создает новый список того же размера, что и исходный список, а затем возвращает этоновый списокДля большого списка это будет использовать вдвое больше памяти, требуемой списком (при условии списков чисел здесь).И если вы вызываете функцию таким образом: nums = almost_all_a(nums), вы просто строите новый список, а когда закончите, отмените предыдущий.Два влияния на производительность: требуется (временная) память и сборщик мусора для очистки старого списка.

В almost_all_b ничего этого не происходит: вы просто меняете элемент списка на месте: никакого дополнительного выделения(увеличение памяти) и нечего собирать (увеличение времени выполнения).

TL / DR: что делает версию a потерянной, это то, что она сводится к выделению нового списка, в то время как ответ связан с сказал:

Использование понимания списка вместо цикла, который не создает список, бессмысленное накопление списка бессмысленных значений и затем выбрасывание списка, часто медленнее из-занакладные расходы по созданию и расширению списка.

...