使用递归进行 3D 数组操作——导致 StackOverflow(不是无限的！)

问题描述

我昨天发布了一个关于类似问题的问题，但我编写了一些不同的代码，现在遇到了不同的问题.这是我导致 StackOverflow 的代码.

I recently posted a question yesterday about a similar issue, but I have coded up something a little different and now have a different problem. Here is my code that is causing a StackOverflow.

** 请注意，3D 网格数组最多包含 100 万个元素，并且可以达到大约 6400 万个元素(存储枚举).

** Note that the 3D grid array is upwards of 1 million elements and can reach up to around 64 million elements (stores enums).

** 另请注意，这不会进入无穷大.在小数据集上，该算法运行良好.

** Also note that this is not going into infinity. On small data sets, this algorithm works fine.

这可能是由极端递归引起的吗?我该如何处理(这是我算法的重要组成部分！)?我做了一些研究，听说过使用队列，即使只是大规模的 for 循环.

Is this likely caused by the extreme recursion? How do I handle this (this is an essential part of my algorithm!)? I've done some research and have heard using a queue, for even just massive for-loops.

什么会降低导致 stackoverflow 的可能性?

What will reduce the likelihood of causing a stackoverflow?

谢谢！

/**
 * Fills all void cells in the 3D grid of Atom.
 *
 * @param x
 *            The starting x coordinate
 * @param y
 *            The starting y coordinate
 * @param z
 *            The starting z coordinate
 */
private void fillAllVoidCells(int x, int y, int z)
{
    // Base case -- If not BLOATED_ATOM, BOUNDING_BOX,
    // or VOID then must be a cavity (only 4 CellType
    // enum types.
    if ((grid[x][y][z] == CellType.BLOATED_ATOM)
        || grid[x][y][z] == CellType.BOUNDING_BOX
        || grid[x][y][z] == CellType.VOID)
    {
        // Pop off runtime stack
        return;
    }
    else
    {
        // Set to void then check all surrounding cells.
        grid[x][y][z] = CellType.VOID;

        fillAllVoidCells(x + 1, y, z); // right
        fillAllVoidCells(x - 1, y, z); // left
        fillAllVoidCells(x, y + 1, z); // in front
        fillAllVoidCells(x, y - 1, z); // behind
        fillAllVoidCells(x, y, z + 1); // above
        fillAllVoidCells(x, y, z - 1); // below
    }
}

====== 编辑 ====== 使用堆栈实现的新方法(根据 Roee Gavirel 帮助)这会是一个正确的实现吗?

===== EDIT ====== New Method Implemented Using a Stack (per Roee Gavirel help)Would this be a correct implementation?

   // ----------------------------------------------------------
    /**
     * Fills all void cells in the 3D grid of Atom.
     *
     * @param x
     *            The starting x coordinate
     * @param y
     *            The starting y coordinate
     * @param z
     *            The starting z coordinate
     */
    private void fillAllVoidCells(int x, int y, int z)
    {
        Point p = new Point(x, y, z);

        stack.push(p);

        while (!stack.isEmpty())
            p = stack.top();
        stack.pop();

        // Base case -- If not BLOATED_ATOM, BOUNDING_BOX,
        // or VOID then must be a cavity (only 4 CellType
        // enum types.
        CellType state = grid[p.x][p.y][p.z];

        if ((state == CellType.BLOATED_ATOM) || state == CellType.BOUNDING_BOX
            || state == CellType.VOID)
        {
            return;
        }
        else
        {
            // Set to void then check all surrounding cells.
            grid[p.x][p.y][p.z] = CellType.VOID;
            Point tempP = p;

            tempP.x = p.x - 1;
            stack.push(tempP);
            tempP.x = p.x + 1;
            stack.push(tempP);
            tempP.x = p.x; // return to original x coordinate

            tempP.y = p.y - 1;
            stack.push(tempP);
            tempP.y = p.y + 1;
            stack.push(tempP);
            tempP.y = p.y; // return to original y coordiante

            tempP.z = p.z - 1;
            stack.push(tempP);
            tempP.z = p.z + 1;
            stack.push(tempP);
            tempP.z = p.z; // return to original z coordinate
        }
    }

推荐答案

这最有可能导致溢出.您可以(并且应该)做的是避免使用自己的堆栈来存储数据并避免递归.

This is most likely to cause an overflow. what you can (and should) do to avoid it is to use your own stack for the data and avoid recursion.

在你的情况下:
1. 有一堆相关的点 (x,y,z)，其中包含您最初调用 fillAllVoidCells 的点.
2. while 栈不是空的，你应该检查一下
3.如果是cavity，将周围的点加入堆栈.

In you case:
1. have a stack of relevant points (x,y,z) which have the point you initially called fillAllVoidCells with.
2. while the stack is not empty you should do your checks
3. If it's cavity add the surrounding points to the stack.

==编辑==类似的东西:

==EDIT==something like that:

struct point {
    int x,y,z;
}

private void fillAllVoidCells(int x, int y, int z)
{
    std::list<point> Ps;
    point p;
    p.x = x;
    p.y = y;
    p.z = z;
    Ps.push_back(p);

    while (!Ps.empty())
        p = Ps.back();
        Ps.pop_back();

        // Base case -- If not BLOATED_ATOM, BOUNDING_BOX,
        // or VOID then must be a cavity (only 4 CellType
        // enum types.
        auto state = grid[p.x][p.y][p.z];
        if ((state == CellType.BLOATED_ATOM)
            || state == CellType.BOUNDING_BOX
            || state == CellType.VOID)
        {
            continue;
        }
        else
        {
            // Set to void then check all surrounding cells.
            grid[p.x][p.y][p.z] = CellType.VOID;

            point tempP = p;
            tempP.x = P.x - 1;
            Ps.push_back(tempP);
            tempP.x = P.x + 1;
            Ps.push_back(tempP);
            tempP.y = P.y - 1;
            Ps.push_back(tempP);
            tempP.y = P.y + 1;
            Ps.push_back(tempP);
            tempP.z = P.z - 1;
            Ps.push_back(tempP);
            tempP.z = P.z + 1;
            Ps.push_back(tempP);
        }
    }
}

这篇关于使用递归进行 3D 数组操作——导致 StackOverflow(不是无限的！)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！