Почему этот итеративный метод Collatz на 30% медленнее, чем его рекурсивная версия в Python?

Прелюдия

У меня есть две реализации для конкретной проблемы, одна рекурсивная и одна итеративная, и я хочу знать, что заставляет итеративное решение быть на 30% медленнее, чем рекурсивное.

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

Мое тематическое исследование Проблема №14 в Project Euler.

Найдите самую длинную цепочку Collatz с начальным числом ниже миллиона.

Код

Вот рецессивное решение (кредит, связанный с веритами в нити проблемы плюс оптимизация от jJjjJ):

def solve_PE14_recursive(ub=10**6):
    def collatz_r(n):
        if not n in table:
            if n % 2 == 0:
                table[n] = collatz_r(n // 2) + 1
            elif n % 4 == 3:
                table[n] = collatz_r((3 * n + 1) // 2) + 2
            else:
                table[n] = collatz_r((3 * n + 1) // 4) + 3
        return table[n]
    table = {1: 1}
    return max(xrange(ub // 2 + 1, ub, 2), key=collatz_r)

Здесь моя итеративная версия:

def solve_PE14_iterative(ub=10**6):
    def collatz_i(n):
        stack = []
        while not n in table:
            if n % 2 == 0:
                x, y = n // 2, 1
            elif n % 4 == 3:
                x, y = (3 * n + 1) // 2, 2
            else:
                x, y = (3 * n + 1) // 4, 3
            stack.append((n, y))
            n = x
        ysum = table[n]
        for x, y in reversed(stack):
            ysum += y
            table[x] = ysum
        return ysum
    table = {1: 1}
    return max(xrange(ub // 2 + 1, ub, 2), key=collatz_i)

И тайминги на моей машине (машина i7 с большим объемом памяти) с использованием IPython:

In [3]: %timeit solve_PE14_recursive()
1 loops, best of 3: 942 ms per loop
In [4]: %timeit solve_PE14_iterative()
1 loops, best of 3: 1.35 s per loop

Комментарии

Рекурсивное решение является удивительным:

  • Оптимизирован, чтобы пропустить шаг или два в зависимости от двух младших значащих бит.
    Мое первоначальное решение не пропустило никаких шагов Collatz и заняло ~ 1.86 с
  • Трудно попасть в предел рекурсии по умолчанию Python 1000.
    collatz_r( 9780657630 ) возвращает 1133, но требует менее 1000 рекурсивных вызовов.
  • Воспоминание позволяет избежать повторной проверки.
  • collatz_r длина, рассчитанная по запросу max

Играя с ним, тайминги кажутся точными до +/- 5 мс.
Языки со статической типизацией, такие как C и Haskell, могут получить тайминги ниже 100 мс.
Я положил инициализацию memoization table в методе по дизайну для этого вопроса, так что тайминги будут отражать "повторное обнаружение" значений таблиц при каждом вызове.

collatz_r(2**1002) поднимает RuntimeError: maximum recursion depth exceeded.
collatz_i(2**1002) счастливо возвращается с помощью 1003.

Я знаком с генераторами, сопрограммами и декораторами.
Я использую Python 2.7. Я также рад использовать Numpy (1,8 на моей машине).

Что я ищу

  • итерационное решение, которое закрывает разрыв производительности
  • обсуждение того, как Python обрабатывает рекурсию
  • более тонкие детали штрафов за производительность, связанных с явным стекем

Я смотрю в основном на первое, хотя второе и третье очень важны для этой проблемы и увеличит мое понимание Python.

Ответы

Ответ 1

Здесь мой снимок (частичное) объяснение после запуска некоторых тестов, которые подтверждают ваши цифры.

В то время как рекурсивные вызовы функций стоят дорого в CPython, они не так дороги, как эмуляция стека вызовов с использованием списков. Стек для рекурсивного вызова представляет собой компактную структуру, реализованную в C (см. объяснение Eli Bendersky и файл Python/ceval.c в исходном коде).

В отличие от этого, ваш эмулированный стек представляет собой объект списка Python, то есть массив с динамическим ростом , который содержит динамически растущий массив для привязки объектов, что, в свою очередь, указывает на фактические значения; до свидания, местность ссылок, промахи прошивки hello. Затем вы используете Python заведомо медленную итерацию на этих объектах. Пошаговое профилирование с kernprof подтверждает, что обработка итераций и обработки списков занимает много времени:

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    16                                               @profile
    17                                               def collatz_i(n):
    18    750000       339195      0.5      2.4          stack = []
    19   3702825      1996913      0.5     14.2          while not n in table:
    20   2952825      1329819      0.5      9.5              if n % 2 == 0:
    21    864633       416307      0.5      3.0                  x, y = n // 2, 1
    22   2088192       906202      0.4      6.4              elif n % 4 == 3:
    23   1043583       617536      0.6      4.4                  x, y = (3 * n + 1) // 2, 2
    24                                                       else:
    25   1044609       601008      0.6      4.3                  x, y = (3 * n + 1) // 4, 3
    26   2952825      1543300      0.5     11.0              stack.append((n, y))
    27   2952825      1150867      0.4      8.2              n = x
    28    750000       352395      0.5      2.5          ysum = table[n]
    29   3702825      1693252      0.5     12.0          for x, y in reversed(stack):
    30   2952825      1254553      0.4      8.9              ysum += y
    31   2952825      1560177      0.5     11.1              table[x] = ysum
    32    750000       305911      0.4      2.2          return ysum

Интересно, что даже n = x занимает около 8% от общего времени работы.

(К сожалению, я не смог получить kernprof для создания чего-то подобного для рекурсивной версии.)

Ответ 2

Итеративный код иногда быстрее, чем рекурсивный, поскольку он избегает служебных вызовов функций. Однако stack.append - это вызов функции (и поиск атрибута сверху) и добавляет аналогичные накладные расходы. Подсчитав вызовы append, итеративная версия выполняет так же много вызовов функций, как и рекурсивная версия.

Сравнение первых двух и последних двух таймингов здесь...

$ python -m timeit pass
10000000 loops, best of 3: 0.0242 usec per loop
$ python -m timeit -s "def f(n): pass" "f(1)"
10000000 loops, best of 3: 0.188 usec per loop
$ python -m timeit -s "def f(n): x=[]" "f(1)"
1000000 loops, best of 3: 0.234 usec per loop
$ python -m timeit -s "def f(n): x=[]; x.append" "f(1)"
1000000 loops, best of 3: 0.336 usec per loop
$ python -m timeit -s "def f(n): x=[]; x.append(1)" "f(1)"
1000000 loops, best of 3: 0.499 usec per loop

... подтверждает, что вызов append, исключающий поиск атрибута, занимает примерно то же время, что и вызов минимальной чистой функции Python, ~ 170 нс.

Из вышесказанного я пришел к выводу, что итеративная версия не обладает неотъемлемым преимуществом. Следующий вопрос, который следует рассмотреть, - это тот, который больше работает. Чтобы получить (очень) приблизительную оценку, мы можем посмотреть количество строк, выполняемых в каждой версии. Я сделал быстрый эксперимент, чтобы узнать, что:

  • collatz_r называется 1234275 раз, а тело блока if выполняется 984275 раз.
  • collatz_i называется 250000 раз, а цикл while выполняется 984275 раз

Теперь, скажем, collatz_r имеет 2 строки вне if и 4 строки внутри (которые выполняются в худшем случае, когда попадает else). Это позволяет выполнить до 6,4 миллиона строк. Сопоставимые цифры для collatz_i могут составлять 5 и 9, что составляет до 10 миллионов.

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