Как найти родителя и родителя родителя для данного ребенка без рекурсии?

Question

У меня очень большой список памяти, я ищу наиболее эффективный алгоритм, чтобы взять список предметов и найти всех родителей, когда ребенок предоставлен.

List<Data> elements = new List<Data>
{
    new Data {Id = 1, ParentId = null },
    new Data {Id = 2, ParentId = 1},
    new Data {Id = 3, ParentId = 2},
    new Data {Id = 4, ParentId = 3}
};

var parents =
    elements
        .Where(x => x.ParentId != null)
        .ToDictionary(x => x.Id, x => x.ParentId.Value);

IEnumerable<int> GetParents(int i) =>
    parents.ContainsKey(i)
        ? new[] { parents[i] }.Concat(GetParents(parents[i]))
        : Enumerable.Empty<int>();
var result = GetParents(3); //1,2

Это работает нормально, но это не эффективный способ.Как переписать код, чтобы не было рекурсивных вызовов Execute?

Answer 1

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

** В этом примере я углубляюсь в иерархию только на 7000 уровней ниже, потому что рекурсивный подход повышает StackOverFlowException для более чем.

** Нерекурсивный подход, включающий первый узел, который имеет значение null как ParendId.

**нерекурсивное время выполнения намного лучше, чем рекурсивное.

    public class Data
    {
        public int Id { get; set; }
        public int? ParentId { get; set; }

    }

    static List<Data> elements = new List<Data>();

    static void Main(string[] args)
    {
        //To fill up the list with huge number if items
        elements.Add(new Data() { Id = 1, ParentId = null });
        Enumerable.Range(2, 1000000).ToList().ForEach(x => elements.Add(new Data { Id = x, ParentId = x - 1 }));

        //Making dictionary as you did it
        var parents =elements.ToDictionary(x => x.Id, x => x.ParentId);


        /*Non-Recursive Approach*/
        IEnumerable<int?> GetNonRecursiveParents(int i)
        {
            List<int?> parentsList = new List<int?>();
            if (parents.ContainsKey(i))
            {
                var parentNode = parents[i];
                do
                {
                    parentsList.Add(parentNode);
                    parentNode = parents[parentNode.Value];                        
                }
                while (parentNode != null);
            }
            return parentsList;
        };
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        var r = GetNonRecursiveParents(7000);
        stopwatch.Stop();
        var elapsed1 = stopwatch.Elapsed;// Execution time: 00:00:00.0023625



        //Making dictionary as you did it
        parents = elements.Where(x => x.ParentId != null).ToDictionary(x => x.Id, x => x.ParentId);


        /*Recursive Approach*/
        IEnumerable<int?> GetParents(int i) =>
            parents.ContainsKey(i)
                ? new[] { parents[i] }.Concat(GetParents(parents[i].Value))
                : Enumerable.Empty<int?>();
        stopwatch.Restart();
        var result = GetParents(7000); 
        stopwatch.Stop();
        var elapsed2= stopwatch.Elapsed;// Execution time: 00:00:00.0040636
    }

Answer 2

Нерекурсивное решение довольно простое:

var currentId = i;

while (parents.TryGetValue(currentId, out var parentId))
{
    yield return parentId;
    currentId = parentId;
}

Я что-то упустил?