Как пройти эту древовидную структуру без рекурсии C#

Этот код сохраняет данные цикла в базе данных, но у меня возникают проблемы с производительностью, так как данные настолько велики, что сохраняет огромное количество записей, и в этом случае рекурсия вызывает очень большую нагрузку на память, поэтому мне нужно альтернативное решение рекурсии, зная, что это n-арное дерево.

    private void ProcessLoops(LoopContainer parent, InboundLoop parentLoop)
    {
        foreach (var segment in parent.Segments)
        {
            if (segment is Loop)
            {
                var segmentLoop = segment as Loop;
                var inboundLoop = new InboundLoop()
                {
                    Inbound834RegisterId = RegisterId,
                    InboundSTId = InboundST.InboundSTId,
                    LoopName = segmentLoop.Specification.Name,
                    LoopNumber = segmentLoop.Specification.LoopId,
                    Sequence = _loopSequence++
                };

                if (parentLoop == null)
                {
                    inboundLoop.InboundLoopId = InboundLoopService.Instance.AddInboundLoop(inboundLoop);
                }
                else
                {
                    inboundLoop.ParentLoopId = parentLoop.InboundLoopId;
                    inboundLoop.InboundLoopId = InboundLoopService.Instance.AddInboundLoop(inboundLoop);
                }
                ProcessLoops(segmentLoop, inboundLoop);
            }
        }
    }
Источник

1 ответ

Решение

Каждая рекурсия может быть задана как цикл.
Для поиска по глубине вы можете:

  1. Поместите корень в очередь
  2. Выдвигая очередь, вы помещаете всех дочерних элементов в очередь
  3. Сохранить предмет в БД

Изменить: добавлен код для запроса

var nodeQueue = new Queue<Node>();
nodeQueue.Add(Tree.Root);
while (!nodeQueue.Empty())
{
    var item = nodeQueue.Pop();
    foreach(Node child in item.Children)
    {
        nodeQueue.Add(child);
    }
    db.Add(item.Data);
}

Другой способ, который займет больше времени, - это рассчитать максимальное количество элементов в дереве (я предполагаю, что оно может быть не сбалансировано).

  1. Выполнить в цикле от 0 до MaxItems.
  2. Каждое число конвертируем в двоичное.
  3. Используйте 0 для левого и 1 для правого.
  4. Для каждой цифры двигайтесь соответственно в дереве. Таким образом, каждое число представляет отдельный узел в вашем дереве, и вы можете проходить по дереву в определенном порядке.

Изменить: добавлен код для запроса

var length = Tree.Count;
var depth = Tree.Depth;
var maxLength = Power(2,depth)-1
for (var i=0; i<maxLength; i++)
{
    db.Add(Tree.GetByNumber(i));
}

Дайте мне знать, если вы хотите более закодированный ответ (если это актуально)

Источник

Я создал способ упорядочить элементы в том порядке, в котором они будут обрабатываться рекурсивно, без использования рекурсии. Поскольку это общий метод расширения, его можно использовать для чего угодно. Например, вы могли быT быть Action<>так что вы можете обрабатывать их, когда захотите. Вот метод расширения:

public static class EnumerableExtensions
{
    public static List<T> ToRecursiveOrderList<T>(this IEnumerable<T> collection, Expression<Func<T, IEnumerable<T>>> childCollection)
    {
        var resultList = new List<T>();
        var currentItems = new Queue<(int Index, T Item, int Depth)>(collection.Select(i => (0, i, 0)));
        var depthItemCounter = 0;
        var previousItemDepth = 0;
        var childProperty = (PropertyInfo)((MemberExpression)childCollection.Body).Member;
        while (currentItems.Count > 0)
        {
            var currentItem = currentItems.Dequeue();
            // Reset counter for number of items at this depth when the depth changes.
            if (currentItem.Depth != previousItemDepth) depthItemCounter = 0;
            var resultIndex = currentItem.Index + depthItemCounter++;
            resultList.Insert(resultIndex, currentItem.Item);

            var childItems = childProperty.GetValue(currentItem.Item) as IEnumerable<T> ?? Enumerable.Empty<T>();
            foreach (var childItem in childItems)
            {
                currentItems.Enqueue((resultIndex + 1, childItem, currentItem.Depth + 1));
            }
            previousItemDepth = currentItem.Depth;
        }

        return resultList;
    }
}

Вот пример того, как его использовать. Такая конструкция будет сглажена.

  • А
  • B
  • C
    • D
      • E
    • F
    • грамм
    • ЧАС
      • я
  • J
    • K
    • L
      • M
  • N
  • O
    • п
    • Q
      • р
      • S
    • Т
internal class Alpha
{
    public string Value { get; set; }
    public Alpha[] Children { get; set; }

    public override string ToString() => Value;
}

internal class Program
{
    public static void Main()
    {
        var items = new []
        {
            new Alpha { Value = "A" },
            new Alpha { Value = "B" },
            new Alpha { Value = "C", Children = new []
            {
                new Alpha { Value = "D", Children = new []
                {
                    new Alpha { Value = "E" },
                }},
                new Alpha { Value = "F" },
                new Alpha { Value = "G" },
                new Alpha { Value = "H", Children = new []
                {
                    new Alpha { Value = "I" },
                }},
            }},
            new Alpha { Value = "J", Children = new []
            {
                new Alpha { Value = "K" },
                new Alpha { Value = "L", Children = new []
                {
                    new Alpha { Value = "M" },
                }},
            }},
            new Alpha { Value = "N" },
            new Alpha { Value = "O", Children = new []
            {
                new Alpha { Value = "P" },
                new Alpha { Value = "Q", Children = new []
                {
                    new Alpha { Value = "R" },
                    new Alpha { Value = "S" },
                }},
                new Alpha { Value = "T" },
            }},
        };
        var ordered = items.ToRecursiveOrderList(a => a.Children);
        foreach (var item in ordered)
        {
            Console.WriteLine(item);
        }
    }
}

Результат выглядит так:

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
Источник 
public class NodeInfo
{
    public object Node { get; set; }
    public Queue<PropertyInfo> PropertiesToBeVisited{ get; set; }
}

public static class TypeExtensions
{
    public static bool IsComplex(this Type type)
    {
        return !type.IsValueType && type != typeof(string);
    }

    public static bool IsCollection(this Type type)
    {
        var collectionTypeName = typeof(ICollection<>).Name;
        return type.Name == collectionTypeName || type.GetInterface(typeof(ICollection<>).Name) != null;
    }
}

    public static void TraverseObjectTree(object data)
    {
        var currentNode = data;
        var currentNodeProperties = new Queue<PropertyInfo>(data.GetType().GetProperties());
        var nodeTracker = new Queue<NodeInfo>();
        while (currentNodeProperties.Count != 0 || nodeTracker.Count != 0)
        {
            if (currentNodeProperties.Count == 0 && nodeTracker.Count != 0)
            {
                var currentNodeInfo = nodeTracker.Dequeue();
                currentNode = currentNodeInfo.Node;
                currentNodeProperties = currentNodeInfo.PropertiesToBeVisited;
                continue;
            }
            var currentNodeProperty = currentNodeProperties.Dequeue();
            var currentNodePropertyType = currentNodeProperty.PropertyType;
            if (currentNodePropertyType.IsComplex())
            {
                var value = currentNode?.GetType().GetProperty(currentNodeProperty.Name)
                    ?.GetValue(currentNode, null);
                if (value != null)
                {
                    object node;
                    if (currentNodePropertyType.IsCollection())
                    {
                        var elementType = currentNodePropertyType.IsArray
                                ? value.GetType().GetElementType()
                                : value.GetType().GetGenericArguments()[0];
                        node = Activator.CreateInstance(elementType ?? throw new InvalidOperationException());
                    }
                    else
                    {
                        node = value;
                    }
                    nodeTracker.Enqueue(new NodeInfo
                    {
                        Node = currentNode,
                        PropertiesToBeVisited = currentNodeProperties
                    });
                    currentNode = node;
                    currentNodeProperties = new Queue<PropertyInfo>(node.GetType().GetProperties());
                    Console.WriteLine(currentNodeProperty.Name);
                    continue;
                }
            }
            Console.WriteLine(currentNodeProperty.Name);
        }
    }

Это сделает работу!

Источник
Другие вопросы по тегам