1
chlx 2014-10-22 20:27:15 +08:00
贴代码
|
2
SErHo 2014-10-22 20:29:28 +08:00 via iPad
使用递归的时候有大量重复计算的。
|
3
Miorpher 2014-10-22 20:30:49 +08:00 via Android
我想vote down 1楼,人家内容里不是清清楚楚写着代码来着吗!
|
5
juicy OP ```python
def fib(): a = 1 b = 2 while 1: a, b = b, (a+b) yield a counter = 0 for n in fib(): if counter == 40: print n break counter +=1 ``` |
7
eriale 2014-10-22 20:42:14 +08:00
两种算法不一样,迭代器的复杂度是o(n),递归的复杂度是指数复杂度o(2^n)。
|
8
hahastudio 2014-10-22 20:44:58 +08:00
Read SICP Chapter 1
https://mitpress.mit.edu/sicp/chapter1/node13.html |
9
hahastudio 2014-10-22 20:48:59 +08:00 1
顺带一提,在 Python 引入 lru_cache 之后,也能很快地递归
https://docs.python.org/3/library/functools.html#functools.lru_cache 当然也有不少自己实现的 memoize decorator,比如 https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize |
10
juicy OP @hahastudio 牛!
|
11
MForever78 2014-10-22 20:50:44 +08:00 1
@eriale 正解。举例,在递归的时候,算 fib(40) 的时候,分别要算 fib(38) 和 fib(39),而在算 fib(39) 的时候,会重新计算一遍 fib(38) 而不会利用刚刚得到的结果,导致了大量的重复计算。benchmark 里也明确写了 c with -O2 ,说明是有编译器优化的。
|
12
mengzhuo 2014-10-22 21:10:05 +08:00
算法问题,楼主就算用其他语言也是一样的结果
|
13
jox 2014-10-22 21:20:48 +08:00
第一种算法python会计算lz发的这个帖子能够得到多少回帖,第二种算法python不会计算任何东西,只是简单地把第一种算法的结果偷过来,就这么简单。
|
14
maemual 2014-10-22 21:28:33 +08:00
楼主,你是在逗我(⊙_⊙)?
你是真不懂递归? |
15
Viztor 2014-10-22 21:44:11 +08:00
算法太差,时间复杂度是指数级的,这种情况下使用不同语言带来的效率差异。。。
试一下尾递归优化。 筛选算法之类的。 |
16
eriale 2014-10-22 22:12:13 +08:00
这种树形算法没法用尾递归优化。
想要优化直接改成迭代器方法好了,或者用@hahastudio说的内存装饰器。 |
17
advancedxy 2014-10-22 22:42:57 +08:00 via iPad
@eriale 为什么不能做尾递归优化?accumulator 中存两个之前的计算值不就行了嘛? 像下面这样。
def fib(acc,n): a,b = acc if n <= 1: return b else: return fib(b,a+b), n-1) fib((1,1),n) |
18
rwalle 2014-10-22 22:54:57 +08:00 via Android
楼主你缺乏一些最基础的算法知识啊
斐波那契用递归方法来计算是最愚蠢的,即使只是用于教科书讲解“递归”这个概念 可以看看《代码大全》 |
19
jox 2014-10-22 23:29:08 +08:00
谁说fibonacci不能用递归来算啊,楼主采用的递归方式不对罢了,python似乎是不支持尾递归优化的,除了函数式编程语言外,支持尾递归优化的似乎不多,C也得在编译的时候开启某个选项才行。
def fib(num): if num == 1 or num == 2: return 1 return fib_helper(1, 1, num) def fib_helper(a, b, count): if count == 1: return a return fib_helper(b, a + b, count - 1) |
20
jox 2014-10-22 23:29:55 +08:00
v2ex怎么贴代码啊
hello world 怎么前面的空格都没有了? |
21
jox 2014-10-22 23:30:30 +08:00
额,v2ex会把前面的空格都处理掉啊,晕了
|
22
xarrow 2014-10-22 23:55:03 +08:00
Python 切片 尾调,明天贴代码!
|
23
songco 2014-10-22 23:58:23 +08:00
其实n不大的情况下, 直接用公式比较好:
f(n)=(√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n} |
24
jox 2014-10-23 00:08:15 +08:00
python对递归深度有限制,默认好像超过1000就不让算了,因为python不支持尾递归优化,所以即使写成尾递归的形式也不会节省资源,但是只要不超过默认的递归深度计算速度也是非常快的,不过有个技巧可以让尾递归形式的函数超过递归深度,就像这样:
|
25
monkeylyf 2014-10-23 04:28:17 +08:00
一个是递归没有memorization 一个是类似dp的O(n) 当然后者快啦
|
26
juicy OP 多谢各位,受益匪浅~
|
27
hahastudio 2014-10-23 11:51:03 +08:00
Python Tail Call Optimization Decorator
http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/ 顺带一提,v2ex 贴代码可以用 gist |
28
leopanhf 2014-10-29 15:50:21 +08:00
我觉得楼主其实不太理解 yield 吧??
|