V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
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
juicy
V2EX  ›  Python

python 在这么算 fibonacci 的时候到底在干什么!?

  •  
  •   juicy · 2014-10-22 20:23:31 +08:00 · 4731 次点击
    这是一个创建于 3686 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这几天学了点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,
    说得夸张一点,人脑算得都比它们快,
    那么,问题来了,如题
    28 条回复    2014-10-29 15:50:21 +08:00
    chlx
        1
    chlx  
       2014-10-22 20:27:15 +08:00
    贴代码
    SErHo
        2
    SErHo  
       2014-10-22 20:29:28 +08:00 via iPad
    使用递归的时候有大量重复计算的。
    Miorpher
        3
    Miorpher  
       2014-10-22 20:30:49 +08:00 via Android
    我想vote down 1楼,人家内容里不是清清楚楚写着代码来着吗!
    juicy
        4
    juicy  
    OP
       2014-10-22 20:32:04 +08:00
    @SErHo 那么是说像nodejs,c,java等语言会自带记忆功能么。。。
    juicy
        5
    juicy  
    OP
       2014-10-22 20:34:46 +08:00
    ```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
    ```
    SErHo
        6
    SErHo  
       2014-10-22 20:36:28 +08:00 via iPad
    @juicy 在计算量相同的情况下,这几种语言的确是要快点。
    eriale
        7
    eriale  
       2014-10-22 20:42:14 +08:00
    两种算法不一样,迭代器的复杂度是o(n),递归的复杂度是指数复杂度o(2^n)。
    hahastudio
        8
    hahastudio  
       2014-10-22 20:44:58 +08:00
    hahastudio
        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
    juicy
        10
    juicy  
    OP
       2014-10-22 20:49:04 +08:00
    @hahastudio 牛!
    MForever78
        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 ,说明是有编译器优化的。
    mengzhuo
        12
    mengzhuo  
       2014-10-22 21:10:05 +08:00
    算法问题,楼主就算用其他语言也是一样的结果
    jox
        13
    jox  
       2014-10-22 21:20:48 +08:00
    第一种算法python会计算lz发的这个帖子能够得到多少回帖,第二种算法python不会计算任何东西,只是简单地把第一种算法的结果偷过来,就这么简单。
    maemual
        14
    maemual  
       2014-10-22 21:28:33 +08:00
    楼主,你是在逗我(⊙_⊙)?

    你是真不懂递归?
    Viztor
        15
    Viztor  
       2014-10-22 21:44:11 +08:00
    算法太差,时间复杂度是指数级的,这种情况下使用不同语言带来的效率差异。。。
    试一下尾递归优化。
    筛选算法之类的。
    eriale
        16
    eriale  
       2014-10-22 22:12:13 +08:00
    这种树形算法没法用尾递归优化。
    想要优化直接改成迭代器方法好了,或者用@hahastudio说的内存装饰器。
    advancedxy
        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)
    rwalle
        18
    rwalle  
       2014-10-22 22:54:57 +08:00 via Android
    楼主你缺乏一些最基础的算法知识啊
    斐波那契用递归方法来计算是最愚蠢的,即使只是用于教科书讲解“递归”这个概念
    可以看看《代码大全》
    jox
        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)
    jox
        20
    jox  
       2014-10-22 23:29:55 +08:00
    v2ex怎么贴代码啊

    hello world

    怎么前面的空格都没有了?
    jox
        21
    jox  
       2014-10-22 23:30:30 +08:00
    额,v2ex会把前面的空格都处理掉啊,晕了
    xarrow
        22
    xarrow  
       2014-10-22 23:55:03 +08:00
    Python 切片 尾调,明天贴代码!
    songco
        23
    songco  
       2014-10-22 23:58:23 +08:00
    其实n不大的情况下, 直接用公式比较好:
    f(n)=(√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
    jox
        24
    jox  
       2014-10-23 00:08:15 +08:00
    python对递归深度有限制,默认好像超过1000就不让算了,因为python不支持尾递归优化,所以即使写成尾递归的形式也不会节省资源,但是只要不超过默认的递归深度计算速度也是非常快的,不过有个技巧可以让尾递归形式的函数超过递归深度,就像这样:

    monkeylyf
        25
    monkeylyf  
       2014-10-23 04:28:17 +08:00
    一个是递归没有memorization 一个是类似dp的O(n) 当然后者快啦
    juicy
        26
    juicy  
    OP
       2014-10-23 08:35:29 +08:00 via iPhone
    多谢各位,受益匪浅~
    hahastudio
        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
    leopanhf
        28
    leopanhf  
       2014-10-29 15:50:21 +08:00
    我觉得楼主其实不太理解 yield 吧??
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1053 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 18:39 · PVG 02:39 · LAX 10:39 · JFK 13:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.