09 22 |
C與C++ List library的比較-武林高手,各有千秋作者: Joey 日期: 2008-09-22 13:17 |
實在不曉得為什麼下這樣的標題,可能最近武俠小說看太多了,不過在講這個主題前,請大家一定要支持”海角七號”這部電影,真得很好看,令人好笑又感動,我打算有機會再安排個墾丁之旅,好好把當時的電影場景再逛一遍
回歸正題,LIST這個資料結構不難懂,只要把買電影票要排隊的那套邏輯拿來好好想一想,就知道LIST是做什麼用的,LIST可以說是QUEUE和STACK的原型,雖然只支援sequential access,但如果善用排序和搜尋,它存取資料的速度其實非常快,之前寫LIST的資料結構,都是用C++的STL,後來最近發現一個純C寫的Library “simclist”,它這支library使用上也蠻簡單的,支援類iterator的方式存取list,所以我把C++ STL和simclist拿出來比較看看,從記憶體,效能,和排序時間看看它們的優點
比較不同程式效能前,我都習慣把real-time priority和execution time-slice調成一樣,雖然kernel會自動幫你設定程式執行優先權,但為了保險起見,我還是自己手動比較安心,而real-time priority我調成70,nice值我調成-10,範例如下
我賦予給STL和simclist的元素基本單位都是unsigned int,比較的方式是
(1)新增10000~1000000組的資料,觀察時間和記憶體的消耗量
(2)排序10000~1000000組的資料,觀察所需的時間
C++ LIST STL請參考這個網站,而simclist的用法很簡單,大致流程就是,初始化,註冊功能函式,就可以用了,範例如下
以下是性能的分析
(1)比較新增元素所花的時間,紅色為simclist,藍色為C++ STL,長條圖越短越好
(2)比較新增元素所花的記憶體,紅色為simclist,藍色為C++ STL,長條圖越短越好
(3) 比較排序元素所花的時間,紅色為simclist,藍色為C++ STL,長條圖越短越好
綜合上面三點,C++ STL在新增元素所使用的記憶體和時間略勝simclist,但排序則輸給simclist,所以在有大量資料需排序且記憶體使用無上限的話,simclist是不錯的選擇,但如果碰到其它情況,就用C++ STL吧!!
點這邊下載此篇文章所用到的原始碼
Regular expression-跟brainfuck差不多的東西 (2009-11-13 15:37)
Reading file in kernel-簡單但實用 (2009-10-13 15:18)
Linux file system for dummies-只花你45分鐘 (2009-08-19 15:40)
OPENSSL-TCP SSL初心者之路 (2009-07-16 15:16)
NAPI與pure interrupt driver的效能比較 (2009-04-29 19:06)
usermode helper-來自kernel的呼喚 (2009-04-21 16:19)
kernel module memory detector-抓出有害的kernel module (2009-03-31 13:50)
kernel space coding-如履薄冰 (2009-03-26 09:52)
readahead與posix_advise-預讀取是萬能靈丹? (2009-03-06 15:54)