Блог

Главная - Вопросы по программированию - Как сгладить запрос, ссылающийся на себя?

Как сгладить запрос, ссылающийся на себя?

#c# #linq

#c# #linq

Вопрос:

Похоже, что на этот вопрос уже был бы дан ответ, но я не могу его найти.
У меня есть следующая таблица:

 Id     Parent     Text
-----------------------
1      NULL       A
2       1         B
3       2         C
4       3         D
5      NULL       E
6       5         F
7       6         G

Теперь я хочу получить такой результат: ( List<string> )

 A
A > B
A > B > C
A > B > C > D
E
E > F
E > F > G

Но проблема в том, что этот проект, над которым я работаю, сначала использует базу данных, я имею в виду, что нет свойства навигации, Parent типа string нет IEnumerable<T> .

Что я сделал до сих пор:

 var list = new List<string>();
string e2 = string.Empty;
foreach (var item in query)
{
    string e1 = string.Empty;
    if (item.Parent == null)
    {
        list.Add(p.Text);
        e2 = item.Text;
    }
    else
    {
        foreach (var subItem in query.Where(t => t.Id == p.Parent))
        {
            if (subItem.Id != 1)
            {
                e1 = e2   " > "   subItem.Text;
            }
            else
            {
                e1 = subItem.Text;
            }
        }
        list.Add(e1   " > "   p.Text);
    }
}

Комментарии:

1. Покажите определение query переменной

2. это всего лишь простой запрос linq: var query = from item in myTable select item;

3. Существует большая разница , является ли запрос IQueryable<T> or IEnumerable<T> . В первом случае вы будете выполнять N запросов к базе данных. Во втором случае принятый вами наивный алгоритм будет выполнять N * N поисков. Другими словами, и то, и другое будет крайне неэффективно. В любом случае, проблема полностью ваша 🙂

Ответ №1:

Используйте рекурсивный алгоритм

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;

namespace ConsoleApplication1
{
    class Program
    {
        static List<string> list = new List<string>();
        static DataTable dt = new DataTable();
        static void Main(string[] args)
        {
            dt.Columns.Add("Id", typeof(int));
            dt.Columns.Add("Parent", typeof(int));
            dt.Columns["Parent"].AllowDBNull = true;
            dt.Columns.Add("Text", typeof(string));

            dt.Rows.Add(new object[] {1, null, "A"});
            dt.Rows.Add(new object[] {2, 1, "B"});
            dt.Rows.Add(new object[] {3, 2, "C"});
            dt.Rows.Add(new object[] {4, 3, "D"});
            dt.Rows.Add(new object[] {5, null, "E"});
            dt.Rows.Add(new object[] {6, 5, "F"});
            dt.Rows.Add(new object[] {7, 6, "G"});

            GetRecursiveChildren(null, new List<string>());

            foreach (string row in list)
            {
                Console.WriteLine(row);
            }
            Console.ReadLine();
        }
        static void GetRecursiveChildren(int? parent, List<string> parents)
        {
            foreach (DataRow row in dt.AsEnumerable().Where(x => x.Field<int?>("Parent") == parent))
            {
                string text = row.Field<string>("Text");
                List<string> newParents = new List<string>();
                newParents.AddRange(parents);
                newParents.Add(text);
                list.Add(string.Join(" > ",newParents));
                int child = row.Field<int>("Id");
                GetRecursiveChildren(child, newParents);
            }
        }
    }

}

Ответ №2:

Это работает для меня:

 var source = new []
{
    new { Id = 1, Parent = (int?)null, Text = "A" },
    new { Id = 2, Parent = (int?)1, Text = "B" },
    new { Id = 3, Parent = (int?)2, Text = "C" },
    new { Id = 4, Parent = (int?)3, Text = "D" },
    new { Id = 5, Parent = (int?)null, Text = "E" },
    new { Id = 6, Parent = (int?)5, Text = "F" },
    new { Id = 7, Parent = (int?)6, Text = "G" }
};

var lookup = source.ToLookup(x => x.Parent);

Func<int?, IEnumerable<string>> recurse = null;
recurse = p =>
    lookup[p].SelectMany(x => new [] { x.Text }
        .Concat(recurse(x.Id).Select(y => $"{x.Text} > {y}")));

foreach (string x in recurse(null))
{
    Console.WriteLine(x);
}

Я получаю:

A
A> B
A > B > C
A> B> C> D
E
E > F
E > F> G
Метки: ,