StackoverflowException 递归和执行缓慢

Question

我有这个代码

private static void Count(List<DataRowSet> rows, int id, ref int count)
{
    foreach (DataRowSet row in rows) {
        if (row.parentId == id) {
            count++;

            Count(rows, row.Id, ref count);
        }
    }
}

和这个班级

public class DataRowSet
{
    public int Id;
    public int parentId;

    public DataRowSet(int id, int parent)
    {
        this.Id = id;
        this.parentId = parent;
    }
}

我想List<DataRowSet>用特定的 id计算 a 的每个孩子。

Count(dataList, 1, ref cnt);

那行得通，但是一旦我有超过 8000 个条目 dataListStackOverflow 异常中。代码也很慢，找到所有条目大约需要 1.5 秒。

我该怎么做才能解决这个问题？

Answer 1

StackOverflowException发生这种情况是因为您的递归太深了。它可以正常工作到 8000，上面的所有内容对于堆栈来说都太多了。您可以通过使用 aStack<DataRowSet>并将项目推入其中而不是递归调用该函数来解决此问题。

查看您的DataRowSet课程，它似乎是一个平面列表，因此有一种简单的方法可以通过使用ILookup<int, DataRowSet>. 这样 - 而不是一遍又一遍地遍历列表 - 您可以使用键来查找任何相关项目。

首先，您必须推送堆栈中的顶级项目。这可以像这样完成。

Stack<DataRowSet> stack = new Stack<DataRowSet>(
    dataRows.Where(x => x.Id == id));

使用dataRows.ToLookup，您可以按条目对条目进行分组ParentId。

ILookup<int, DataRowSet> dataLookup = dataRows.ToLookup(x => x.parentId);

之后，您只需要循环stack直到它为空，同时推送具有正确 id 的新项目。

while (stack.Count > 0) {
    DataRowSet currentRow = stack.Pop();

    foreach (DataRowSet rowSet in dataLookup[currentRow.Id]) {
        stack.Push(rowSet);
    }
}

这样你就不用担心 StackOverflowException了，性能也得到了提高。

总之，您的新函数看起来有点像这样。

private static int Count(List<DataRowSet> dataRows, int id)
{
    int totalDescendants = 0;

    Stack<DataRowSet> stack = new Stack<DataRowSet>(
        dataRows.Where(x => x.Id == id));

    ILookup<int, DataRowSet> dataLookup = dataRows.ToLookup(x => x.parentId);

    while (stack.Count > 0) {
        DataRowSet currentRow = stack.Pop();

        foreach (DataRowSet rowSet in dataLookup[currentRow.Id]) {
            totalDescendants++;
            stack.Push(rowSet);
        }
    }

    return totalDescendants;

}

并且可以这样调用

int cnt = Count(dataList, 1);