V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
This topic created in 4205 days ago, the information mentioned may be changed or developed.
这几天学了点python,有一道题是让练习用python计算fibonacci数列，发现个很有意思的事：
当用传统的写法
return fib(n-1) + fib(n-2)
来算fib(40)的时候，算得超级慢,分钟级别的
而用generator的时候
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
瞬间就计算完了
后来，在这个链接里http://fengmk2.cnpmjs.org/blog/2011/fibonacci/nodejs-python-php-ruby-lua.html 发现了各种语言算fib(40)的效率
我很纳闷的是：
最后几种语言花费的时间跟python一样，都竟然达到1m，2m，甚至3m，
说得夸张一点，人脑算得都比它们快，
那么，问题来了，如题
当用传统的写法
return fib(n-1) + fib(n-2)
来算fib(40)的时候，算得超级慢,分钟级别的
而用generator的时候
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
瞬间就计算完了
后来，在这个链接里http://fengmk2.cnpmjs.org/blog/2011/fibonacci/nodejs-python-php-ruby-lua.html 发现了各种语言算fib(40)的效率
我很纳闷的是：
最后几种语言花费的时间跟python一样，都竟然达到1m，2m，甚至3m，
说得夸张一点，人脑算得都比它们快，
那么，问题来了，如题
 |
1
chlx Oct 22, 2014
贴代码
|
 |
2
SErHo Oct 22, 2014 via iPad
使用递归的时候有大量重复计算的。
|
 |
3
Miorpher Oct 22, 2014 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 Oct 22, 2014
两种算法不一样，迭代器的复杂度是o(n),递归的复杂度是指数复杂度o(2^n)。
|
 |
8
hahastudio Oct 22, 2014
Read SICP Chapter 1
https://mitpress.mit.edu/sicp/chapter1/node13.html |
|
9
hahastudio Oct 22, 2014  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 Oct 22, 2014 1
@eriale 正解。举例，在递归的时候，算 fib(40) 的时候，分别要算 fib(38) 和 fib(39)，而在算 fib(39) 的时候，会重新计算一遍 fib(38) 而不会利用刚刚得到的结果，导致了大量的重复计算。benchmark 里也明确写了 c with -O2 ，说明是有编译器优化的。
|
 |
12
mengzhuo Oct 22, 2014
算法问题，楼主就算用其他语言也是一样的结果
|
 |
13
jox Oct 22, 2014
第一种算法python会计算lz发的这个帖子能够得到多少回帖，第二种算法python不会计算任何东西，只是简单地把第一种算法的结果偷过来，就这么简单。
|
 |
14
maemual Oct 22, 2014
楼主，你是在逗我(⊙_⊙)？
你是真不懂递归？ |
 |
15
Viztor Oct 22, 2014
算法太差，时间复杂度是指数级的，这种情况下使用不同语言带来的效率差异。。。
试一下尾递归优化。 筛选算法之类的。 |
|
16
eriale Oct 22, 2014
这种树形算法没法用尾递归优化。
想要优化直接改成迭代器方法好了，或者用@hahastudio说的内存装饰器。 |
 |
17
advancedxy Oct 22, 2014 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 Oct 22, 2014 via Android
楼主你缺乏一些最基础的算法知识啊
斐波那契用递归方法来计算是最愚蠢的，即使只是用于教科书讲解“递归”这个概念 可以看看《代码大全》 |
|
19
jox Oct 22, 2014
谁说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 Oct 22, 2014
v2ex怎么贴代码啊
hello world 怎么前面的空格都没有了？ |
|
21
jox Oct 22, 2014
额，v2ex会把前面的空格都处理掉啊，晕了
|
 |
22
xarrow Oct 22, 2014
Python 切片 尾调，明天贴代码！
|
 |
23
songco Oct 22, 2014
其实n不大的情况下, 直接用公式比较好:
f(n)=(√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n} |
|
24
jox Oct 23, 2014
python对递归深度有限制，默认好像超过1000就不让算了，因为python不支持尾递归优化，所以即使写成尾递归的形式也不会节省资源，但是只要不超过默认的递归深度计算速度也是非常快的，不过有个技巧可以让尾递归形式的函数超过递归深度，就像这样：
 |
 |
25
monkeylyf Oct 23, 2014
一个是递归没有memorization 一个是类似dp的O(n) 当然后者快啦
|
|
26
juicy OP 多谢各位，受益匪浅~
|
|
27
hahastudio Oct 23, 2014
Python Tail Call Optimization Decorator
http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/ 顺带一提，v2ex 贴代码可以用 gist |
 |
28
leopanhf Oct 29, 2014
我觉得楼主其实不太理解 yield 吧？？
|
Select Language