Почему эта функция выражения генератора медленнее, чем версия цикла?

Я работал над теорией о том, что генераторные выражения имеют тенденцию быть более эффективными, чем обычные циклы. Но затем я столкнулся с следующим примером: напишите функцию, которая задала число, N и некоторые факторы, ps, возвращает сумму всех чисел в N, кратных хотя бы одному коэффициенту.

Вот версия цикла и более короткая версия выражения генератора:

def loops(N, ps):
    total_sum = 0 
    for i in xrange(N):
        for p in ps: 
            if i%p == 0:
                total_sum += i
                break
    return total_sum

def genexp(N, ps):
    return sum(i for i in xrange(N)
               if any(i%p == 0 for p in ps))

Я ожидаю, что эти два будут примерно равны, возможно, версия для понимания немного быстрее, но я не ожидал этого:

for func in ('loops', 'genexp'):
    print func, timeit.timeit('%s(100000, [3,5,7])' % func, 
                              number=100, 
                              setup='from __main__ import %s' % func)


loops 2.82878184319
genexp 10.1663100719

4x медленнее даже близко! Зачем? Что я не понимаю?

Ответы

Ответ 1

Прежде всего: выражения генератора являются эффективными с точки зрения памяти, не обязательно эффективными с точки зрения скорости.

Ваша компактная версия genexp() медленнее по двум причинам:

  • Выражения генератора реализуются с использованием новой области (например, новой функции). Вы производите N новых областей для каждого теста any(). Создание новой области и разрывание ее снова относительно дорого, конечно, когда это делается в цикле, а затем сравнивается с кодом, который этого не делает.

  • Названия sum() и any() - это дополнительные глобальные переменные, которые нужно искать. В случае any(), это дополнительный N глобальных запросов на тест. Глобалы необходимо искать в словаре, а не в локалях, которые просматриваются индексом в C-массиве (что очень быстро).

Последний является лишь небольшим компонентом, большая часть затрат заключается в создании и уничтожении фреймов (областей); если вы создаете версию, где _any и _sum являются локальными пользователями для функции, которую вы получаете, но небольшое улучшение производительности:

>>> def genexp_locals(N, ps, _any=any, _sum=sum):
...     return _sum(i for i in xrange(N)
...                if _any(i%p == 0 for p in ps))
... 
>>> for func in ('loops', 'genexp', 'genexp_locals'):
...     print func, timeit.timeit('%s(100000, [3,5,7])' % func, 
...                               number=100, 
...                               setup='from __main__ import %s' % func)
... 
loops 2.00835800171
genexp 6.45241594315
genexp_locals 6.23843789101

Я не создал локальный для xrange, чтобы сохранить этот аспект одинаковым. Технически говоря, имя _any рассматривается как замыкание, а не локальное, с помощью объекта кода выражения генератора, которые не так медленны, как глобальные поисковые запросы, но не так быстро, как локальный поиск.