如何提高合併連續堆空間的性能

我寫了一個堆管理器模擬器。我使用了兩個列表來保存已分配塊和空閒塊的地址和大小。我發現下面的函數大幅度降低了我的代碼性能，因爲我需要分配數百萬個對象... 此函數的目的是在堆中查找連續的空閒塊併合並它們，但問題是它中存在線性搜索因此需要很長時間才能完成（超過1小時）我該如何改進？有任何想法嗎？如何提高合併連續堆空間的性能

public void updateFreeList(tuple freeElement) 
{ 
    int i=0; 
    if(freeList.size()> 1) 
    { 
    while(i<freeList.size()) 
    { 
     try{ 
     if((freeList.get(i).getAddress()+freeList.get(i).getSize()) == (freeList.get(i+1).getAddress())) 
     { 
      freeList.get(i).setSize(freeList.get(i).getSize() + freeList.get(i+1).getSize()); 
      freeList.remove(i+1); 
      continue; 
     } 
     i++; 
     } 
     catch (Exception e) 
     { 
     break; 
     } 
    } 
    } 
}

來源

2014-10-18 Alex

您可以使用以下觀察：只有在其中一個塊已被釋放的情況下，兩個塊纔可合併。這就是爲什麼不需要檢查整個列表：當您釋放一個塊並將其返回到空閒塊列表時，您只需檢查上一個和下一個塊。

來源

2014-10-18 14:47:04 kraskevich

但它在列表中，所以我需要遍歷freeList來查找上一個和下一個塊。例如，在freeList中，我有（50,50）（300,100）（700,100）（1000,200）並且想要釋放（100,200），所以我需要遍歷freeList以查找下一個和上一個。那麼還有線性搜索嗎？我對嗎？ – Alex 2014-10-18 15:26:34

@ user2942756如果您沒有維護任何額外的數據結構來加速搜索，它是線性的。但是，如果每個操作都有一個額外的對數因子是可行的，那麼您可以維護一個'TreeSet'塊，以便您可以在'O（log N）'時間內找到下一個和前一個。 – kraskevich 2014-10-18 15:38:10

如何提高合併連續堆空間的性能

回答

相關問題