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

または構造体への参照を保存します

 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

マップ縮小アルゴリズムを探しているようですね。

他の人は、 MapReduceを潜在的なオプションとして言及しています。Azureでそれを使用することに取り組んだ人もいます。

あなたがあなた自身を作るのを助けるこのリンクのような、そこにたくさんの記事/アルゴリズムがあります。

于 2012-10-15T18:55:27.760 に答える
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 に答える