面试题：内存管理之最佳适应算法的基础实现

Question

请简述最佳适应算法在内存分配中的基本原理，并使用一种你熟悉的编程语言实现一个简单的基于最佳适应算法的内存分配器，假设内存块大小和申请大小均为整数，内存块以链表形式存储。

Answer 1

最佳适应算法基本原理

最佳适应算法在内存分配时，会遍历所有可用的内存块，从这些内存块中挑选出大小最接近但又不小于请求分配大小的内存块进行分配。这样做的目的是尽量减少内存碎片，提高内存利用率。在分配后，如果该内存块还有剩余空间，则将剩余空间作为一个新的内存块继续保留在可用内存块链表中。

Python 实现基于最佳适应算法的内存分配器

class MemoryBlock:
    def __init__(self, size):
        self.size = size
        self.next = None


class MemoryAllocator:
    def __init__(self):
        self.free_list = None

    def add_free_block(self, size):
        new_block = MemoryBlock(size)
        new_block.next = self.free_list
        self.free_list = new_block

    def allocate(self, request_size):
        best_fit = None
        prev = None
        current = self.free_list
        while current:
            if current.size >= request_size and (not best_fit or current.size < best_fit.size):
                best_fit = current
                best_fit_prev = prev
            prev = current
            current = current.next

        if best_fit:
            if best_fit.size == request_size:
                if best_fit_prev:
                    best_fit_prev.next = best_fit.next
                else:
                    self.free_list = best_fit.next
            else:
                best_fit.size -= request_size
            return True
        return False

可以使用以下方式测试：

# 测试代码
allocator = MemoryAllocator()
allocator.add_free_block(100)
allocator.add_free_block(200)
allocator.add_free_block(50)

print(allocator.allocate(75))  
print(allocator.allocate(150))  
print(allocator.allocate(25))  

上述代码首先定义了表示内存块的 MemoryBlock 类和实现内存分配功能的 MemoryAllocator 类。add_free_block 方法用于向空闲内存块链表中添加新的内存块。allocate 方法实现了最佳适应算法，在空闲链表中查找最合适的内存块并进行分配。最后通过测试代码展示了如何使用这个内存分配器。