10

木 T を定義しましょう:

    A
   / \
  B   C
 / \
D   E

新しいノードが E に追加され、T' が生成されたとします。

    A
   / \
  B   C
 / \
D   E
     \
      G

変更可能な言語では、これは簡単な作業です。E の子を更新するだけで完了です。ただし、不変の世界では、まず E へのパスを知り、次に E + 新しい子から E' を導出し、次に B' を導出し、最後に A' ( = T') を導出する必要があります。

これは面倒です。理想的には、E と G (および場合によっては T) の値を取り、E へのパスを提供せずに T' を生成する関数が存在します。

この問題に対処するには、次の 2 つの方法が考えられます。

  • 親参照 - このようにして、すべてのノードはルートへのパスを導出できます。2 つの問題: 相互に参照する 2 つのノード (つまり、親 <-> 子) を作成することは、純粋関数型言語の問題です (簡単な解決策はありますか?)。E -> E' が導出されるときはいつでも、E' の代わりに E の古い値を保存するため、E' のすべての子も新しく導出する必要があります。
  • ジッパー - すべてのノードは、親ジッパーから派生した作成時にジッパーを格納します。相互参照の問題は解消されますが、E -> E' が導出されると、E' の子のジッパーもすべて導出する必要があります。これは、古いツリー E を指しているためです。

合理的なパフォーマンスを念頭に置いて、私が望むことは可能ですか? ご意見をお寄せいただきありがとうございます。

4

1 に答える 1

1

Lazy Replace の実行に基づく別のオプション。パフォーマンスが重要で、多くの変更が加えられる場合は、ベンチマークすることをお勧めします。

私は F# で実装しましたが、印刷機能以外に「不純」なものを使用したとは思いません。

これはちょっとしたテキストの壁です。基本的な原則は、ノードを返す関数を置き換えることによって、ツリーを怠惰に保ち、ノードを置き換えることです。

秘訣は、ノードを識別する何らかの方法が必要なことです。それは、それ自体の参照/名前ではなく、値によるものではありません。識別は、ReplacementNodes に複製可能である必要があります。この場合、System.Object は参照的にそれぞれ異なるため、System.Object を使用しました。

type TreeNode<'a> = {
    getChildren: unit -> seq<TreeNode<'a>>;
    value: 'a;
    originalRefId: System.Object; //This is set when the onject is created,
                                  // so we can identify any nodes that are effectivly this one 
    }


let BasicTreeNode : 'a ->seq<TreeNode<'a>>-> TreeNode<'a>  = fun nodeValue -> fun children ->
    {value = nodeValue; originalRefId = System.Object(); getChildren = fun () -> children;}


let rec ReplacementNode : TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a>  = 
    fun nodeToReplace -> fun newNode -> fun baseNode ->
        if (System.Object.ReferenceEquals(baseNode.originalRefId, nodeToReplace.originalRefId)) then
            //If it has the same Oringal 
            newNode //replace the node
        else
            //Just another pass on node, tranform its children, keep orignial reference
            {value = baseNode.value; 
             originalRefId = baseNode.originalRefId;
             getChildren = fun () -> 
                baseNode.getChildren() |> Seq.map(ReplacementNode nodeToReplace newNode); }


type TreeType<'a> = {
    Print: unit -> unit; 
    ReplaceNode: TreeNode<'a> -> TreeNode<'a> -> TreeType<'a>;
    //Put all the other tree methods, like Traversals, searches etc in this type
    }

let rec Tree  = fun rootNode ->
    {
        Print = fun () -> 
            let rec printNode = fun node -> fun depth -> 
                printf "%s %A\n" (String.replicate depth " - ")  node.value
                for n in node.getChildren() do printNode n (depth + 1)
            printNode rootNode 0
            ;
        ReplaceNode = fun oldNode -> fun newNode ->
            Tree (ReplacementNode oldNode newNode rootNode)



    }

テストケース/例:

let e = BasicTreeNode "E" Seq.empty
let d = BasicTreeNode "D" Seq.empty
let c = BasicTreeNode "C" Seq.empty
let b = BasicTreeNode "B" [d;e]
let a = BasicTreeNode "A" [b;c]
let originalTree = Tree a
printf "The Original Tree:\n"
originalTree.Print()

let g = BasicTreeNode "G" Seq.empty
let newE = BasicTreeNode "E" [g]

let newTree = originalTree.ReplaceNode e newE
printf "\n\nThe Tree with a Local Change: \n"
newTree.Print()

printf "\n\nThe Original Tree is Unchanged: \n"
originalTree.Print()


printf "\n\nThe Tree with a Second Local Change: \n"
let h = BasicTreeNode "H" Seq.empty
let newC = BasicTreeNode "C" [h]
let newTree2 = newTree.ReplaceNode c newC
newTree2.Print()



printf "\n\nTrying to Change a node that has been replaced doesn't work \n"
let i = BasicTreeNode "i" Seq.empty
let newnewC = BasicTreeNode "C" [h; i]
let newTree3 = newTree.ReplaceNode c newC //newTree.ReplaceNode newc newnewC would work
newTree3.Print()

テストの最後に、置き換えられるオブジェクトに古いノード名 (/reference) を使用しても機能しないことがわかりました。別のノードの参照 ID を持つ新しいタイプを作成するオプションがあります。

//Like a basicTreeNode, but reuses an existing ID, so they can be replaced for oneanother
let EdittedTreeNode = fun orignalNode -> fun nodeValue -> fun children -> 
    {value = nodeValue; originalRefId = orignalNode.originalRefId; getChildren = fun () -> children;}

ReplacementNode定義を編集して、置き換えるノードの ID を保持することもできます。( を返すだけでなく、 、 、 、のnewNodeを持つさらに別の新しいノードを返すことによって)valuegetChildrennewNodeoriginalRefIdnodetoReplace

于 2013-09-07T02:52:14.550 に答える