设计内存分配器

标签: 设计 数组 哈希表 模拟

难度: Medium

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

  1. 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
  2. 释放 给定 id mID 对应的所有内存单元。

注意：

  • 多个块可以被分配到同一个 mID 。
  • 你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

  • Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
  • int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于  最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
  • int free(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

示例：

输入
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.free(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。

提示：

  • 1 <= n, size, mID <= 1000
  • 最多调用 allocate 和 free 方法 1000 次

Submission

运行时间: 109 ms

内存: 16.8 MB

class Allocator:

    def __init__(self, n: int):
        self.space = [[-1, n, 0]]

    def allocate(self, size: int, mID: int) -> int:
        for i, (ID, cnt, idx) in enumerate(self.space):
            if ID == -1 and cnt >= size:
                self.space[i] = [mID, size, idx]
                if cnt > size:
                    self.space.insert(i + 1, [-1, cnt - size, idx + size])
                return idx
        return -1


    def free(self, mID: int) -> int:
        ret = 0
        for i, (ID, cnt, idx) in enumerate(self.space):
            if ID == mID:
                ret += cnt
                self.space[i] = [-1, cnt, idx]
        i = 1
        while i < len(self.space):
            if self.space[i][0] == -1 and self.space[i - 1][0] == -1:
                self.space[i - 1][1] += self.space[i][1]
                self.space.pop(i)
            else:
                i += 1
        return ret



# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.free(mID)

Explain

该题解采用了一个列表 space 来维护内存分配的状态。每个元素是一个三元组 [ID, cnt, idx]，表示从下标 idx 开始，有 cnt 个连续的内存单元被分配给了 ID。如果 ID 为 -1，则表示这些内存单元是空闲的。在分配内存时，遍历 space，找到第一个空闲且大小足够的块，然后更新这个块的状态，并在需要时插入一个新的空闲块。在释放内存时，将所有属于给定 mID 的块标记为空闲，并合并连续的空闲块。

时间复杂度: O(n)

空间复杂度: O(n)

class Allocator:

    def __init__(self, n: int):
        self.space = [[-1, n, 0]]  # 初始化空闲内存块列表

    def allocate(self, size: int, mID: int) -> int:
        for i, (ID, cnt, idx) in enumerate(self.space):
            if ID == -1 and cnt >= size:  # 找到足够大的空闲块
                self.space[i] = [mID, size, idx]  # 分配内存块
                if cnt > size:
                    self.space.insert(i + 1, [-1, cnt - size, idx + size])  # 插入剩余的空闲块
                return idx
        return -1  # 没有找到合适的空闲块

    def free(self, mID: int) -> int:
        ret = 0
        for i, (ID, cnt, idx) in enumerate(self.space):
            if ID == mID:
                ret += cnt
                self.space[i] = [-1, cnt, idx]  # 标记为空闲块
        i = 1
        while i < len(self.space):
            if self.space[i][0] == -1 and self.space[i - 1][0] == -1:
                self.space[i - 1][1] += self.space[i][1]  # 合并连续的空闲块
                self.space.pop(i)
            else:
                i += 1
        return ret  # 返回释放的内存单元数目

Explore

使用三元组列表`space`来维护内存状态的主要原因是它的简单性和直观性。列表允许我们以线性方式遍历和查找足够大的空闲块，这对于维护连续的内存块非常有效。此外，使用列表可以非常方便地插入和删除元素，特别是在内存块分配和释放时。虽然二叉树或哈希表在某些操作上可能提供更快的时间复杂度，但它们在处理连续内存块的合并和拆分操作时可能不如列表直观和高效，特别是需要频繁地更新数据结构以反映内存的连续空间变化。

在`allocate`方法中，如果分配内存后剩余的内存块大小正好为0，那么就不需要插入一个新的空闲块。这是因为没有剩余的空间可以作为一个独立的空闲块来维护。在这种情况下，原有的块被完全分配给请求者，列表中只更新该块的状态而不添加新的元素，这有助于避免不必要的列表操作和空间浪费。

在`free`方法中，释放内存后进行的连续空闲块的合并操作确实考虑了所有可能的连续空闲区域的合并，包括多个连续区域的合并。方法通过遍历列表并检查相邻的空闲块来实现合并。如果发现连续的空闲块，就将它们合并成一个更大的空闲块。这个过程会继续进行，直到没有更多可以合并的连续空闲块为止。这种方法确保了内存的最大化利用与整合，减少了内存碎片。

多次进行内存分配和释放操作可能会导致`space`列表的长度增加，特别是在频繁地分配较小块和随后释放这些块的情况下，因为这可能在列表中引入更多的小的空闲块。这种变化会影响性能，主要是因为列表长度的增长可能导致遍历和查找操作的时间开销增加。长列表可能导致分配和释放操作的效率下降，尤其是在查找合适的空闲块或合并空闲块时。为了优化性能，可能需要定期的内存整理和碎片整理操作，以减少空间碎片和缩短列表长度。