Медленная рекурсия в python

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

def factorial2(x, rest=1):
    if x <= 1:
        return rest
    else:
        return factorial2(x-1, rest*x)


def factorial3(x):
    if x <= 1:
        return 1
    return reduce(lambda a, b: a*b, xrange(1, x+1))

Я знаю, что python не оптимизирует хвостовую рекурсию, поэтому вопрос не в этом. По моему мнению, генератор должен генерировать n количество чисел, используя оператор +1. Технически, fact(n) должно добавить число n раз, как рекурсивное. lambda в reduce будет называться n раз так же, как рекурсивный метод... Поэтому, поскольку в обоих случаях у нас нет оптимизации хвостовых вызовов, стеки будут созданы/уничтожены и возвращены n раз, А if в генераторе должен проверять, когда поднимать исключение StopIteration.

Это заставляет меня задаться вопросом, почему рекурсивный метод все еще медленнее, чем другой, поскольку рекурсивный использует простую арифметику и не использует генераторы.

В тесте я заменил rest*x на x на рекурсивный метод, а потраченное время было уменьшено наравне с методом с использованием reduce.

Вот мои тайминги для факта (400), 1000 раз

factorial3: 1.22370505333

factorial2: 1.79896998405

Edit:

Запуск метода от 1 до n не помогает вместо n до 1. Так что не накладные расходы с -1.

Кроме того, мы можем сделать рекурсивный метод быстрее. Я пробовал несколько вещей, таких как глобальные переменные, которые я могу изменить... Использование изменяемого контекста путем размещения переменных в ячейках, которые я могу изменить как массив, и сохранить рекурсивный метод без параметров. Отправка метода, используемого для рекурсии, в качестве параметра, поэтому нам не нужно "разыгрывать" его в нашей области...?! Но ничего не делает это быстрее.

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

Ответы

Ответ 1

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

$ cat fact.py 
def factorial_recursive1(x):
    if x <= 1:
        return 1
    else:
        return factorial_recursive1(x-1)*x

def factorial_recursive2(x, rest=1):
    if x <= 1:
        return rest
    else:
        return factorial_recursive2(x-1, rest*x)

def factorial_reduce(x):
    if x <= 1:
        return 1
    return reduce(lambda a, b: a*b, xrange(1, x+1))

# Ignore the rest of the code for now, we'll get back to it later in the answer
def range_prod(a, b):
    if a + 1 < b:
        c = (a+b)//2
        return range_prod(a, c) * range_prod(c, b)
    else:
        return a
def factorial_divide_and_conquer(n):
    return 1 if n <= 1 else range_prod(1, n+1)

$ ipython -i fact.py 
In [1]: %timeit factorial_recursive1(400)
10000 loops, best of 3: 79.3 µs per loop
In [2]: %timeit factorial_recursive2(400)
10000 loops, best of 3: 90.9 µs per loop
In [3]: %timeit factorial_reduce(400)
10000 loops, best of 3: 61 µs per loop

Так как в вашем примере задействованы очень большие числа, изначально я подозревал, что разница в производительности может быть вызвана порядком умножения. Умножая на каждой итерации большой частичный продукт на следующее число, пропорционально количеству цифр/бит в произведении, поэтому временная сложность такого метода равна O (n 2), где n равно количество бит в конечном продукте. Вместо этого лучше использовать технику разделения и покорения, где конечный результат получается как произведение двух примерно одинаково длинных значений, каждое из которых вычисляется рекурсивно одинаковым образом. Поэтому я также внедрил эту версию (см. factorial_divide_and_conquer(n) в приведенном выше коде). Как вы можете видеть ниже, он по-прежнему теряет версию reduce() для небольших аргументов (из-за той же проблемы с именованными параметрами), но превосходит ее для больших аргументов.

In [4]: %timeit factorial_divide_and_conquer(400)
10000 loops, best of 3: 90.5 µs per loop
In [5]: %timeit factorial_divide_and_conquer(4000)
1000 loops, best of 3: 1.46 ms per loop
In [6]: %timeit factorial_reduce(4000)
100 loops, best of 3: 3.09 ms per loop

UPDATE

Попытка запуска версий factorial_recursive?() с x=4000 достигает предела рекурсии по умолчанию, поэтому предел должен быть увеличен:

In [7]: sys.setrecursionlimit(4100)
In [8]: %timeit factorial_recursive1(4000)
100 loops, best of 3: 3.36 ms per loop
In [9]: %timeit factorial_recursive2(4000)
100 loops, best of 3: 7.02 ms per loop