Преобразование времени в генератор в 3,4 раза замедляется

Question

Что происходит?Может кто-нибудь объяснить мне, что здесь происходит, я изменил в узком цикле:

##            j=i
##            while j < ls - 1 and len(wordlist[j]) > lc: j+=1
            j = next(j for j in range(i,ls) if len(wordlist[j]) <=  lc)

Прокомментировал , а версия запустила всю программу: 625 мс , следующий версия генератора запустила всю программу за время 2.125 с .

Что может быть причиной того, что эта более питонная версия привела к такой катастрофической производительности?

РЕДАКТИРОВАТЬ: Может быть, это связано с использованием Псикомодуль ?Конечно, по крайней мере время работы с Python 2.7, который не имеет psyco, было 2.141 для следующей версии, что означает почти то же самое, что Python 2.6 с psyco.

После удаления файлов * .pyc я не получил код для замедления,Затем, когда я удалил импорт psyco из библиотечного модуля, я также получил 2.6 для использования без psyco, результаты для не psyco-версии и psyco-версии (поскольку теперь библиотечная процедура также замедляется, и ее синхронизация также актуальна:)

not psyco:

1. while: подготовка в библиотеке: 532 мс, общее время работы 2,625 с
2. next: подготовка в библиотеке: 532 мс, общее время работы (время.clock ()): 2,844 с (версия с одинаковым временем стены xrange)

psyco:

1. while: подготовка в библиотеке: 297 мс, общее время работы: 609..675 мс
2. следующий: подготовка в библиотеке: 297 мс, общее время работы: 1,922 с (версия с диапазоном вместо xrange везде в программе: 1,985 с)

Запуск вСистема WindowsXP AMD Sempron 3100+ с 2 ГБ оперативной памяти.Подсчет циклов и вызовов с двумя глобальными переменными:

    j=i
    callcount += 1
    while j < ls - 1 and len(wordlist[j]) > lc:
        j+=1
        loopcount += 1

Результат для тестового ввода с psyco:

Finished in 625 ms
Loopcount: 78317
Callcount: 47970
Ration: 1.633

Таким образом, цикл находится внутри замкнутого цикла, но в среднем выполняется только парараз (обратите внимание, что два приращения глобальных счетчиков не замедляли код в psyco)

ВЫВОДЫ: Несмотря на очень чувствительный характер алгоритма относительно длины словаря, который заставил меняпропустите некоторые невозможные слова из рассмотрения в этом цикле, позже основные случаи рекурсии проверяются поиском по словарю, который является O (n), поэтому очень полезная ранняя оптимизация становится не очень полезной , даже при более длинном вводеи перемещение счетчика вызовов в начало функции показало, что на количество вызовов не влияет длина словаря, но количество внешних циклов сокращается (исходный код находится в elif части оператора if).

Более длительное время выполнения (29 372 решения) с циклом while иd весь цикл удален (с использованием i вместо j) (подготовка библиотеки 312 мс):

1. без цикла : число ветвей elif: 485488, externalloopcount: 10129147, соотношение:0,048, время выполнения 6000 с ( без счетчиков: 4,594 с )
2. С циклом : цикл-счет: 19355114, внешний счет: 8194033, коэффициент: 0,236, время выполнения 5,704 с ( без счетчиков: 4,688 с )

(время работы без цикла, счетчиков и психо: 32,792 с, библиотека 608 мс)

То есть без дополнительных счетчиков преимущество этой петли с использованием psyco находится в более сложном случае: (4688-4594) * 100 / 4688.0% = 2%

Это вдохновило меня на отменить другую более раннюю оптимизацию , о которой я задумывался в DaniWeb. Более ранняя версия кода работала быстрее , когда наименьший размер слова был глобальным , а не параметром. Согласно документации, вызовы локальных переменных выполняются быстрее, но очевидно, что затраты на создание рекурсии тяжелее, чем это. Теперь в более сложном случае это другое изменение оптимизации принесло ожидаемое поведение производительности в случае отсутствия оптимизации длины слова: время выполнения с psyco составило 312 мс подготовки, всего 4 469.4.484 с время работы . Таким образом, это сделало код чище и принесло больше пользы в этом случае, как и удаленный цикл. И перевод параметра в версию с циклом while не сильно изменил время выполнения (вариация стала больше для кода подготовки библиотеки)

**What I learned from this: If you do n optimizations for speed 
you must check the first n-1 optimizations after doing nth one**

Answer 1

Я обнаружил, что использование генераторов часто медленнее, чем генерация всего списка, что немного нелогично. Мне удалось устранить узкие места в производительности, просто добавив пару [].

Например, сравните эти:

$ python -m timeit -n 1000 "' '.join(c for c in 'hello world')"
1000 loops, best of 3: 6.11 usec per loop
$ python -m timeit -n 1000 "' '.join([c for c in 'hello world'])"
1000 loops, best of 3: 3.79 usec per loop

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

Редактировать: Как отмечает Томас Воутерс в комментариях, причина того, что генератор работает медленнее, это , потому что это такой простой случай. Для баланса здесь его тест, в котором генератор является явным победителем:

$ python -m timeit -s "s = 'hello world' * 10000" -s "class C: pass" "for i in (C() for c in s): pass"
10 loops, best of 3: 33.6 msec per loop
$ python -m timeit -s "s = 'hello world' * 10000" -s "class C: pass" "for i in [C() for c in s]: pass"
10 loops, best of 3: 172 msec per loop

Answer 2

Два не эквивалентны.

j=i
while j < ls - 1 and len(wordlist[j]) > lc: 
    j+=1

остановит цикл while, как только список слов [j] <= lc. Он мог бы пройти цикл ноль раз, если первое слово в списке короче или равно lc. </p>

j = next(j for j in range(i,ls) if len(wordlist[j]) <=  lc)

продолжит итерацию по всему диапазону от i до ls, независимо от длины слов в списке.

Редактировать : игнорировать вышеизложенное - как указала Эмбер, вызов next () означает, что выражение генератора вычисляется только до тех пор, пока не будет возвращен первый результат. В этом случае я подозреваю, что разница во времени происходит от использования range () вместо xrange () (если это не Python 3.x). В Python 2.x range () создаст полный список в памяти, даже если выражение генератора возвращает только первое значение.