Python实现ID分配器：面试问题及后续优化需求问询

Core Requirements Recap #

We need a class that manages IDs in the range 0 to size-1, with two key methods:

• alloc(): Returns an unused ID, marking it as allocated.
• release(id): Marks an allocated ID as available again.

The constraints are:

• Space efficiency: Use a bit array (each bit represents an ID's state) instead of a full boolean array.
• Time efficiency: Both methods should run in near-O(1) average time.

Approach #

1. Bit Array for Space Savings #

Instead of using a boolean array (where each entry takes 1 byte), we use a bit array: each bit corresponds to one ID. A value of 1 means the ID is allocated, 0 means it's free. This cuts space usage by 7/8 (since 1 byte = 8 bits).

In practice, we simulate a bit array using an array of integers (each integer holds 64 bits, for example). For a size of N, we need (N + 63) // 64 integers to store all bits.

2. Free ID Stack for Fast Allocation #

To avoid scanning the entire bit array every time we need an ID (which would be O(n)), we maintain a stack of recently released IDs. When alloc() is called:

• First, pop an ID from the stack if it's not empty (O(1) operation).
• If the stack is empty, allocate the next sequential unassigned ID (tracking with a next_alloc pointer, also O(1)).

3. O(1) Release Operation #

When releasing an ID, we:

• Mark the corresponding bit in the array as free.
• Push the ID onto the free stack so it can be reused quickly.

Implementation (Python) #

Here's a complete implementation with error handling and efficient operations:

class IDAllocator:
    def __init__(self, size):
        if size <= 0:
            raise ValueError("Size must be a positive integer")
        self.size = size
        # Calculate number of 64-bit integers needed to store the bit array
        self.bit_array = [0] * ((size + 63) // 64)
        self.free_stack = []
        self.next_alloc = 0

    def _is_allocated(self, id):
        """Helper to check if an ID is currently allocated"""
        idx = id // 64
        bit_pos = id % 64
        return (self.bit_array[idx] & (1 << bit_pos)) != 0

    def _mark_allocated(self, id):
        """Helper to mark an ID as allocated"""
        idx = id // 64
        bit_pos = id % 64
        self.bit_array[idx] |= (1 << bit_pos)

    def _mark_free(self, id):
        """Helper to mark an ID as free"""
        idx = id // 64
        bit_pos = id % 64
        self.bit_array[idx] &= ~(1 << bit_pos)

    def alloc(self):
        """Allocate and return an unused ID"""
        # Prioritize reusing released IDs first
        if self.free_stack:
            id = self.free_stack.pop()
            self._mark_allocated(id)
            return id
        # If no free IDs left, assign the next sequential ID
        if self.next_alloc < self.size:
            id = self.next_alloc
            self.next_alloc += 1
            self._mark_allocated(id)
            return id
        # No available IDs remaining
        raise RuntimeError("No available IDs to allocate")

    def release(self, id):
        """Release an allocated ID back to the pool"""
        if not (0 <= id < self.size):
            raise ValueError(f"ID {id} is out of range (valid range: 0 to {self.size-1})")
        if not self._is_allocated(id):
            raise RuntimeError(f"ID {id} is not currently allocated")
        
        self._mark_free(id)
        self.free_stack.append(id)

How to Test It #

Let's run a quick test to verify the functionality:

# Initialize allocator with 5 IDs (0-4)
allocator = IDAllocator(5)

# Allocate first two IDs
print(allocator.alloc())  # Output: 0
print(allocator.alloc())  # Output: 1

# Release ID 0 and allocate again
allocator.release(0)
print(allocator.alloc())  # Output: 0

# Release both allocated IDs and reallocate
allocator.release(1)
allocator.release(0)
print(allocator.alloc())  # Output: 0
print(allocator.alloc())  # Output: 1

# Allocate remaining IDs
print(allocator.alloc())  # Output: 2
print(allocator.alloc())  # Output: 3
print(allocator.alloc())  # Output: 4

# Try to allocate when none are left (should throw error)
try:
    print(allocator.alloc())
except RuntimeError as e:
    print(e)  # Output: No available IDs to allocate

Key Efficiency Notes #

• Space: For a size of 10,000, the bit array uses only (10000 +63)//64 = 157 integers, which is 157*4=628 bytes (vs 10,000 bytes for a boolean array).
• Time: alloc() runs in O(1) average time (stack pops are O(1), and sequential allocation is O(1)). release() is always O(1) (bit manipulation and stack push are constant time).

内容的提问来源于stack exchange，提问作者Pig