c# - 排序算法在处理较大的数据集时会导致堆栈溢出？

Question

我正在寻找一种更好的方法来对以下类型的数据进行排序。以下适用于较小的数据集(在某些系统上为 2000，在其他 9000 上)但在处理较大的数据集时会导致堆栈溢出

保存数据的结构如下所示

public class AttributeItem
{
    public string AttributeType { get; set; }
    public string Title { get; set; }
    public string Value { get; set; }
    public int ObjectID { get; set; }
    public bool CanModify { get; set; }
    public bool CanDelete { get; set; }
    public bool? IsParent { get; set; }
    public int SortID { get; set; }
    public int? ParentSortID { get; set; }
    public bool Deleted { get; set; }
}

public class AttributeItemNode
{
    public AttributeItem Item {get;set;}
    public int Depth {get;set;}

    public AttributeItemNode(AttributeItem item , int Depth)
    {
        this.Item = item ;
        this.Depth = Depth;
    }
}

这是一个数据示例，需要将其分类到单个对象中，并使用 int 指示其深度。子级别可能比示例数据中显示的三个级别更深

var items = new List<AttributeItem>();
items.Add(new AttributeItem{Title ="Parent1", ObjectID=1,SortID =1, IsParent= true, ParentSortID = Int32.MinValue});

items.Add(new AttributeItem{Title ="FooChild", ObjectID=2,SortID =2, IsParent= false, ParentSortID = 1});

items.Add(new AttributeItem{Title ="Parent2", ObjectID=4,SortID =4, IsParent= true, ParentSortID = Int32.MinValue});

items.Add(new AttributeItem{ Title ="Parent2Child1", ObjectID=5,SortID =5, IsParent= false, ParentSortID = 4});

items.Add(new AttributeItem{Title ="Parent2Child2", ObjectID=7,SortID =7, IsParent= false, ParentSortID = 4});

items.Add(new AttributeItem{Title ="Parent2Child2Child1", ObjectID=6,SortID =6, IsParent= false, ParentSortID = 5});

预期的输出如下(我已经从对象中删除了不相关的数据以提高可读性)

Depth = 0 Title ="Parent1"
Depth = 1 Title ="FooChild" 
Depth = 0 Title ="Parent2"
Depth = 1 Title ="Parent2Child1" 
Depth = 2 Title ="Parent2Child2Child1"
Depth = 1 Title ="Parent2Child2"

这里是实际的排序代码

    public static IList<AttributeItemNode> SortAttributeItems(IList<AttributeItem> list)
    {
        List<AttributeItemNode> newList = new List<AttributeItemNode>();
        SortAttributeItems(list, null, 0, newList);

        return newList;
    }

    private static void SortAttributeItems(IList<AttributeItem> list, AttributeItem currentItem, int depth, List<AttributeItemNode> newList)
    {
        AttributeItem newItem = null;
        // look for children
        if (currentItem != null)
        {
            foreach (AttributeItem item in list)
            {
                if (item.ParentSortID.HasValue && item.ParentSortID.Value != Int32.MinValue && item.ParentSortID.Value == currentItem.SortID)
                {
                    newList.Add(new AttributeItemNode(item, (depth + 1)));
                    SortAttributeItems(list, item, depth + 1, newList); 
                }
            }
        }

        if (depth == 0)
        {
            foreach (AttributeItem item in list)
            {
                if (!item.ParentSortID.HasValue || item.ParentSortID.Value == Int32.MinValue) 
                {
                    if (currentItem == null || item.SortID >= currentItem.SortID) 
                    {
                        if (newItem == null || newItem.SortID >= item.SortID)
                        {
                            newItem = item;
                        }
                    }
                }
            }
        }

        if (newItem != null)
        {
            newList.Add(new AttributeItemNode(newItem, depth));
            list.Remove(newItem);
            SortAttributeItems(list, newItem, depth, newList);
        }

    }

Answer 1

这个问题可以不使用递归有效地解决。它可以分为两部分 - 创建树结构并使用迭代将树展平 pre-order Depth First Traversal , 对每个级别进行排序。

对于第一部分，我们可以使用 LINQ ToLookup在 O(N) 时间内通过 ParentSortID 创建快速查找结构的方法。

对于第二部分，在DRY之后原则我将使用我对 How to flatten tree via LINQ? 的回答中的通用方法通过创建允许从项目和深度投影到自定义结果的重载(如您所见，我已经拥有):

public static class TreeUtils
{
    public static IEnumerable<TResult> Expand<T, TResult>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector, Func<T, int, TResult> resultSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return resultSelector(item, stack.Count);
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

这里是有问题的方法的实现:

public static IList<AttributeItemNode> SortAttributeItems(IList<AttributeItem> list)
{
    var childrenMap = list.ToLookup(e => e.ParentSortID ?? int.MinValue);
    return childrenMap[int.MinValue].OrderBy(item => item.SortID)
        .Expand(parent => childrenMap[parent.SortID].OrderBy(item => item.SortID),
            (item, depth) => new AttributeItemNode(item, depth))
        .ToList();
}