在使用函数式语言之后,我开始在Java中使用更多的递归 - 但是语言似乎有一个相对较浅的调用堆栈,大约1000.
有没有办法让调用堆栈更大？就像在Erlang中一样,我可以创建数百万次调用的函数吗？
当我做项目欧拉问题时,我越来越注意到这一点.
谢谢.
1> Apocalisp..：
增加堆栈大小仅用作临时绷带.正如其他人所指出的那样,你真正想要的是尾部调用消除,而Java由于各种原因没有这个.但是,如果你愿意,你可以作弊.
手里拿着红丸？好的,请这样.
有一些方法可以为堆交换堆栈.例如,不要在函数内进行递归调用,而是让它返回一个惰性数据结构,在评估时调用它.然后,您可以使用Java的for-construct来展开"堆栈".我将用一个例子来证明.考虑一下这个Haskell代码:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
请注意,此函数从不评估列表的尾部.因此该函数实际上不需要进行递归调用.在Haskell中,它实际上为尾部返回一个thunk,如果需要它就会被调用.我们可以在Java中做同样的事情(这使用Functional Java中的类):
public Stream map(final F f, final Stream as)
{return as.isEmpty()
? nil()
: cons(f.f(as.head()), new P1>()
{public Stream _1()
{return map(f, as.tail);}});}
请注意,它Stream由type的值和type A的值组成P1,类似于在调用_1()时返回流的其余部分的thunk.虽然它看起来像递归,但是没有对map进行递归调用,而是成为Stream数据结构的一部分.
然后可以使用常规for-construct解开.
for (Stream b = bs; b.isNotEmpty(); b = b.tail()._1())
{System.out.println(b.head());}
这是另一个例子,因为你在谈论Project Euler.这个程序使用相互递归的函数,并且不会烧掉堆栈,即使是数百万次调用:
import fj.*; import fj.data.Natural;
import static fj.data.Enumerator.naturalEnumerator;
import static fj.data.Natural.*; import static fj.pre.Ord.naturalOrd;
import fj.data.Stream; import fj.data.vector.V2;
import static fj.data.Stream.*; import static fj.pre.Show.*;
public class Primes
{public static Stream primes()
{return cons(natural(2).some(), new P1>()
{public Stream _1()
{return forever(naturalEnumerator, natural(3).some(), 2)
.filter(new F()
{public Boolean f(final Natural n)
{return primeFactors(n).length() == 1;}});}});}
public static Stream primeFactors(final Natural n)
{return factor(n, natural(2).some(), primes().tail());}
public static Stream factor(final Natural n, final Natural p,
final P1> ps)
{for (Stream ns = cons(p, ps); true; ns = ns.tail()._1())
{final Natural h = ns.head();
final P1> t = ns.tail();
if (naturalOrd.isGreaterThan(h.multiply(h), n))
return single(n);
else {final V2 dm = n.divmod(h);
if (naturalOrd.eq(dm._2(), ZERO))
return cons(h, new P1>()
{public Stream _1()
{return factor(dm._1(), h, t);}});}}}
public static void main(final String[] a)
{streamShow(naturalShow).println(primes().takeWhile
(naturalOrd.isLessThan(natural(Long.valueOf(a[0])).some())));}}
为堆交换堆栈可以做的另一件事是使用多个线程.我们的想法是,不是进行递归调用,而是创建一个执行调用的thunk,将此thunk关闭到新线程并让当前线程退出该函数.这就是像Stackless Python这样的东西背后的想法.
以下是Java中的示例.抱歉在没有import static条款的情况下看起来有点不透明:
public static Promise foldRight(final Strategy s,
final F> f,
final B b,
final List as)
{return as.isEmpty()
? promise(s, P.p(b))
: liftM2(f).f
(promise(s, P.p(as.head()))).f
(join(s, new P1>>()
{public Promise _1()
{return foldRight(s, f, b, as.tail());}}));}
Strategy s由一个线程池支持,并且该promise函数将一个thunk交给线程池,返回一个Promise非常类似的东西java.util.concurrent.Future,只是更好.看这里.关键是上面的方法将右递归数据结构折叠到O(1)堆栈中的右侧,这通常需要消除尾部调用.因此,我们有效地实现了TCE,以换取一些复杂性.您可以按如下方式调用此函数:
Strategy s = Strategy.simpleThreadStrategy();
int x = foldRight(s, Integers.add, List.nil(), range(1, 10000)).claim();
System.out.println(x); // 49995000
请注意,后一种技术非常适用于非线性递归.也就是说,它将以常量堆栈运行,甚至是没有尾调用的算法.
你可以做的另一件事就是采用一种叫做蹦床的技术.蹦床是一种计算,具体化为数据结构,可以逐步实现.该功能的Java库包括Trampoline我写的数据类型,从而有效地让你把任何函数调用到尾调用.作为一个例子,这里是一个蹦床foldRightC,在常量堆栈中向右折叠:
public final Trampoline foldRightC(final F2 f, final B b)
{return Trampoline.suspend(new P1>()
{public Trampoline _1()
{return isEmpty()
? Trampoline.pure(b)
: tail().foldRightC(f, b).map(f.f(head()));}});}
它与使用多个线程的原理相同,除了不是在自己的线程中调用每个步骤,我们在堆上构造每个步骤,非常像使用a Stream,然后我们在一个循环中运行所有步骤Trampoline.run.
这是我见过的一些最疯狂的Java代码,非常详细的解释+1.
@Nik:最大的性能改进是从不工作(StackOverflowError)到工作.
2> Tom..：
我想你可以使用这些参数
-ss Stacksize以增加本机堆栈大小或
-oss Stacksize增加Java堆栈大小,
默认本机堆栈大小为128k,最小值为1000字节.默认的Java堆栈大小为400k,最小值为1000字节.
http://edocs.bea.com/wls/docs61/faq/java.html#251197
编辑:
在阅读了第一条评论(Chuck's)之后,以及重新阅读问题并阅读其他答案,我想澄清一下,我将这个问题解释为"增加堆栈大小".我不打算说你可以拥有无限的堆栈,例如在函数式编程中(一种我只是触及其表面的编程范例).
这可以为您提供更多级别,但堆栈大小仍然有限.你将无法像高功率消除的功能语言一样无限地递归.
链接断开。
3> Jon Skeet..：
这取决于JVM是否使用尾递归 - 我不知道它们是否有任何影响,但你不应该依赖它.特别是,改变堆栈大小将非常很少是做正确的事,除非你有你需要多少递归级别实际上使用了硬限制,你知道每个会到底有多少堆栈空间占用.非常脆弱.
基本上,您不应该在不为其构建的语言中使用无界递归.你不得不使用迭代,我害怕.是的,有时可能会有轻微的疼痛:(
关于尾部调用优化的工作正在进行中,但它目前在Java中不受支持,因为它打破了对堆栈外观的一些期望,这对Java的安全模型(以及不太重要的事情,如堆栈跟踪)很重要.http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm
4> angry person..：
如果你不得不问,你可能做错了什么.
现在,虽然您可能找到一种方法来增加java中的默认堆栈,但是我只需要添加2美分就可以找到另一种方法来执行您想要的操作,而不是依赖于增加的堆栈.
由于java规范没有强制JVM实现尾递归优化技术,解决问题的唯一方法是通过减少需要保留的局部变量/参数的数量来减少堆栈压力跟踪,或理想情况下,只是显着降低递归的级别,或者根本不重写而没有递归.
5> Sean..：
大多数函数式语言都支持尾递归.但是,大多数Java编译器都不支持这一点.而是进行另一个函数调用.这意味着你可以在递归调用的数量上总是有一个上限(因为你最终会耗尽堆栈空间).
使用尾递归,您可以重用递归函数的堆栈帧,因此您对堆栈没有相同的约束.
6> 小智..：
您可以在命令行上设置:
java -Xss8M类
7> Svante..：
在Java VM上运行的Clojure非常希望实现尾调用优化,但它不能由于JVM字节码的限制(我不知道细节).因此,它只能通过一种特殊的"复现"形式来帮助自己,这种形式实现了一些你期望从正确的尾递归中获得的基本功能.
无论如何,这意味着JVM目前无法支持尾调用优化.我强烈建议不要将递归用作JVM上的通用循环结构.我个人认为Java不是一种足够高级的语言.
京公网安备 11010802040832号