庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

两段代码的比较

Posted on 2008-05-31 17:25 dennis 阅读(2125) 评论(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 增加栈的深度吧

只有注册用户登录后才能发表评论。


网站导航: