时间戳

首页 > 解决方案 > 什么时候可以增加 jvm (-Xss) 的最大堆栈大小？

java - 什么时候可以增加 jvm (-Xss) 的最大堆栈大小？

问题描述

我在做什么 ？

我在 coursera 上做一门课程，要求我编写一个计算树高的程序。输入是一个父数组，其中每个索引是节点，其值是节点的父节点。如果节点是根节点，则其值为-1。

到目前为止我做了什么？

我编写了一个算法，通过递归遍历其子节点到其根节点并将中间子节点的高度保存在数组（深度变量）中来检查树的高度。因为它是一个recursion我经常看到的一个stackoverflow exception很自然的，因为堆栈大小对于大树来说是不够的。

为了摆脱这个异常，我尝试为我的递归调用找到最佳值，结果它接近3100k。此外，当我看到针对一些预定义测试用例测试我的算法的代码时，也将1 << 26 的堆栈大小传递到线程构造函数中。

我需要知道什么？

  1. 有没有更好的方法来解决这个问题？

  2. 像这样增加堆栈大小可以吗？

这是代码

int computeHeight() {
    int[] depth = new int[n];
    int maxHeight = 0;
    for (int i = 0; i < n; i++) {
        int height = computeHeight(parent, depth, i);
        maxHeight = Math.max(height, maxHeight);
    }
    return maxHeight;
}

private int computeHeight(int[] parent, int[] depth, int idx) {
    if (parent[idx] == -1) {
        // root found
        depth[idx] = 1;
        return depth[idx];
    }
    // depth of parent unknown
    if (depth[parent[idx]] == 0) {
        computeHeight(parent, depth, parent[idx]);
    }
    depth[idx] = depth[parent[idx]] + 1;
    return depth[idx];
}

标签： javaalgorithmrecursion

解决方案

如果树向右或向左倾斜，例如如果每个节点只有一个右子节点，那么递归很容易导致堆栈溢出（再次取决于堆栈设置），不确定其中一个输入是否适合您的情况。

这可以以迭代方式完成：

a）将所有父母（数组中的值）添加到 HashSet

b）然后遍历所有节点（这里只是从 0 到 n 的索引）并查看它是否存在于集合中，如果不是它是叶子。

c）然后从叶子遍历到根以获得高度，同时将每个节点的高度存储在一个数组中，这样下次你就不必再爬上相同的路径了。

d) 每次更新最大高度。

推荐阅读