C與C++ List library的比較-武林高手,各有千秋

實在不曉得為什麼下這樣的標題,可能最近武俠小說看太多了,不過在講這個主題前,請大家一定要支持”海角七號”這部電影,真得很好看,令人好笑又感動,我打算有機會再安排個墾丁之旅,好好把當時的電影場景再逛一遍

回歸正題,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吧!!

點這邊下載此篇文章所用到的原始碼