<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    莊周夢蝶

    生活、程序、未來
       :: 首頁 ::  ::  :: 聚合  :: 管理

    兩段代碼的比較

    Posted on 2008-05-31 17:25 dennis 閱讀(2147) 評論(4)  編輯  收藏 所屬分類: java
    第一個程序:
    import java.util.ArrayList;
    import java.util.List;

    public class TailRecursionTest {
        
    public static void main(String[] args) {
            TailRecursionTest t 
    = new TailRecursionTest();
            
    for (int i = 0; i < 10000; i++)
                t.a(
    0);
        }

        
    public void a(int j) {
            j
    ++;
            List list 
    = new ArrayList<Integer>(100000);
            
    // 對list進行處理
        }
    }
        沒啥特殊的,僅僅是為了測試,我們將a方法調用10000次,a方法創建一個有100000個元素的list的局部變量。
    第二個程序:
    import java.util.ArrayList;
    import java.util.List;

    public class TailRecursionTest2 {
        
    public static void main(String[] args) {
            TailRecursionTest2 t 
    = new TailRecursionTest2();
            t.a(
    0);
        }

        
    public void a(int j) {
            System.out.println(j);
            j
    ++;
            
    if (j == 10000)
                
    return;
            List list 
    = new ArrayList<Integer>(100000);
            
    // 對list進行處理
            a(j);
        }
    }

        也沒啥特殊的,就是將循環換成了遞歸,a方法做的事情沒變。兩個都跑一下,程序1順利結束,程序2出問題了,啥問題?如下:
    161
    162
    163
    164
    165
    Exception in thread 
    "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.ArrayList.
    <init>(Unknown Source)
        at TailRecursionTest2.a(TailRecursionTest2.java:
    17)
        at TailRecursionTest2.a(TailRecursionTest2.java:
    20)
        at TailRecursionTest2.a(TailRecursionTest2.java:
    20)
        at TailRecursionTest2.a(TailRecursionTest2.java:
    20)
        at TailRecursionTest2.a(TailRecursionTest2.java:
    20)
       我倒,才運行166次了,heap就滿了。問題在哪呢?oh,yep,你肯定想到了,是不是重復創建list這個大集合引起的呢?它不是局部變量嗎?怎么也會溢出?是的,list是局部變量,在a的方法棧里引用著,指向heap上的大對象,更關鍵的問題在于,java是沒有尾遞歸優化的,遞歸方法是不會使用同一個棧幀,每一次遞歸調用,都將壓入新的棧幀,并且這個棧幀上又new了一個list變量,引用著heap上新的一個大集合。隨著棧深度的增加,jvm里維持著一條長長的方法調用軌跡以便你能回來,在方法沒有返回之前,這些list變量一直被各自的棧幀引用著,不能被GC,你說,能不OOM嗎?
        也許,你想到了個補救方法來挽救程序2,就是每次在處理完list后,我把它設置為null,不讓棧幀繼續引用著它,咱編寫對gc友好的代碼,這不就行了,試試:
    import java.util.ArrayList;
    import java.util.List;

    public class TailRecursionTest2 {
        
    public static void main(String[] args) {
            TailRecursionTest2 t 
    = new TailRecursionTest2();
            t.a(
    0);
        }

        
    public void a(int j) {
            System.out.println(j);
            j
    ++;
            
    if (j == 10000)
                
    return;
            List list 
    = new ArrayList<Integer>(100000);
            
    // 對list進行處理
            list = null;  //gc友好
            a(j);
        }
    }
        得意洋洋,我跑一下看看,這次跑到4000多次,但是:
    ......
    4289

    4290
    4291
    4292
    java.lang.StackOverflowError
        at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source)
        at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source)
        at java.nio.charset.CharsetEncoder.encode(Unknown Source)
        沒辦法啊,人家sun的jdk就是不支持尾遞歸優化,很不給你面子的棧溢出了。ibm的jdk據說支持尾遞歸優化,上面這個程序在ibm的jdk上可能可以正常結束,未經測試。

    總結:在java里,遞歸最好咱還是別用,老老實實地while、for;就算遞歸了,最好遞歸方法不要new太大的對象,除非你能確定遞歸的深度不是那么大。


    評論

    # re: 兩段代碼的比較  回復  更多評論   

    2008-06-03 11:02 by 隔葉黃鶯
    幫博主在 IBM JDK1.4 下運行過
    第二個例子能運行到2700多
    第三個例子能順利執行

    我也在 SUN JDK 1.6 試了一下
    第二個例子運行了 165
    第三個例子運行到 4292

    我在程序中基本不用遞歸,只在樹型結構里用過,遞歸也不好理解。

    # re: 兩段代碼的比較  回復  更多評論   

    2008-06-03 14:16 by dennis
    @隔葉黃鶯
    ibm的jdk6是實現了尾遞歸優化,這點可以確認。

    # re: 兩段代碼的比較  回復  更多評論   

    2008-06-04 00:25 by YODA
    總結寫的很好
    這個還算是很明顯的遞歸程序,有一次見過一個更狠的,JSP頁面動態include,好幾個頁面,最后搞出來一個include環(估計是好幾個人寫的),直接就StackOverFlow了。

    # re: 兩段代碼的比較  回復  更多評論   

    2012-07-08 18:27 by dys
    可以通過-xss 增加棧的深度吧
    主站蜘蛛池模板: 在线观看免费中文视频| 久久高潮一级毛片免费| 午夜一区二区免费视频| 亚洲伊人久久大香线蕉苏妲己| 香蕉免费看一区二区三区| 中文字幕亚洲一区| 99在线热播精品免费99热| 亚洲人成网77777亚洲色| 成全视频在线观看免费| 亚洲国产精品福利片在线观看| 永久免费A∨片在线观看| 亚洲a一级免费视频| 香蕉免费一区二区三区| 亚洲精品美女在线观看播放| 精品久久久久久亚洲中文字幕| 国产片免费福利片永久| 一级a性色生活片久久无少妇一级婬片免费放 | 成人性生交大片免费看中文| 国产亚洲精品a在线观看app | 一本天堂ⅴ无码亚洲道久久| 永久免费av无码网站大全| 美女隐私免费视频看| 国产亚洲AV手机在线观看| 欧洲人成在线免费| 亚洲a级在线观看| 又粗又硬又大又爽免费视频播放| 亚洲综合精品一二三区在线| 国产福利视精品永久免费 | 人成电影网在线观看免费| 亚洲AV无码专区电影在线观看| 91福利视频免费| 亚洲人av高清无码| 国产亚洲精品看片在线观看| 69视频在线观看高清免费| 亚洲AV成人无码天堂| 亚洲精品国产精品国自产观看| 无码国产精品一区二区免费式芒果| 亚洲一卡2卡3卡4卡国产网站 | 99re热精品视频国产免费| 亚洲色偷偷色噜噜狠狠99网| 亚洲中文字幕无码一久久区|