※ 引述《jacky1989 ()》之銘言： : 如題 : 這篇純閒聊，無學術交流，不喜者，現在就可以左轉了 : 最近在工作上遇到一些比較麻煩的問題 : 我要去檔案裡抓一些特定的資料，但是我不知道這些資料到底有多少 : 因此我沒辦法預先設定陣列大小或變數多寡 : 這時候就突然想到，以前老師教的，資料串結(linked list) : 就大家常看到的struct XXX{}; : 以前老師在教的時候，都不覺得這個有用 : 只覺得這到底要幹嘛，啊我用陣列就好啦!!! : 結果現在超常用到...... : 只能說，資料串結很有用，尤其面對未知的資料量時，整個大神的概念 : 就呼籲大家不要輕易放棄任何一種技術囉~~ : 因為你不知道哪一年的哪一天你會用到它 >> 因為就像你說的，有需要從中間插入的狀況，我讀的資料有可能不是連續性的 >> 還有一個狀況，我不知道到底需要讀多少資料 >> 這樣是不是也可以用動態陣列呢? 嗯，我們純討論就好。 (1) 一般如果是讀檔如文字檔的話，應該會有特定的 format， 像是 csv 或是 tab 分隔檔，先用 fread / memchr 做預讀一次， 再配置完整的 array， 速度應該是會比 link 快很多， 因 link 每次的 malloc 都要花一些時間， 真的資料大時到後面會有資料碎片化問題。 (2) 一般用純 c , 會用 realloc 去重新配置記憶體大小， 若要用即時動態的話，我想也是建議仿 std::vector 的基本策略， 初始化容量 (CAP) 給 1，當讀入個數(CNT) >= CAP 時， 將 CAP *=2 ， 等到某個狀態全讀完時，再調用一次 realloc ， 做 fit-size 動作。 (3) 另希望你的 link 排序已經寫好了，因 c standard library 並沒有支援 link 排序，但有支援 array 排序。一般如上所說， 若有可能在中間插入時，整個搬動實體資料 ( struct data ) 會費時， 所以大多的做法是對 { array to pointer } 做排序，也就是 最一開始的 array 是這麼做的。 typedef struct tagdata { // what ever }data ; int iCap = 10 , iCount = 0; data ** pDataPtrAry = (data**)malloc( sizeof(data*) * iCap); while( DataInCondition() ) { if(iCount >=iCap) { iCap*=2; // 下面一行 為簡寫，完整的 defect 去查 realloc 傳回值。 pDataPtrAry = (data**)realloc(pDataPtrAry , sizeof(data*) * iCap); } pDataPtrAry[iCount] = (data*)malloc(sizeof(data)); ++iCount; } // 最後做 fit-size , 完整 defect 查 realloc 傳回值 pDataPtrAry = (data**)realloc(pDataPtrAry, sizeof(data*) * iCount); 是的，其實有些步驟和 link 很像，但其實後面的 loop malloc 是可以簡化的， 便是一次都 malloc 完成，用指標指過去即可，前半段如下。 int iCap = 10 , iCount = 0; data ** pDataPtrAry = (data**)malloc( sizeof(data*) * iCap); data * pRealDataTrunk = (data*) malloc( sizeof(data) * iCap) ; data * pPtr = pRealDataTrunk; for(int i = 0; i < iCap ; ++i) { pDataPtrAry[i] = pPtr; ++pPtr; } 這樣不論是在配置或釋放，都會明顯比 link 還快。那這樣到底還有什麼好處？ (A) 我們最後排序在做移動時，是對 pointer 做移動，不是對實體 struct 做移動， 所以移動成本低。 (B) 在配置記憶體、釋放記憶體時，"寫得好" 的情況下，比 link 速度還快。 當然，若對 link 也做過優化，不是每讀進來一次時才 malloc 一次的話， 那速度還有機會拉上來，不過這部份的優化我沒研究便是。 (C) 可以直接套用 qsort 這支 function，不用再重刻，也不用再驗效能。 當然，若你有把握，用 link 做 sorting 時，能寫得比 stdlib.h 裡面的 qsort 還快的話，那就另當別論了。 code 僅為示意討論，沒跑過。若可以跑的話代表是塞到的。 以上，若我敘述有誤，或持有不同看法，也歡迎提出、指正、討論。 -- 就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮， 永遠當老闆的傀儡 你是不是想這麼做？ 是的話你就拿回去~ 拿啊！！ 九世宅男 : 下輩子不要再讓我幹工程師了 ~ < Kuso 星爺語錄 > --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.73.92 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1481128623.A.C44.html