有没有办法进一步优化这个程序?

Question

我正在编写这个程序来计算涉及阶乘的基本方程，该方程正在在线服务器上进行测试。等式是 (1/n！) * (1！+ 2！+ 3...n!).该程序运行良好并完成工作，但是对于 n>1000 的测试用例，它运行缓慢并导致服务器超时。无论如何，我可以优化此程序以使其在较大的测试用例中更快地运行吗？结果需要截断到小数点后 6 位，因此 math.floor() 的内容正在发生。

import math
def fact(n):
return math.factorial(n)
def going(n):
return math.floor(((sum(fact(i) for i in range(1, n+1)))/ fact(n) * 1000000))/ 1000000

Answer 1

查看不同级别的优化:)的代码执行会很有趣 第一种情况 - 未优化的代码(运行输入 1000、3000、...，然后向下)

from functools import wraps
import time
import math

def timeit(func):
@wraps(func)
def timeit_wrapper(*args, **kwargs):
start_time = time.perf_counter()
result = func(*args, **kwargs)
end_time = time.perf_counter()
total_time = end_time - start_time
print(f'Function {func.__name__}{args} {kwargs} Took {total_time:.4f} seconds')
return result
return timeit_wrapper
def my_fact(n):
return math.factorial(n)
@timeit
def going(n):
return math.floor(((sum(my_fact(i) for i in range(1, n+1)))/ my_fact(n) * 1000000))/ 1000000
def main():
for i in range(1000, 20000, 2000):
going(i)
for i in range(20000, 1000, -2000):
going(i)
if __name__ == '__main__':
main()

执行-

Function going(1000,) {} Took 0.0193 seconds
Function going(3000,) {} Took 0.3540 seconds
Function going(5000,) {} Took 1.5023 seconds
Function going(7000,) {} Took 3.8886 seconds
Function going(9000,) {} Took 7.7359 seconds
Function going(11000,) {} Took 13.7363 seconds
Function going(13000,) {} Took 21.8165 seconds
Function going(15000,) {} Took 32.3038 seconds
Function going(17000,) {} Took 44.8729 seconds
Function going(19000,) {} Took 61.6663 seconds
Function going(20000,) {} Took 70.6783 seconds
Function going(18000,) {} Took 52.4495 seconds
Function going(16000,) {} Took 37.3437 seconds
Function going(14000,) {} Took 25.7586 seconds
Function going(12000,) {} Took 17.7381 seconds
Function going(10000,) {} Took 10.2902 seconds
Function going(8000,) {} Took 5.6387 seconds
Function going(6000,) {} Took 2.4552 seconds
Function going(4000,) {} Took 0.7788 seconds
Function going(2000,) {} Took 0.1096 seconds

鉴于代码大量使用阶乘函数 A LOT，最好优化其执行时间。 一个简单快捷的优化是缓存到阶乘函数(结果将被保存并在将来重用)。这将很好地工作，因为您可以在所有输入上运行它，因此重新运行会快得多，就像在这段代码中一样-

from functools import wraps
import functools
import time
import math

def timeit(func):
@wraps(func)
def timeit_wrapper(*args, **kwargs):
start_time = time.perf_counter()
result = func(*args, **kwargs)
end_time = time.perf_counter()
total_time = end_time - start_time
print(f'Function {func.__name__}{args} {kwargs} Took {total_time:.4f} seconds')
return result
return timeit_wrapper
@functools.cache
def my_fact(n):
return math.factorial(n)
@timeit
def going(n):
return math.floor(((sum(my_fact(i) for i in range(1, n+1)))/ my_fact(n) * 1000000))/ 1000000
def main():
for i in range(1000, 20000, 2000):
going(i)
for i in range(20000, 1000, -2000):
going(i)
if __name__ == '__main__':
main()

执行-

Function going(1000,) {} Took 0.0208 seconds
Function going(3000,) {} Took 0.3680 seconds
Function going(5000,) {} Took 1.1571 seconds
Function going(7000,) {} Took 2.3572 seconds
Function going(9000,) {} Took 4.1111 seconds
Function going(11000,) {} Took 5.9934 seconds
Function going(13000,) {} Took 8.4503 seconds
Function going(15000,) {} Took 10.4227 seconds
Function going(17000,) {} Took 13.3260 seconds
Function going(19000,) {} Took 16.8218 seconds
Function going(20000,) {} Took 9.8875 seconds
Function going(18000,) {} Took 0.1035 seconds
Function going(16000,) {} Took 0.0705 seconds
Function going(14000,) {} Took 0.0464 seconds
Function going(12000,) {} Took 0.0266 seconds
Function going(10000,) {} Took 0.0171 seconds
Function going(8000,) {} Took 0.0109 seconds
Function going(6000,) {} Took 0.0061 seconds
Function going(4000,) {} Took 0.0030 seconds
Function going(2000,) {} Took 0.0009 seconds

前面的实现非常好，在高输入下运行后，未来的运行会很快，因为它们将使用缓存，尽管第一次运行不会很快。 更好的优化是使用自定义阶乘函数，该函数会保存缓存，并给定输入，始终从上一个最高的缓存开始，而不是重新开始计算，如以下代码所示

from functools import wraps
import time
import math

def timeit(func):
@wraps(func)
def timeit_wrapper(*args, **kwargs):
start_time = time.perf_counter()
result = func(*args, **kwargs)
end_time = time.perf_counter()
total_time = end_time - start_time
print(f'Function {func.__name__}{args} {kwargs} Took {total_time:.4f} seconds')
return result
return timeit_wrapper

fact_cache = {1: 1}
maximal_factorial = 1
def my_fact(n):
global fact_cache
global maximal_factorial
if n in fact_cache:
return fact_cache[n]
result_index = maximal_factorial
result = fact_cache[maximal_factorial]
while result_index < n:
result_index += 1
result *= result_index
fact_cache[result_index] = result
maximal_factorial = n
return result
@timeit
def going(n):
return math.floor(((sum(my_fact(i) for i in range(1, n+1)))/ my_fact(n) * 1000000))/ 1000000
def main():
for i in range(1000, 20000, 2000):
going(i)
for i in range(20000, 1000, -2000):
going(i)
if __name__ == '__main__':
main()

执行-

Function going(1000,) {} Took 0.0014 seconds
Function going(3000,) {} Took 0.0103 seconds
Function going(5000,) {} Took 0.0168 seconds
Function going(7000,) {} Took 0.0263 seconds
Function going(9000,) {} Took 0.0357 seconds
Function going(11000,) {} Took 0.0479 seconds
Function going(13000,) {} Took 0.0656 seconds
Function going(15000,) {} Took 0.0999 seconds
Function going(17000,) {} Took 0.1365 seconds
Function going(19000,) {} Took 0.1823 seconds
Function going(20000,) {} Took 0.1955 seconds
Function going(18000,) {} Took 0.1035 seconds
Function going(16000,) {} Took 0.0661 seconds
Function going(14000,) {} Took 0.0418 seconds
Function going(12000,) {} Took 0.0264 seconds
Function going(10000,) {} Took 0.0172 seconds
Function going(8000,) {} Took 0.0119 seconds
Function going(6000,) {} Took 0.0067 seconds
Function going(4000,) {} Took 0.0030 seconds
Function going(2000,) {} Took 0.0013 seconds

在您的情况下，这可能是矫枉过正，但优化很有趣！

希望这对:)有所帮助

Answer 2

首先请注意，您可以重写总和：

(1! + 2! +....+ (n-1)! + n!) / n! = 1!/n! + 2!/n! + ... (n-1)!/n! +n!/n!
= 1/(2*3*...n) + 1/(3*...n) + ... 1/n + 1

我们可以简单地计算分母上的乘积，并在飞行中将倒数添加到总数中，无需存储任何东西。因此，可以在 O(n) 时间和 O(1) 空间中进行计算：

def better(n):
res = 1
prod = 1
for k in range(n, 1, -1):
prod *= k
res += 1/prod
return res

仅此而已。

仍有一些改进的余地：随着 n 变大，整数积将变得非常大，并且总是需要更多的时间来计算，因为 Python 整数具有无限的精度。我们可以简单地使用浮点数：

def better_with_float_prod(n):
res = 1
prod = 1.0  # prod will be a float now
for k in range(n, 1, -1):
prod *= k
res += 1/prod
return res

一些时序(n非常小，整数和浮点版本之间几乎没有区别)

n = 10
# %timeit going(n)
# %timeit better(n)
# 3.93 µs ± 42.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
# 1.76 µs ± 62.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
n = 1000
# 21.9 ms ± 262 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
# 524 µs ± 6.74 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

n=2000
# %timeit going(n)
# %timeit better(n)
# %timeit better_with_float_prod(n)
# 158 ms ± 1.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# 1.7 ms ± 4.05 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# 310 µs ± 5.98 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

n = 5000
# %timeit going(n)
# %timeit better(n)
# %timeit better_with_float_prod(n)
# 2.12 s ± 6.51 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# 9.77 ms ± 14.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# 765 µs ± 1.08 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

当 n = 100_000 时：

%timeit better_with_float_prod(100000)
# 15.5 ms ± 307 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

所以，更短，更快！

Answer 3

计算可以优化为不使用阶乘函数和大数，并具有以下改进：

• O(n) 处理复杂性和 O(1) 空间
• 节省大量空间和处理时间
• 对缓存方法的改进(参见盖伊答案)

法典

def faster_going(n, term = 1):
# Using Walrus operator available in Python 3.8+
return 1 + sum(term for i in range(n, 1, -1) if (term:=term/i))

解释

我们正在计算的总和是：

(1! + 2! + ... + (n-1)! + n!)/n!

从右到左取术语，我们有以下术语：

term[n] = Last term will is            = n!/n!       = 1 
term[n-1] = next to last term is       = (n-1)!/n! = term[0]/n 
term[n-2] = second to last term is     = (n-2)!/n!  = term[1]/(n-1) 
... 
term[2] = 1st term                     = 1/n!       = term[3]/1

我们只需将 term[2] + ... + term[n] 相加即可获得结果，而无需计算大整数。

因此，我们与以下方面存在递归关系：

项 [n] = 1 ... 术语[k-1] = 术语[k]/k

函数faster_going只是使用递归公式将项从 1 加到 n。

性能比较

Guy缓存方法的比较(见其他答案)

总结：

• 当 n = 20， 000 时，这种方法比 Guy 方法快 41 倍
• 函数 go(20000，) {} 耗时 0.4924 秒
• 函数 faster_going(20000，) {} 耗时 0.0127 秒

测试代码

from functools import wraps
import time
import math

def timeit(func):
@wraps(func)
def timeit_wrapper(*args, **kwargs):
start_time = time.perf_counter()
result = func(*args, **kwargs)
end_time = time.perf_counter()
total_time = end_time - start_time
print(f'Function {func.__name__}{args} {kwargs} Took {total_time:.4f} seconds')
return result
return timeit_wrapper

def my_fact(n):
global fact_cache
global maximal_factorial
if n in fact_cache:
return fact_cache[n]
result_index = maximal_factorial
result = fact_cache[maximal_factorial]
while result_index < n:
result_index += 1
result *= result_index
fact_cache[result_index] = result
maximal_factorial = n
return result
@timeit
def going(n):
return math.floor(((sum(my_fact(i) for i in range(1, n+1)))/ my_fact(n) * 1000000))/ 1000000
@timeit
def faster_going(n, term = 1):
return 1 + sum(term for i in range(n, 1, -1) if (term:=term/i))

def main():
for i in range(1000, 20000, 2000):
# Reset cache for each run, so timing is independent
fact_cache = {1: 1}
maximal_factorial = 1
going(i)
faster_going(i)

for i in range(20000, 1000, -2000):
# Reset cache for each run, so timing is independent
fact_cache = {1: 1}
maximal_factorial = 1

going(i)
faster_going(i)

输出

Function going(1000,) {} Took 0.0025 seconds
Function faster_going(1000,) {} Took 0.0005 seconds
Function going(3000,) {} Took 0.0159 seconds
Function faster_going(3000,) {} Took 0.0022 seconds
Function going(5000,) {} Took 0.0244 seconds
Function faster_going(5000,) {} Took 0.0030 seconds
Function going(7000,) {} Took 0.0430 seconds
Function faster_going(7000,) {} Took 0.0043 seconds
Function going(9000,) {} Took 0.0558 seconds
Function faster_going(9000,) {} Took 0.0056 seconds
Function going(11000,) {} Took 0.0914 seconds
Function faster_going(11000,) {} Took 0.0070 seconds
Function going(13000,) {} Took 0.1426 seconds
Function faster_going(13000,) {} Took 0.0084 seconds
Function going(15000,) {} Took 0.1989 seconds
Function faster_going(15000,) {} Took 0.0144 seconds
Function going(17000,) {} Took 0.2982 seconds
Function faster_going(17000,) {} Took 0.0116 seconds
Function going(19000,) {} Took 0.4696 seconds
Function faster_going(19000,) {} Took 0.0120 seconds
Function going(20000,) {} Took 0.4924 seconds
Function faster_going(20000,) {} Took 0.0127 seconds
Function going(18000,) {} Took 0.3013 seconds
Function faster_going(18000,) {} Took 0.0118 seconds
Function going(16000,) {} Took 0.1817 seconds
Function faster_going(16000,) {} Took 0.0099 seconds
Function going(14000,) {} Took 0.1093 seconds
Function faster_going(14000,) {} Took 0.0088 seconds
Function going(12000,) {} Took 0.0724 seconds
Function faster_going(12000,) {} Took 0.0072 seconds
Function going(10000,) {} Took 0.0482 seconds
Function faster_going(10000,) {} Took 0.0060 seconds
Function going(8000,) {} Took 0.0332 seconds
Function faster_going(8000,) {} Took 0.0048 seconds
Function going(6000,) {} Took 0.0208 seconds
Function faster_going(6000,) {} Took 0.0043 seconds
Function going(4000,) {} Took 0.0118 seconds
Function faster_going(4000,) {} Took 0.0024 seconds
Function going(2000,) {} Took 0.0044 seconds
Function faster_going(2000,) {} Took 0.0012 seconds​