ツリー構造を作る時のメモリを減らしたい
で作成したツリー構造(完全二分木)だと、木の深さ/高さNに対して2^Nメモリ食うんでそれなんとかしたいぞと、
上記の例の場合、ノートの結合があるので、メモリ消費量は本来Nオーダーに抑えられるはずだぞと。
なので、あまり見たことないけど、ツリー構造の要素を無理矢理参照にしてみた。
//Refで要素を持たせたツリー type Tree = | Empty | Node of (float ref)*(Tree ref)*(Tree ref) member this.Value = match this with | Node(x, _, _) -> x | _ -> ref 0.0 //ツリー表示 let rec printTree tree = match tree with | Node(x, lhs, rhs) -> printfn "Value : %f" !x printTree !lhs printTree !rhs | Empty -> () [<EntryPoint>] let main argv = //適当なツリー let node1 = Node (ref 10.0, ref Empty, ref Empty) let node2 = Node (ref 20.0, ref Empty, ref Empty) let node = Node (ref 30.0, ref node1, ref node2) printfn "===値変更前===" printTree node //値の変更 printfn "===値変更後===" node1.Value := 100.0 printTree node 0 // return an integer exit code
上のコードを実行した結果、node1に対する値の変更がnodeにも反映されているから、nodeはちゃんとnode1への参照を持っていそうだ。
===値変更前=== Value : 30.000000 Value : 10.000000 Value : 20.000000 ===値変更後=== Value : 30.000000 Value : 100.000000 Value : 20.000000
こう書くもんなのかな・・・?