下图可视化了 16 个不同大小的内存块所需的寿命:
我实际上要寻找的是给定大小为i和生存期[begin i , end i )的N个块,返回在我们的总时间间隔和N个偏移量中包含它们所需的最小总内存块,偏移量i , 到输入块的这个总内存块中。
一个简单的非最优算法如下:
int offsets[N];
offsets[0] = 0;
int total_size = size[0];
for (int i = 1; i < N; ++i)
{
offsets[i] = offsets[i - 1] + size[i - 1];
total_size += size[i];
}
我们当前的算法是按大小对块进行排序,然后从最大到最小处理它们,找到该块不与已“分配”的块重叠的第一个偏移量。这本质上是一个贪心算法,所以我有一种感觉,它可以做得更好。
该算法只需要在应用程序启动时运行一次,因此它不必非常快。分配的数量大约为 10-50,为了我们的目的,可以将时间离散化为大约 50 个固定大小的单位。