Как улучшить производительность слияния непрерывного пространства кучи

Question

Я написал симулятор менеджера кучи. Я использовал два списка, чтобы сохранить адрес и размер выделенных и свободных блоков. Я обнаружил, что следующая функция резко ухудшает мою производительность кода, так как мне нужно выделить миллион объектов ... Цель этой функции - найти непрерывный свободный блок в куче и объединить их, но проблема в том, что в нем есть линейный поиск и в результате это занимает много времени (более 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; 
     } 
    } 
    } 
} 

Answer 1

Вы можете использовать следующее наблюдение: два блока могут быть объединены, только если один из них только что был освобожден. Вот почему нет необходимости проверять весь список: когда вы освобождаете блок и возвращаете его в список свободных блоков, вам нужно проверить только предыдущий и следующий блоки.