存储部分共享字符串的集合内存

最有效的方法我有一个递归C＃应用程序，遍历一棵树，需要保持链中的所有节点的历史，每当最后一个节点等于X.存储部分共享字符串的集合内存

对于例如，我在下面

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

通知节点3是怎样一个兄弟到节点搜索词匹配。我的目标是确定遇到MATCH的根和每条路径之间的父子关系。这意味着将生成以下输出：

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

解决此问题的正确方法是什么？

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

我的目标是在Azure表或Blob存储上实现此操作......每IO查询100批次的行，最多查询20,000行在heiarchy每个级别。

我敢肯定，但不知道它会被称为这已经做过..

问题

我应该如何参考字符串在内存中，以便他们消费最少量的RAM？

示例答案：

使用与裁判参数结构......或者......

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); 
    } 
}

来源

2012-10-15 LamonteCristo

你在问什么？你需要一个递归的方法，沿树走，记住它在树中的位置并返回所有匹配。你在问C＃数据结构吗？或者数据库中的数据结构？最有效的方法呢？ ...？ – Achim

因此，如果Node3在Node2“下”，这样你就可以获得Root-> Node2-> Node3，为什么你不能获得Root-> Node1-> Node2-> Node33或Root-> Node1-> Node2-> Node3 ？由于Node3不是Node2的子节点，所以在这种情况下“under”的意思并不清楚，它是兄弟节点。 –

@MattBurland我不是想要计算兄弟姐妹，只是父母的孩子关系。我仔细检查了我的例子，我认为它是正确的。 – LamonteCristo

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

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 
    } 
}

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

来源

2012-10-15 17:44:42 climbage

我可能有多达512个级别，但实际上有256个级别。每个级别可以有20,000个兄弟姐妹。我不确定如何做数学来衡量所需的RAM。 – LamonteCristo

您是否需要维护到匹配节点的整个路径，还是只维护节点的父节点？ – climbage

我更喜欢整个路径。如果存在内存限制，那么我可以将“整个路径”的特征限制在X级别深处，但是我必须承认存在X + 1（或更多）的链接 – LamonteCristo

听起来像你正在寻找地图缩减算法。

其他人提到MapReduce作为潜在的选择;有些人已经在Azure中使用它。

有一些文章/算法在那里，如this link，这将帮助你制作自己的。

来源

2012-10-15 18:55:27 GlenH7

存储部分共享字符串的集合内存

回答

相关问题