最佳适应算法和最坏适应算法

Question

使用链表这种数据结构用Python实现最佳适应算法和最坏适应算法

Answer 1

引自免费微信小程序：皆我百晓生

最佳适应算法（Best Fit）和最坏适应算法（Worst Fit）是两种内存管理策略，用于分配和回收内存块。它们通常在操作系统、编程语言运行时环境或其他需要动态分配内存的系统中使用。

1. 最佳适应算法：选择当前可用内存块中最小的一个来满足进程的需求。这可能会导致内存碎片。
2. 最坏适应算法：总是选择当前可用内存块中最大的一个来满足进程的需求。这可能会浪费大量内存空间。

下面我将分别使用Python实现这两种算法，并使用链表作为数据结构来存储内存块。

首先，我们需要定义一个表示内存块的类MemoryBlock，以及一个表示内存池的类MemoryPool，包含插入、删除和分配内存块的方法。

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


class Node:
    def __init__(self, memory_block):
        self.block = memory_block
        self.next = None


class MemoryPool:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert(self, size):
        new_block = MemoryBlock(size)
        if not self.head:
            self.head = self.tail = Node(new_block)
        else:
            self.tail.next = Node(new_block)
            self.tail = self.tail.next

    def delete(self, block):
        current = self.head
        prev = None
        while current:
            if current.block is block:
                if prev:
                    prev.next = current.next
                else:
                    self.head = current.next
                if current == self.tail:
                    self.tail = prev
                return
            prev = current
            current = current.next

    def best_fit(self, required_size):
        current = self.head
        smallest_size = float('inf')
        smallest_block = None
        while current:
            if current.block.size >= required_size and current.block.size < smallest_size:
                smallest_size = current.block.size
                smallest_block = current.block
            current = current.next
        if smallest_block:
            self.delete(smallest_block)
            return smallest_block
        else:
            return None

    def worst_fit(self, required_size):
        current = self.head
        largest_size = 0
        largest_block = None
        while current:
            if current.block.size > largest_size:
                largest_size = current.block.size
                largest_block = current.block
            current = current.next
        if largest_block:
            self.delete(largest_block)
            return largest_block
        else:
            return None

接下来，我们创建一个简单的测试用例：

def test_memory_pools():
    mem_pool = MemoryPool()
    
    # 插入一些内存块
    for i in range(5, 16, 3):
        mem_pool.insert(i)

    print("Best Fit:")
    for i in [8, 4, 9, 15]:
        block = mem_pool.best_fit(i)
        if block:
            print(f"Required: {i}, Allocated: {block.size}")
        else:
            print(f"No suitable block found for {i}")

    print("\nWorst Fit:")
    for i in [8, 4, 9, 15]:
        block = mem_pool.worst_fit(i)
        if block:
            print(f"Required: {i}, Allocated: {block.size}")
        else:
            print(f"No suitable block found for {i}")

test_memory_pools()

这段代码首先创建了一个内存池并插入了一些内存块，然后分别使用最佳适应和最坏适应算法为不同的请求分配内存。输出将会显示每次分配的结果，包括所需大小和实际分配的内存块大小。

注意，由于这是一个简化的实现，它没有处理内存块的合并和碎片问题。在实际应用中，可能还需要添加额外的逻辑来优化内存管理和减少碎片。