可變長度的空閒列表

的free list的概念通常用於重新使用空間，所以如果我有一個完整的固定長度值的文件，我刪除一個，我把它放在一個空閒列表上。然後當我需要插入新的價值時，我從列表中拿出一個並放在那個位置上。可變長度的空閒列表

不過我有點困惑，如何實現是可變長度值的空閒列表。如果我刪除了這個值，並且我把這個位置和它的長度放在了空閒列表中，我該如何檢索新值的「最佳」候選者？

使用普通名單將O(n)時間複雜度。使用樹（長度作爲關鍵）將使該log(n)。有什麼更好的，會給O(1)？

2016-07-15 Resurrection

有很多不同的選擇，從基本的，但簡單的代碼，線性表，因爲你已經提到的，它由一系列平衡樹的散列桶來隔離不同大小的分配，這是一個「清單」要正確編寫代碼相當困難，並且其中還有許多其他選項。這一切都取決於你需要什麼，你願意花費多少工作來獲得它 - 編程中的一個常見主題...... – twalberg

@twalberg用例大致是這樣的：我有一個圖，其中每個節點（和邊緣）可以具有與它們中的每一個相關聯的任意數量的鍵值對。我需要將這些文件存儲在一個文件中，這樣我可以a）根據節點+密鑰對O（1）值進行訪問，b）有一種方法可以知道與節點相關的所有密鑰。所以對於a）哈希表將很好地工作，但它不允許b）。因此我需要以某種方式以不同的方式存儲它。 – Resurrection

是，哈希表！所以你有一個大的散列表，其中包含空閒塊的大小作爲鍵，值是數組，指向相應大小的塊。所以，每次釋放一個塊：

hash[block.size()].append(block.address())

而且每次分配空閒塊：

block = hash[requested_size].pop()

這種方法的問題是有太多的可能的塊大小。因此散列會填滿數百萬個密鑰，浪費大量內存。

因此，你可以有一個列表，並遍歷它找到一個合適的塊：

for block in blocks: 
    if block.size() >= requested_size: 
     return blocks.remove(block)

內存使用效率，但是緩慢的，因爲你可能有過百萬塊進行掃描。

所以你要做的就是結合這兩種方法。如果將分配量設置爲64，那麼包含256個大小類的散列可以用於最大64 * 256 = 16 kb的所有分配。大於您存儲在樹中的塊，該樹會給您O（日誌N）插入和刪除。

來源

2016-10-23 16:16:04

可變長度的空閒列表

回答

相關問題