c# - StackoverflowException递归和执行缓慢

我有这个代码

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;
    }
}

我想计算具有特定ID的List<DataRowSet>的每个孩子。

Count(dataList, 1, ref cnt);

那行得通，但是一旦我在dataList中有8000多个条目，就会发生StackOverflow异常。代码也很慢，大约需要1.5秒才能找到所有条目。

我该如何解决？

最佳答案

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);