Как улучшить код, чтобы установить глубину дерева траверс в C# datatable?

Question

У меня есть datatable, который имеет структуру дерева траверса на нем, он имеет много столбцов, но те, которые имеют значение, следующие: | RepID | LeaderID | Depth |

Я хочу, чтобы установить глубину этого дерева как: RepID, который имеет не LeaderID (нуль) не должно быть Глубина 0 RepID, который имеет в качестве лидера те, которые имеют глубину 0 должна быть глубина 1 и так далее

До сих пор я сделал рекурсивный алгоритм, который выполняет работу, однако, поскольку я повторяю более 400 000 строк, это занимает много времени.

До сих пор мой код выглядит следующим образом:

public static DataTable SetTreeLevel(DataTable dtReps) 
{ 
    //Getting the 1st level (reps without a leader) 
    var first_level = from r in dtReps.AsEnumerable() 
         where (r.Field<int?>("LeaderID") == null || r.Field<int?>("LeaderID") == 0) 
         select r; 

    //Setting the level for the reps obtained 
    foreach (var row in first_level) 
    { 
     row["Depth"] = 1; 
    } 

    //Setting the next levels 
    return setTreeLevelRecursive(dtReps, 2); 
} 

private static DataTable setTreeLevelRecursive(DataTable dtReps, int depth) 
{ 
    //Getting reps of the last level (depth -1) 
    var last_level = from r in dtReps.AsEnumerable() 
        where r.Field<int?>("Depth") == depth - 1 
         select r.Field<int?>("RepID"); 

    //List to improve performance 
    List<int?> last_level_list = last_level.ToList<int?>(); 

    //Getting the next level reps (leader is on the last level list) 
    var actual_level = from r in dtReps.AsEnumerable() 
         where last_level_list.Contains(r.Field<int?>("LeaderID")) 
         select r; 

    //List to improve performance 
    List<DataRow> actual_level_list = actual_level.ToList<DataRow>(); 

    foreach (DataRow row in actual_level_list) 
    { 
     row["Depth"] = depth; 
    } 

    //Validating if there are reps without depth 
    if ((from r in dtReps.AsEnumerable() 
     where r.Field<int?>("Depth") == null 
     select r).Count() > 0) 
    { 
     //Asignando siguiente nivel 
     setTreeLevelRecursive(dtReps, depth + 1); 
    } 

    //Regresando resultado 
    return dtReps; 
} 

Edit: Использование оптимизации Servy, я закодировано следующее:

var lookup = dtReps.AsEnumerable().ToLookup(x => x.Field<int?>("LeaderID")); 

      //First level 
      var first_level = from r in dtReps.AsEnumerable() 
           where (r.Field<int?>("LeaderID") == null || r.Field<int?>("LeaderID") == 0) 
           select Tuple.Create(r.Field<int>("RepID"), 1); 

      var rows = Traverse(first_level, node => lookup[node.Item1] 
       .Select(row => Tuple.Create(row.Field<int>("RepID"), node.Item2 + 1))).ToList(); 

      foreach (var r in rows) 
      { 
       (from r_nivel in dtReps.AsEnumerable() 
       where r_nivel.Field<int>("RepID") == r.Item1 
       select r_nivel).FirstOrDefault()["Depth"] = r.Item2; 
      } 

Но Еогеасп занимает много времени Спасибо!

Answer 1

Во-первых, вы можете определить объект Rep:

public class Rep 
{ 
    public int RepID {get;set;} 
    public int LeaderID {get;set;} 
    public int Depth {get;set;} 
} 

Затем заполнить список из вашей DataTable с помощью:

List<Rep> Reps=dtReps.OfType<DataRow>().Select(c=>new Rep(){RepID=Convert.ToInt32(c["RepID"]),LeaderID=Convert.ToInt32(c["LeaderID"])).ToList(); 

Затем вы создаете таблицу поиска для представителей каждого лидера по:

Dictionary<int,List<Rep>> LeaderLookup=Reps.GroupBy(c=>c.LeaderID).ToDictionary(c=>c.Key,c=>c.ToList()); 

Теперь вы используете LeaderLookup для рекурсивного набора глубин. Это очень быстро, я использую аналогичные данные с около 3000 предметов, и он может быть заполнен в течение секунды.

Для этого необходимо определить эту функцию:

private void RecursivelySetDepthOfChildren(int RepID,int CurrentDepth,Dictionary<int,<List<Rep>> LeaderLookup) 
{ 
    int DepthOfChildren=CurrentDepth+1; 
    foreach(Rep child in LeaderLookup[RepID]) 
    { 
     child.Depth=DepthOfChildren; 
     RecursivelySetDepthOfChildren(child.RepID,child.Depth,LeaderLookup); 
    } 
} 

Затем вы вызываете функцию с:

RecursivelySetDepthOfChildren(0,0,LeaderLookup); 

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

Сколько времени это займет?