V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
kennedy32
V2EX  ›  PHP

为什么这段代码的执行时间会超过30S

  •  
  •   kennedy32 · 2013-12-25 03:46:31 +08:00 · 6313 次点击
    这是一个创建于 3987 天前的主题,其中的信息可能已经有所发展或是发生改变。
    function tuzi($x){
    if($x == 0 || $x == 1){
    return 1;
    }else{
    return tuzi($x-1)+tuzi($x-2);
    }
    }
    function testtuzi($n){
    for ($i=0;$i<=$n;$i++){
    echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
    }
    }
    testtuzi(60);
    46 条回复    1970-01-01 08:00:00 +08:00
    Rojey
        1
    Rojey  
       2013-12-25 04:04:06 +08:00   ❤️ 1
    递归,循环太多,循环套递归,递归套循环。能不慢么。
    casparchen
        2
    casparchen  
       2013-12-25 04:17:09 +08:00   ❤️ 1
    远大于2的60次方次计算,30S就能出结果?不会吧。
    能出结果已经很不错了。
    skyangel3
        3
    skyangel3  
       2013-12-25 04:55:43 +08:00 via iPhone
    60的fibonnaci sequence 运算30s 在php可以出结果。你的机器已经很牛了
    goodan
        4
    goodan  
       2013-12-25 08:54:07 +08:00 via iPhone
    @skyangel3 是飞播纳妾数列咩…
    wizardoz
        5
    wizardoz  
       2013-12-25 09:17:05 +08:00   ❤️ 1
    你用的这个算法是算法导论上用来做反面教材的。
    justfindu
        6
    justfindu  
       2013-12-25 09:20:06 +08:00
    这递归到死了吧
    kennedy32
        7
    kennedy32  
    OP
       2013-12-25 09:37:11 +08:00
    @Rojey
    @casparchen
    @skyangel3

    虚拟主机跑到35行,自己的电脑还没试过。我以为是个小运算,很简单的加法。
    kennedy32
        8
    kennedy32  
    OP
       2013-12-25 09:37:37 +08:00
    @wizardoz 正确的是怎样?
    ccidcce32167
        9
    ccidcce32167  
       2013-12-25 09:38:14 +08:00
    建议你用银河或深蓝来跑这个程序
    luoyou1014
        10
    luoyou1014  
       2013-12-25 09:39:46 +08:00
    @kennedy32
    改用循环写菲波纳锲算法
    kennedy32
        11
    kennedy32  
    OP
       2013-12-25 09:50:02 +08:00
    @luoyou1014 可以把一楼的代码改写一下么??
    zencoding
        12
    zencoding  
       2013-12-25 09:55:44 +08:00   ❤️ 1
    @kennedy32 这个是一个经典的死递归,从代码层次改变不了多少效率的
    Keita1314
        13
    Keita1314  
       2013-12-25 10:18:51 +08:00   ❤️ 1
    @kennedy32 用数组别用递归
    *a= 1;
    *(a+1) =1;
    for(int i =2;i<=n;i++)
    *(a+i) = *(a+i-1)+*(a+i-2);
    luoyou1014
        14
    luoyou1014  
       2013-12-25 10:19:49 +08:00   ❤️ 1
    @kennedy32

    <?php
    function tuzi($x){
    $sum = 0;
    $first=0;
    $second=1;
    for($i=0;$i<$x;$i++){
    $sum = $first + $second;
    $first = $second;
    $second = $sum;
    }
    return $sum;
    }

    function testtuzi($n){
    for ($i=0;$i<=$n;$i++){
    echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
    }
    }
    testtuzi(60);
    levn
        15
    levn  
       2013-12-25 10:25:29 +08:00   ❤️ 1
    TMBest
        16
    TMBest  
       2013-12-25 10:30:00 +08:00   ❤️ 1
    算法概论第一章吧,就在讲fib的各种算法,更快的算法是用矩阵。最快的是这货:
    long int fib(unsigned long int n) {
    return lround((pow(0.5 + 0.5 * sqrt(5.0), n) -
    pow(0.5 - 0.5 * sqrt(5.0), n)) /
    sqrt(5.0));
    }
    参考:http://www.evanmiller.org/mathematical-hacker.html#HN_Repost
    tonitech
        17
    tonitech  
       2013-12-25 10:40:00 +08:00   ❤️ 1
    return tuzi($x-1)+tuzi($x-2);
    这句话让你的代码变成了一个庞大的2叉树。。。n进去就是2的n-1次方!
    Golevka
        18
    Golevka  
       2013-12-25 10:43:05 +08:00
    因为这种二阶线性递归式直接写出来的话复杂度是exponential time的, 如果一定要递归的话可以用memoization. 所以说那些妄想速成码农就应该尽早砍掉重练, 回去撸一撸SICP和lambda calculus就知道踏实了.

    ref: http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html
    moondark
        19
    moondark  
       2013-12-25 10:45:07 +08:00
    @TMBest 这货也只是理论上的最快,前提是sqrt与pow函数的运行时间较短
    clippit
        20
    clippit  
       2013-12-25 10:47:20 +08:00
    @TMBest 这个是直接套通项公式了吧?
    anheiyouxia
        21
    anheiyouxia  
       2013-12-25 11:10:04 +08:00   ❤️ 1
    flyaway
        22
    flyaway  
       2013-12-25 11:15:23 +08:00
    斐波拉契数列,递归的方法存在太多的overlapping,大量重复计算,降低了效率
    skydiver
        23
    skydiver  
       2013-12-25 11:20:30 +08:00 via Android
    @TMBest 不是说正确做法是直接用lgamma函数么……
    skydiver
        24
    skydiver  
       2013-12-25 11:39:23 +08:00
    @skydiver 记错了。。那个是算阶乘。。
    kennedy32
        25
    kennedy32  
    OP
       2013-12-25 11:39:58 +08:00
    @Keita1314 额,我只看得懂php
    kennedy32
        26
    kennedy32  
    OP
       2013-12-25 11:40:16 +08:00
    @luoyou1014 谢谢
    baiyunheitu
        27
    baiyunheitu  
       2013-12-25 12:05:18 +08:00
    递归的复杂度不太乐观。
    c742435
        28
    c742435  
       2013-12-25 12:14:16 +08:00
    你用一个数组存储计算结果就可以了。算法不用改。
    kuye
        29
    kuye  
       2013-12-25 12:35:18 +08:00   ❤️ 1
    一种很肤浅的作法:
    function tuzi($x){
    static $result=array();
    if(isset($result[$x])){
    return $result[$x];
    }
    if($x == 0 || $x == 1){
    $r= 1;
    }else{
    $r= tuzi($x-1)+tuzi($x-2);
    }
    $result[$x]=$r;
    return $r;
    }
    function testtuzi($n){
    for ($i=0;$i<=$n;$i++){
    echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
    }
    }
    testtuzi(60);
    kevinroot
        30
    kevinroot  
       2013-12-25 13:29:24 +08:00
    PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
    14896 root 25 0 302m 9.9m 6948 R 100.0 0.5 1:07.71 php tuzi.php

    php tuzi.php 11870.42s user 4.86s system 99% cpu 3:18:38.25 total
    才跑到46
    dorentus
        31
    dorentus  
       2013-12-25 14:53:49 +08:00   ❤️ 2
    回答楼主的问题:

    tuzi($x) 这个函数,里面用到了前两次的计算结果 tuzi($x-1) 和 tuzi($x-2)
    但是,每次计算的结果并没有保存在什么地方,每次都是从头开始重新计算的

    例如:要计算 tuzi(4),
    >>>> 需要先计算 tuzi(3) 和 tuzi(2),分解为:
    >>>>>>>> 计算 tuzi(3):需要先计算 tuzi(2) 和 tuzi(1)
    >>>>>>>>>> 计算 tuzi(2):需要先计算 tuzi(1) 和 tuzi(0)
    >>>>>>>>>>>> 计算 tuzi(1) 得 1
    >>>>>>>>>>>> 计算 tuzi(0) 得 1
    >>>>>>>>>> 计算 tuzi(1) 得 1
    >>>>>>>> 计算 tuzi(2):需要先计算 tuzi(1) 和 tuzi(0)
    >>>>>>>>>> 计算 tuzi(1) 得 1
    >>>>>>>>>> 计算 tuzi(0) 得 1

    注意上面每一步计算都是独立的(因为之前的结果并没有保存起来供以后使用),比如 tuzi(2) 就分别计算了两次。

    然后,比如 testtuzi 的循环里面,下一步假如开始要计算 tuzi(5),需要计算 tuzi(4) 和 tuzi(3),然后虽然上次循环里面 tuzi(4) 和 tuzi(3) 其实已经都算过了,但是不行,这一次里面还是得重新从头开始算。

    @kuye 的方法是拿空间换时间的方法(如果我对 PHP 的 static 没理解错的话),拿很少的空间(那个 static array)保存了每次 tuzi($x) 计算的结果,大大提高了后面计算的速度。
    kennedy32
        32
    kennedy32  
    OP
       2013-12-25 16:49:14 +08:00
    @dorentus 非常感谢,最详细的解答
    kennedy32
        33
    kennedy32  
    OP
       2013-12-25 16:50:21 +08:00
    @kuye 改动最小的方案,谢谢。其实这是MIT600SC第六课递归的例子,能用递归当然最好了
    vibbow
        34
    vibbow  
       2013-12-25 18:17:15 +08:00
    能30s跑完这个代码的电脑都是神级的电脑了...
    我的电脑还在慢慢跑,我看多久能跑完...
    pljhonglu
        35
    pljhonglu  
       2013-12-25 18:37:35 +08:00
    其实 LZ 是来秀电脑配置的。。。
    hourui
        36
    hourui  
       2013-12-25 19:25:18 +08:00
    楼上正解...
    kofj
        37
    kofj  
       2013-12-25 20:22:44 +08:00
    @levn 怎么插入github的这种格式化了的代码的?
    faceair
        38
    faceair  
       2013-12-25 20:36:04 +08:00
    kurtis
        39
    kurtis  
       2013-12-25 22:54:37 +08:00
    @dorentus
    看到现在,只有你got point

    这个问题,本质就是应该拿空间换时间。
    有张表记录下每次计算的结果作为缓存,以后不用每次计算就可以了。

    这个是大学作业吗?好像很久很久以前有人讨论过这个问题了,
    TheJuli
        40
    TheJuli  
       2013-12-25 23:01:31 +08:00
    用超算平台跑一遍试试
    tonic
        41
    tonic  
       2013-12-25 23:21:22 +08:00
    可以改成尾递归的... 或者直接改迭代
    kennedy32
        42
    kennedy32  
    OP
       2013-12-25 23:39:09 +08:00
    @vibbow
    @pljhonglu
    @hourui

    E3 1230 v2 30s跑到36行
    vibbow
        43
    vibbow  
       2013-12-26 06:33:17 +08:00
    @kennedy32 你怎么做到那么快的?
    我 i7-4930mx 跑到 testtuzi(36); 花了332秒...
    wizardoz
        44
    wizardoz  
       2013-12-26 09:19:32 +08:00
    @kennedy32 正确的应该是从底向上,从n = 1 累加到n = x。所以问题不在于用了递归调用,而是在于选了一种有很多冗余计算的算法。
    kennedy32
        45
    kennedy32  
    OP
       2013-12-26 12:07:55 +08:00
    @vibbow 我还觉得慢呢,虚拟主机都能跑35
    huafang
        46
    huafang  
       2014-01-14 22:30:38 +08:00
    你函数还没定义好,就内部调用。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   926 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 22:18 · PVG 06:18 · LAX 14:18 · JFK 17:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.