如何加快递归搜索功能？

Question

我在编写搜索功能的速度方面遇到了麻烦.功能步骤如下所述:

1. 该函数以两个表名参数开始,即起始点和目标
2. 然后,该函数遍历表 - 列组合列表(50,000长)并检索与起始点表关联的所有组合.
3. 然后该函数循环遍历每个检索到的组合,并且对于每个组合,它再次遍历表 - 列组合列表,但这次查找与给定列匹配的表.
4. 最后,函数遍历从最后一步检索到的每个组合,并且对于每个组合,它检查表是否与目标表相同; 如果是这样它会保存它,如果不是,它会调用自己传递表名形式的组合.

功能目标是能够跟踪链接直接或具有多个分离度的表之间的链接.递归级别是固定的整数值.

我的问题是,每当我尝试在两个级别的搜索深度上运行此功能时(在此阶段不敢尝试更深),作业内存不足,或者我失去了耐心.我等了17分钟才把工作用完了一次.

每个表的平均列数为28,标准差为34.

下面的图表显示了可以在表之间建立的各种链接的示例:

这是我的代码:

private void FindLinkingTables(List<TableColumns> sourceList, TableSearchNode parentNode, string targetTable, int maxSearchDepth)
{
    if (parentNode.Level < maxSearchDepth)
    {
        IEnumerable<string> tableColumns = sourceList.Where(x => x.Table.Equals(parentNode.Table)).Select(x => x.Column);

        foreach (string sourceColumn in tableColumns)
        {
            string shortName = sourceColumn.Substring(1);

            IEnumerable<TableSearchNode> tables = sourceList.Where(
                x => x.Column.Substring(1).Equals(shortName) && !x.Table.Equals(parentNode.Table) && !parentNode.Ancenstory.Contains(x.Table)).Select(
                    x => new TableSearchNode { Table = x.Table, Column = x.Column, Level = parentNode.Level + 1 });
            foreach (TableSearchNode table in tables)
            {
                parentNode.AddChildNode(sourceColumn, table);
                if (!table.Table.Equals(targetTable))
                {
                    FindLinkingTables(sourceList, table, targetTable, maxSearchDepth);
                }
                else
                {
                    table.NotifySeachResult(true);
                }
            }
        }
    }
}

编辑:分离出TableSearchNode逻辑并添加属性和方法以实现完整性

//TableSearchNode
public Dictionary<string, List<TableSearchNode>> Children { get; private set; }

//TableSearchNode
public List<string> Ancenstory
{
    get
    {
        Stack<string> ancestory = new Stack<string>();
        TableSearchNode ancestor = ParentNode;
        while (ancestor != null)
        {
            ancestory.Push(ancestor.tbl);
            ancestor = ancestor.ParentNode;
        }
        return ancestory.ToList();
    }
}

//TableSearchNode
public void AddChildNode(string referenceColumn, TableSearchNode childNode)
    {
        childNode.ParentNode = this;
        List<TableSearchNode> relatedTables = null;
        Children.TryGetValue(referenceColumn, out relatedTables);
        if (relatedTables == null)
        {
            relatedTables = new List<TableSearchNode>();
            Children.Add(referenceColumn, relatedTables);
        }
        relatedTables.Add(childNode);
    }

在此先感谢您的帮助!

Answer 1

你真的浪费了很多内存。我立即想到的是：

1. 首先将传入替换List<TableColumns> sourceList为ILookup<string, TableColumns>. 您应该在致电之前执行此操作一次FindLinkingTables：

   ILookup<string, TableColumns> sourceLookup = sourceList.ToLookup(s => s.Table);
   FindLinkingTables(sourceLookup, parentNode, targetTable, maxSearchDepth);
   

2. .ToList()如果确实不需要，请不要打电话。例如，如果您只想枚举一次结果列表的所有子项，则不需要它。所以你的主要功能将如下所示：

   private void FindLinkingTables(ILookup<string, TableColumns> sourceLookup, TableSearchNode parentNode, string targetTable, int maxSearchDepth)
   {
       if (parentNode.Level < maxSearchDepth)
       {
           var tableColumns = sourceLookup[parentNode.Table].Select(x => x.Column);
   
           foreach (string sourceColumn in tableColumns)
           {
               string shortName = sourceColumn.Substring(1);
   
               var tables = sourceLookup
                   .Where(
                       group => !group.Key.Equals(parentNode.Table)
                                && !parentNode.Ancenstory.Contains(group.Key))
                   .SelectMany(group => group)
                   .Where(tableColumn => tableColumn.Column.Substring(1).Equals(shortName))
                   .Select(
                       x => new TableSearchNode
                       {
                           Table = x.Table,
                           Column = x.Column,
                           Level = parentNode.Level + 1
                       });
   
               foreach (TableSearchNode table in tables)
               {
                   parentNode.AddChildNode(sourceColumn, table);
                   if (!table.Table.Equals(targetTable))
                   {
                       FindLinkingTables(sourceLookup, table, targetTable, maxSearchDepth);
                   }
                   else
                   {
                       table.NotifySeachResult(true);
                   }
               }
           }
       }
   }
   

   [编辑]

3. 另外，为了加速剩余的复杂 LINQ 查询，您可以准备另一个ILookup：

   ILookup<string, TableColumns> sourceColumnLookup = sourceLlist
           .ToLookup(t => t.Column.Substring(1));
   
   //...
   
   private void FindLinkingTables(
       ILookup<string, TableColumns> sourceLookup, 
       ILookup<string, TableColumns> sourceColumnLookup,
       TableSearchNode parentNode, string targetTable, int maxSearchDepth)
   {
       if (parentNode.Level >= maxSearchDepth) return;
   
       var tableColumns = sourceLookup[parentNode.Table].Select(x => x.Column);
   
       foreach (string sourceColumn in tableColumns)
       {
           string shortName = sourceColumn.Substring(1);
   
           var tables = sourceColumnLookup[shortName]
               .Where(tableColumn => !tableColumn.Table.Equals(parentNode.Table)
                                     && !parentNode.AncenstoryReversed.Contains(tableColumn.Table))
               .Select(
                   x => new TableSearchNode
                       {
                           Table = x.Table,
                           Column = x.Column,
                           Level = parentNode.Level + 1
                       });
   
   
           foreach (TableSearchNode table in tables)
           {
               parentNode.AddChildNode(sourceColumn, table);
               if (!table.Table.Equals(targetTable))
               {
                   FindLinkingTables(sourceLookup, sourceColumnLookup, table, targetTable, maxSearchDepth);
               }
               else
               {
                   table.NotifySeachResult(true);
               }
           }
       }
   }
   

4. 我已经检查过你的Ancestory财产了。如果IEnumerable<string>足以满足您的需求，请检查此实现：

   public IEnumerable<string> AncenstoryEnum
   {
       get { return AncenstoryReversed.Reverse(); }
   }
   
   public IEnumerable<string> AncenstoryReversed
   {
       get
       {
           TableSearchNode ancestor = ParentNode;
           while (ancestor != null)
           {
               yield return ancestor.tbl;
               ancestor = ancestor.ParentNode;
           }
       }
   }