Re: [問題] 同時間需要大量delete的狀況
※ 引述《xtxml (赤木巧☠)》之銘言：
: 目前兩個方式：
: 1.之前的做法會是，寫一個manager來把這些資料收集起來，延遲刪除。
其實既然都要刪除，Manager 跟有無延遲刪除關聯並不大；
: 2.而我想自製一個memory allocator類別，給裝node的容器使用，他的行為是：
: (1)批量的向系統要記憶體，一次可能要100或1000個node的大小，
: 然後慢慢分配給容器使用，用完再要一個批量。
: (2)容器要求deallocate的時候不做事，只確保做完解構。
: (因為記憶體不重複使用，最後會一次刪，所以不一一處理deallocate)
: (3)等全部的node要一起刪除的話，就把批次要來的記憶體釋放掉，
: 可以大量減少delete的次數。
這種做法，STL本身其實就有；但STL的大小判別標準我並不是很清楚，建議是查
書比較好。比方說侯捷有針對 STL 的源碼剖析、還有像是EffectC++跟MEC++都有
相關內容，只是到底在哪本我就忘了。
下文述說。
: 想請教一下：
: 一.這樣的問題有沒有更合適的處理方式？方法1.或方法2.哪一個好一點。
其實都不好，new 在 memory allocation 屬於 HEAP-BASED ALLOCATION ，效能會
比較不好。再者，你所謂的同時刪除、同時新增，也不一定是指全體、如此一來就
會有 fragment，除非你的資料大小全部都統一。
: 二.關於方法2.目前想到就是要謹慎使用，並且包裝好確保會安全的刪除，
: 不知道有沒有什麼我沒有考慮到的缺點，或者不推薦這樣做的理由。
: 還請各位指教，感謝。
這不用太過擔心，除非運用雙重指標或複雜的資料結構、解構式寫好，基本上不會
有太大的問題。
至於新增、刪除的時間成本，你可以參照資料結構(in C++)聖經本第二版第 197 頁，
他採用了一種 AVALIABLE SPACE LISTS 的資料結構，讓刪除總體資料的時間複雜度
降低至常數時間。
無論你現在採用的資料結構是不是 LINKED LIST，這都帶有啟發性；
因為對於資料的存取，其實建立在記憶體的位置上；也就說要對該記憶體有識別性，
你才能知道你正在讀取有意義的資料。
所以 SORT 可以只針對 POINTER 進行調換，而非對資料本身進行搬移；
這點在刪除上也是相同的，不用對原本的資料進行刪除、而是對指標進行改寫，像是
STACK-BASED ALLOCATION，你甚至不必「真的」去刪除他，而是將TOP直接置底。
當然，如果你的資料結構不適用這個方法，那就要另尋方法了。
還有很多的記憶體配置技術，我認識的也只有這些了；
當中如果有錯，請板友們指正，感謝<(_ _)>
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.36.214
※ 編輯: bachelorwhc 來自: 220.134.36.214 (07/04 23:48)
推
07/05 00:09, , 1F
07/05 00:09, 1F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 4 篇)：