※ 引述《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/cn.aspx?n=bbs/C_and_CPP/M.1481128623.A.C44.html