[Computers] 這不是 tree，這不是 tree..

最近跑的暑期學習計畫，進度已經到了容易混亂的境界..

內容大致是將一些乍看之下是 tree 的東西 merge 起來，
像是把

Ａ─→Ｂ┬→Ｃ─→Ｘ
　　　　└→Ｅ

Ｋ┬→Ｄ─→Ｃ─→Ｘ
　└→Ｇ─→Ｙ

兩個合併成

　　　　┌→Ｅ
Ａ─→Ｂ┴→Ｃ─→Ｘ
Ｋ┬→Ｄ──┘
　└→Ｇ─→Ｙ

這樣的東西 (怪了，怎麼越看越像迷宮 @@)

nodes 的處理的方式是 bottom-up，而不是 top-down，
如此將很多 tree 組合起來後，計算 node 的 overlap 比例，
像上例的結果是 2/11 = 18.2%；
再來，把共同的 parent path 列出來，上例為 Ｃ─→Ｘ

所以就能得到「Ａ、Ｋ的共同祖先是Ｃ與Ｘ」這個結論，
也就是說，「滴血認親」 囧?

雖然看起來不算太複雜，說起來也很輕鬆，
但我著實不知道最後會是 tree 還是 graph..
(個人覺得應該會變成 graph 啦)

現在雖然已經找出用遞迴跑，十分簡單的 merge 方式，
程式也寫了一部份，但仍無法運作 (只有一部分啊.. XD)

已經完成的部份跑起來是很不慢，但記憶體吃滿兇的，
用動態分配的會讓效能降低，但固定記憶體又會跑到爆..

嘖嘖，電腦這種東西一點都不好用啊 (吼喔喔)

總之呢.. 今天我就寫到這裡，不然作息又要不正常了 T__T


[posted by cornguo @ CornGuo's BLOG]