Python 中的 ID 分配器实现

Question

在我最近的一次采访中，我被要求实现一个 ID 分配器。

问题来了：

实现一个id分配器类，可以分配0~size-1范围内的id。这个类有2个方法：

1. alloc() - 分配一个未被使用的 id，返回它。
2. release(id) - 获取正在使用的 id，并使其可供分配。

后续要求基本上是维护一个位数组以节省空间，但是这两种方法的运行时间都需要优于线性。我被困在后续工作中，你们有什么想法吗？

from bitarray import bitarray

class id_allocator():

    def __init__(self, size):
        self.ids = bitarray(size) # 0 is available, 1 is unavailable

    def alloc(self):
        for idx, _id in enumerate(self.ids):
            if not _id:
                self.ids[idx] = True
                return idx
        raise Exception('no ids available')

    def release(self, _id):
        if _id > len(self.ids) or self.ids[_id] == True:
            raise Exception('invalid id')
        self.ids[_id] = False

Answer 1

如果您不必按顺序使用您的 id，您可以通过保留一组空闲 id 和一组已用 id 在恒定时间内完成此操作。

class IdAllocator():

    def __init__(self, size):
        self.free_ids = set(range(size))
        self.used_ids = set()

    def alloc(self):
        try:
            id = self.free_ids.pop()
            self.used_ids.add(id)
            return id

        except KeyError:
            raise Exception('No id available')

    def release(self, id):
        if id in self.used_ids:
            self.used_ids.remove(id)
            self.free_ids.add(id)

这不像使用

bitarray

那样具有内存效率，但 O(1) 时间复杂度可能超过它。

Answer 2

对于位数组方法的后续问题：假设您使用的是位操作而不是 Python 布尔列表，您可以使用二分搜索在 O(log n) 中找到一个空闲 ID。在每次迭代中，用您正在检查的间隔中的一系列位数组掩码并将结果与掩码进行比较。如果它们不相等，您就找到了包含免费 ID 的序列。