Я сделал программу, которая выводит факториал числа, вызывая функцию: factorial(), которая использует рекурсию для вычисления и возврата значения. Я также включил цикл для прерывания программы, когда пользователь вводит слово «выключено». Пожалуйста, предложите какие-либо улучшения
Вот код:
def factorial(base):
if base == 0 or base == 1:
return 1
else:
return base * factorial(base - 1)
while True:
base: int = int(input("Enter a base number: "))
Result = factorial(base)
print(f"The factorial of {base} is: {Result}")
offf: str = input("Enter 'off' to terminate calculations: ")
if offf == "off":
print("Calculations Terminated")
break
Вот терминал:
@KellyBundy, честно говоря, это довольно неэффективный способ вычисления факториала.
@KellyBundy: для вычисления факториалов рекурсия не нужна. Цикл, вероятно, будет немного быстрее, я думаю.
@matszwecja Как так? Вероятно, результат появляется перед пользователем моментально.
@SergioTulentsev Но имеет ли это значение?
@KellyBundy Да, это имеет большое значение, тем более что это рекурсивное решение перестает работать около n = 1000. И на самом деле с компьютерами ничего не происходит «мгновенно».
@matszwecja: хм, python, должно быть, выделяет крошечный стек. В ruby идентичный код начинает давать сбой при n ≈ 9350.
@matszwecja Они ничего не сказали о сбое при больших n, так что, вероятно, они этого не делают. И даже factorial(1000) занимает всего около миллисекунды, что всем покажется мгновенным.
@SergioTulentsev Python имеет ограничение глубины рекурсии по умолчанию, равное 1000. Его можно изменить, но по умолчанию этот код всегда будет падать около n = 1000, так что это своего рода «жестко запрограммированный» сбой по сравнению с нехваткой памяти программы.
@KellyBundy: "Но имеет ли это значение?" - по-видимому, это относится к Silent_Arts
@SergioTulentsev Я не уверен, что это так, и они не сказали почему, отсюда и мой вопрос. Как насчет того, чтобы просто подождать, пока они ответят? Меня совершенно не интересуют догадки других людей.
Рекурсия падает, когда я ввожу что-то около 1000, я думаю, что тогда я просто буду использовать цикл.
Хотя рекурсивный подход кажется естественным, к сожалению, он не очень эффективен, так как каждый вызов требует создания отдельного кадра стека. Это также вызывает проблемы из-за ограничения глубины рекурсии Python, что означает, что эта программа будет вызывать исключение для любого base
> 1000. Итеративный подход (с циклами) примерно в 2-3 раза быстрее и позволяет избежать проблем с ограничением рекурсии.
def factorial_iterative(base, acc = 1):
acc = 1
for i in range(1, base+1):
acc *= i
return acc
Обновлено: Конечно, это все еще не превосходит встроенный метод Python math.factorial
, который дает нам что-то близкое к 10-кратному ускорению.
Вот результаты для base = 995 и 20000 вызовов функции:
math.factorial
: 1,1593496799468994 сек.Предлагаю тоже померить math.factorial
.
@KellyBundy здесь, вероятно, невероятно сложный анализ различных способов вычисления n! и их эффективность.
math.factorial
также использует другой алгоритм, который, как мне кажется, имеет лучшую сложность. Поэтому я подозреваю, что при достаточно больших значениях оно превзойдет ваше решение Numba (я не знаком с Numba и пользуюсь только телефоном, иначе я бы сам его протестировал...).
Подождите... Это простое использование Numba вообще корректно? Я только что попробовал (в конце концов, на replit.com могу), и он требует 30! отрицательно. Похоже, он использует только 64-битные целые числа.
Упс, похоже, что на самом деле это работает только для любых типов C, которые могут обрабатываться. Немного странно, что он не вызывает никаких исключений, хотя
Ваше решение Numba, выглядящее значительно быстрее, чем math.factorial
кстати, было своего рода намеком на то, что что-то не так, так как это не должно быть возможно :-). (По крайней мере, не с таким простым алгоритмом.) Вот почему я проверил. Кстати, вы перезаписываете второй аргумент, и вы можете начать диапазон с 2.
Вы также можете попробовать эту вещь, которая запомнит факториалы.
res_store = [1]
def factorial(num):
try:
return num * res_store[num-1]
except IndexError:
for i in range(len(res_store), num+1):
res_store.append(i * res_store[i-1])
return num * res_store[num-1]
С точки зрения производительности это будет очень быстро, но результат будет сохранен в списке, поэтому он займет память. Для факториала 3000 -> потребление размера будет 26040 байт.
Разве это недостаточно эффективно?