2024-09-27 17:57:16 发布
网友
在Python 3中
def power(base,exponent): if exponent == 1: return base return base * power(base, exponent - 1)
我没有考虑过转角情况(指数<;=0)
为什么不使用上面写的代码来代替使用Divide and Conquer Technique计算的代码,这段代码看起来更简单、更容易理解?这段代码是不是效率降低了?在
是的,如果不是尾部递归,那么效率可能会降低。递归会为内存不足的过大数字创建堆栈帧。正确的方法是使用尾部递归来表达它。您只需要使用一个变量来存储结果acc,这里它将在变量中计算结果,而不是进行递归函数调用
acc
def power2(base,exponent,acc): if exponent == 0: return acc return power2(base,exponent-1,acc*base) print(power2(10,2,1)) #start acc from 1 initially
但是python不是尾部优化的,所以这是这里使用尾部优化的方法
以下是用代码计算2^8所采取的步骤:
power(2,8)= 2*power(2,7)= 2*2*power(2,6)= 2*2*2*power(2,5)= 2*2*2*2*power(2,4)= 2*2*2*2*2*power(2,3)= 2*2*2*2*2*2*power(2,2)= 2*2*2*2*2*2*2*power(2,1)=
以下是使用“分而治之”计算2^8所采取的步骤:
正如您所见,您的方法采用O(n)步,而divide and convery则采用O(lg(n))步骤,速度明显更快。在
如果你关心速度的话,用递归来解决这类问题永远不是一个好主意,因为正如你所看到的,迭代方法(函数式语言中的尾部递归)通常要快得多,在这个例子中,它比你在基准测试中看到的快两倍,就像分而治之的方法一样,你应该一直使用它,除非你正在使用小于22的异能。在
以下是一些基准:
代码:
def r_power(base, exponent): # recursive credits to OP if exponent == 1: return base return base * r_power(base, exponent - 1) def lindc_power(x, y): # linear divide and conquer, credits to Smitha Dinesh Semwal if y == 0: return 1 elif int(y % 2) == 0: return lindc_power(x, int(y / 2)) * lindc_power(x, int(y / 2)) else: return x * lindc_power(x, int(y / 2)) * lindc_power(x, int(y / 2)) def lgdc_power(x, y): # logarithmic divide and conquer if y == 0: return 1 elif int(y % 2) == 0: return lgdc_power(x, int(y / 2)) ** 2 else: return x * lgdc_power(x, int(y / 2)) ** 2 def i_power(base, exponent): # iterative, credits to Yugandhar Chaudhari acc = 1 while True: if exponent == 0: return acc base, exponent, acc = base, exponent - 1, acc * base
结果:
| -| | base | power | recursive | iterative | linear dc | logarithmic dc | | -| | 2 | 10 | 1.27 µs | 746 ns | 8.99 µs | 2.33 µs | | 2 | 22 | 2.96 µs | 1.58 µs | 18.6 µs | 2.95 µs | | 2 | 100 | 15.1 µs | 8.31 µs | 75.3 µs | 4.14 µs | | 2 | 500 | 96.7 µs | 48.9 µs | 312 µs | 5.69 µs | | 2 | 1000 | 424 µs | 178 µs | 1.3 ms | 6.58 µs | | 2 | 1500 | 201 µs | 108 µs | 620 µs | 7.89 µs | | 2 | 2000 | 435 µs | 242 µs | 1.23 ms | 8.15 µs | | 2 | 3000 | error | 409 µs | 2.49 ms | 10.3 µs | | 2 | 6000 | error | 1.13 ms | 5.01 ms | 17.6 µs | | 2 | 10000 | error | 2.64 ms | 9.84 ms | 25.2 µs | | 2 | 20000 | error | 8.74 ms | 19.9 ms | 45.7 µs | | 2 | 100000 | error | 161 ms | 82.4 ms | 249 µs | | 2 | 200000 | error | 626 ms | 159 ms | 532 µs | | 2 | 1000000 | error | 15 s | 651 ms | 3.23 ms | | -|
我的最大递归深度是3000。在
是的,如果不是尾部递归,那么效率可能会降低。递归会为内存不足的过大数字创建堆栈帧。正确的方法是使用尾部递归来表达它。您只需要使用一个变量来存储结果
acc
,这里它将在变量中计算结果,而不是进行递归函数调用但是python不是尾部优化的,所以这是这里使用尾部优化的方法
^{pr2}$以下是用代码计算2^8所采取的步骤:
以下是使用“分而治之”计算2^8所采取的步骤:
^{pr2}$正如您所见,您的方法采用O(n)步,而divide and convery则采用O(lg(n))步骤,速度明显更快。在
如果你关心速度的话,用递归来解决这类问题永远不是一个好主意,因为正如你所看到的,迭代方法(函数式语言中的尾部递归)通常要快得多,在这个例子中,它比你在基准测试中看到的快两倍,就像分而治之的方法一样,你应该一直使用它,除非你正在使用小于22的异能。在
以下是一些基准:
代码:
结果:
我的最大递归深度是3000。在
相关问题 更多 >
编程相关推荐