c# - 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>的每个 child 具有特定的 ID。

Count(dataList, 1, ref cnt);

这可行，但是一旦我在 dataList 中有超过 8000 个条目发生 StackOverflow 异常。而且代码速度很慢，大约需要 1.5 秒才能找到所有条目。

我该如何解决这个问题？

Answer 1

StackOverflowException发生这种情况是因为你的递归太深了。它在 8000 以内都可以正常工作，上面的所有内容对于堆栈来说都太多了。您可以使用 Stack<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);