以下图片展示了多种大小的16个内存块所需寿命的可视化图像:
我需要的是,给定数量为N、大小为sizei和生命周期为[begini, endi)的内存块,返回在总时间间隔内包含它们所需的最小总内存块大小以及这些输入块的N个偏移量offseti。
一个简单但不够优秀的算法如下:
我们目前的算法是按块大小排序,然后从最大的块开始处理,找到第一个偏移量,该块不与已“分配”块重叠。这本质上是一种贪心算法,因此我感觉可能可以更好地实现。
该算法只需要在应用程序启动时运行一次,因此它不必非常快。分配数量的顺序为10-50,并且对于我们的目的,时间可以离散化为大约50个固定大小的单位。
![enter image description here](https://istack.dev59.com/KgysZ.webp)
一个简单但不够优秀的算法如下:
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个固定大小的单位。