星期六, 4月 18, 2009

漫談 heap tree

身為一個懶人如我,heap tree 對我而言是一個非常好用的 data structure,其實這篇講的不是很難,只是要講我很懶 XD

我還蠻記得我第一次學習 C++ STL 的時候,我第一次體會到,何謂需求? 如果可以分析資料的基本特性,就可以找到比較弱的方法,而不用每次都用很強的方法。舉個例子說,從一個 ordered list 中取出 max element ,早期的我可能笨笨的排序完就直接上了 (std::sort() 很方便啊 XD),但是如果每次都只是從序列中取出最大或最小元素,可能候用 std::make_heap() 搭配 std::pop_heap() 即可,而且速度比前者快很多,其實大部分我們只是想取某個特性的元素,也不用每次都拿排序來做。如果每次都僅插入元素來形成 ordered list 的話,當然也可以使用 std::list 與 std::list::sort() 來實作,這樣子我們也可以很方便的來達成我們的要求,只是每次插入一個新元素的時間為 O(n),但是只要能夠循序存取就支援這個特性。而 heap tree 雖然插入一個新元素為O(log n) ,但是考慮到記憶體使用策略,端看怎麼用了。

我記得我在很久以前與人合作寫程式的時候,有人一次讀了數mb進來存在 std::string 中,然後使用 std::string::insert ,這人就問我為什麼跑起來無敵慢,我說原因其實蠻簡單的,因為這個 member function 的時間是 O(n),後來改成分段讀取後處理,速度快了好多啊XD。

題外話: 我沒有用過 Boost::asio 和 Boost::thread ,有人用過的可以告訴我穩定否 XD?


---
寫程式時,盡量使用最弱假設,會有驚喜的。


2009/04/18 5:32 pm 大鳥 在 comments 中有提到更好的方法,不過我還沒試,所以有看的人要記得看回覆喔XD

張貼留言