java - 增加堆栈大小是否被认为是一种不好的做法？

Question

我的 Java 程序中出现 StackOverflowException，因此我使用 -Xss100m 增加了堆栈大小。这是否意味着我的代码有问题？我需要解决以下任务:

1. 你有n件衣服
2. 对于每双衣服 x、y，您都知道 x 与 y 搭配是否合适
3. 将所有衣服放入最大数量的衣柜中，但您必须确保当您从每个衣柜中取出 1 件衣服时，它看起来不错(因此每件衣服都必须看起来不错)

我将其实现为一个图表，其中顶点是衣服，当两个顶点看起来彼此不合适时，它们之间有一条边。所以基本上我需要将每个“组”连接的顶点放入一个衣柜中。为此，我使用简单的 DFS:

SimpleGraph 类的一部分

    Map<Integer, List<Integer>> edges;

    /**
     * Recursive implementation of DFS algorithm adjusted to SimpleGraph class
     * 
     * @param vertice               id of vertice we start at
     * @param visited               array holding info if given vertice was visited or not
     * @param applyToEachVertice    function applied to each vertice we visit
     * @return                      did we marked ANY vertice as visited ( if we DFS starting at
     *                               visited vertice it returns false and true otherwise )
     */
    boolean deepFirstSearch( int vertice, boolean[] visited, Consumer<Integer> applyToEachVertice )
    {
        if(visited[vertice])
           return false;
        visited[vertice] = true;
        applyToEachVertice.accept(vertice);

        // checks if vertice has any neighbours
        if(!edges.containsKey(vertice))
            return true;

        for( int v : edges.get(vertice) )
            if(!visited[v]) 
                deepFirstSearch(v, visited, applyToEachVertice);
        return true;
    }

主循环

    void resolve( SimpleGraph sg )
    {
        boolean[] visited = new boolean[sg.getVertNumber()];
        final int[] wardrobe = new int[sg.getVertNumber()];        
        for(int i = 0, warNr = 0; i < sg.getVertNumber(); i++)
        {
            final int cNr = warNr;
            if(sg.deepFirstSearch(i, visited, x -> wardrobe[x] = cNr))
                warNr++;
        }
    }

编辑: 实际上以迭代方式实现 DFS 解决了这个问题。这意味着我可以在不更改堆栈大小的情况下运行我的应用程序。

boolean deepFirstSearchNotRecursive( int vertice, boolean[] visited, Consumer<Integer> applyToEachVertice )
{
    if(visited[vertice])
        return false;

    Deque<Integer> stack = new ArrayDeque<>();  
    stack.push(vertice);

    while(!stack.isEmpty())
    {
        Integer next = stack.pop();
        visited[next] = true;
        applyToEachVertice.accept(next);
        if(!edges.containsKey(next))
            continue;
        for(Integer i : edges.get(next))
            if(!visited[i])
                stack.push(i);
    }

    return true;
}

Answer 1

我认为您的问题不是由无限递归引起的，因为您将能够从 StackOverflowException 堆栈跟踪中发现问题，并且扩展堆栈大小对您没有帮助。

虽然有正当理由增加堆栈跟踪大小，但我敢说调用链的深度与传递给应用程序的输入大小成正比。在这种情况下，您永远无法将其配置得足够大(如果您不限制输入的大小，这对于图形来说可能是一件棘手的事情)。切换到递归深度独立于输入数据的算法是正确的方法。

当然，如果您有预定义的数据集或编写了永远不会重复使用的一次性脚本，那么偷工减料比重新实现算法的核心更好。