0

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.

** 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.

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.

What will reduce the likelihood of causing a stackoverflow?

Thank you!

/**
 * 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
    }
}

===== 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
        }
    }
4

1 回答 1

0

这很可能导致溢出。您可以（并且应该）做的避免它是使用您自己的数据堆栈并避免递归。

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

==EDIT== 类似的东西：

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);
        }
    }
}
于 2013-04-30T07:59:16.307 回答