1

我有一个递归 C# 应用程序，它遍历一棵树，并且只要最后一个节点等于 X，就需要维护链中所有节点的历史记录。

例如，我在下面搜索单词 MATCH

Root
 |
 |-Node1
 |   |-Sub1
 |   |-MATCH
 |
 |-Node2
 |   |-Node22
 |   |-Node33
 |   |   |-MATCH
 |   |-Node3
 |
 |-Node3
 |   |-Node88
     |-MATCH

注意 Node3 是 Node2 的兄弟。我的目标是确定根与遇到 MATCH 的每条路径之间的父子关系。这意味着生成以下输出：

   Root -> Node1 -> MATCH
   Root -> Node2 -> Node33 -> MATCH
   Root -> Node2 -> Node3  -> MATCH
   Root -> Node3 -> MATCH

进行编码的正确方法是什么？

我立即看到，任何跟踪深度或长路径的尝试都会导致大部分内存被用于跟踪没有价值的路径。唯一有价值的路径是上面列出的找到匹配项的路径

我的目标是在 Azure 表或 Blob 存储上实现这一点……每个 IO 查询每批 100 行，在层次结构中每个级别最多查询 20,000 行。

我敢肯定这已经完成了，但不知道它会叫什么..

问题

我应该如何引用内存中的字符串，以便它们消耗最少的 RAM？

示例答案：

使用带有 ref 参数的结构...或...

Struct MyMemoryData
{
    public string PreviousNode {get;set;}
    public string NodeName {get;set;}
}

void MyRecursion(MyMemoryData searchStack, List<string> nodesToQuery)
{
    foreach(var str in nodesToQuery)
    {
        var newToDoList = GetChildNodes(str);

        searchStack.PreviousNode = searchStack.CurentNode;
        searchStack.CurrentNode = str;
        MyRecursion(searchStack, newToDoList);
    }
}

或将 ref 保存到结构

 Struct MyMemoryData
    {
        public MyMemoryData PreviousNode {get;set;}  // this line was changed: Type is MyMemoryData
        public string NodeName {get;set;}
    }

    void MyRecursion(MyMemoryData searchStack, List<string> nodesToQuery)
    {
        foreach(var str in nodesToQuery)
        {
            var newToDoList = GetChildNodes(str);

            searchStack.PreviousNode = searchStack;  // this line was changed: Saving the object instead of the value
            searchStack.CurrentNode = str;
            MyRecursion(searchStack, newToDoList);
        }
    }

或者只是将其全部保存在这样的列表中：

void MyRecursion(List<string> searchStack, List<string> nodesToQuery)
{
    foreach(var str in nodesToQuery)
    {
        var newToDoList = GetChildNodes(str);

        searchStack.Add(str);
        MyRecursion(searchStack, newToDoList);
    }
}
4

2 回答 2

0

你打算有多少级别？栈的大小应该受树的深度影响，而不是每一层的项目数。

void MyRecursion(Stack<string> searchStack, List<string> nodesToQuery)
{
    foreach(var str in nodesToQuery)
    {
        var newToDoList = GetChildNodes(str);

        searchStack.Push(str);
        MyRecursion(searchStack, newToDoList);
        searchStack.Pop(); // make sure to get pop off the current once you are no longer on this level
    }
}

编辑：老实说，我认为您可能需要考虑一种迭代方法。您的大部分内存将newToDoList存储在每个递归级别。如果您可以按顺序遍历树（想想XmlReader哪个是向前的）并以这种方式维护堆栈，那么您可能会更好。

于 2012-10-15T17:44:42.320 回答
0

听起来您正在寻找一种地图缩减算法。

其他人提到MapReduce是一种潜在的选择。有些人已经在 Azure 中使用它。

那里有许多文章/算法，例如此链接，可以帮助您制作自己的文章/算法。

于 2012-10-15T18:55:27.760 回答