大厂算法：简易内存池

一、题目 §

请实现一个简易内存池，根据请求命令完成内存分配和释放。

内存池支持两种操作命令REQUEST和RELEASE。其格式为：

REQUEST=请求的内存大小

表示请求分配指定大小内存。 如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为零则输出error

RELEASE=释放的内存首地址

表示释放掉之前分配的内存。释放成功无需输出；如果释放不存在的首地址则输出error

注意：

1. 内存池总大小为100字节
2. 内存池地址分配必须是连续内存，并优先从低地址分配
3. 内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放
4. 不会释放已申请的内存块的中间地址
5. 释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其他内存块

二、输入 §

首行为整数N，表示操作命令的个数，取值范围0<N<=100

接下来的N行，每行将给出一个操作命令。操作命令和参数之间用”=“分割，输出描述见题目输出要求

三、输出 §

输出请求的内存块的首地址

四、示例 §

示例一

输入：
2
REQUEST=10
REQUEST=20

输出：
0
10

示例二

输入：
5
REQUEST=10
REQUEST=20
RELEASE=0
REQUEST=20
REQUEST=10

输出：
0
10
30
0

五、题解 §

1. 注意题解中的 memory 不是真正分配的内存，可以理解为真实内存的逻辑地址，用来管理真正内存块
2. 分配过的内存用 Map 来管理比较好理解；申请过的内存和释放的内存中通过标记数组来表示，让算法理解和实现起来更简单
3. 网上还有一种解法是通过 Java 的 TreeMap 来管理分配过的内存块（key 为内存块起始地址，值为终地址）。方法比较高效，但是实现起来稍微有点技巧

5.1 Java 实现 §

package org.stone.study.algo.ex202411;

import java.util.*;

/**
 * 简易内存池
 */
public class MemoryPool {

    private final int[] memory;
    private final Map<Integer, Integer> allocated;

    public MemoryPool() {
        this.memory = new int[100];
        Arrays.fill(memory, 0);
        this.allocated = new HashMap<>();
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        List<String> cmds = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            cmds.add(sc.nextLine());
        }

        List<Object> res = new MemoryPool().execute(cmds);
        res.forEach(System.out::println);
    }

    /**
     * 执行引擎
     * @param cmds
     * @return
     */
    public List<Object> execute(List<String> cmds) {
        List<Object> res = new ArrayList<>();
        for(String cmd : cmds) {
            String[] cmdArr = cmd.split("=");
            if("REQUEST".equals(cmdArr[0])) {
                res.add(request(Integer.parseInt(cmdArr[1])));
            } else if("RELEASE".equals(cmdArr[0])) {
                Object errMsg = release(Integer.parseInt(cmdArr[1]));
                if(errMsg != null) {
                    res.add(errMsg);
                }
            }
        }

        return res;
    }

    /**
     * 申请内存
     * @param size
     * @return
     */
    private Object request(int size) {
        int start = 0;
        if(size <= 0 || size > 100) {
            return "error";
        }

        while(start < 100) {
            // 找到连续的空闲内存起点
            while (start < 100 && memory[start] != 0) {
                start++;
            }
            if (start + size > 100) {
                return "error";
            }
            // 找到连续的空闲内存终点
            int end = start;
            while (end < 100 && memory[end] == 0) {
                ++end;
            }
            // 找打一块连续的空闲内存
            if (end - start >= size) {
                allocated.put(start, size);
                for (int i = start; i < start + size; i++) {
                    memory[i] = 1;
                }
                return start;
            }
            // 没有找到继续往后找连续内存
            start = end;
        }

        return "error";
    }

    /**
     * 释放内存
     * @param address
     * @return
     */
    private Object release(int address) {
        if(!allocated.containsKey(address)) {
            return "error";
        }

        int size = allocated.get(address);
        for(int i = address; i < address + size; i++) {
            memory[i] = 0;
        }

        allocated.remove(address);

        return null;
    }
}

5.2 Python实现 §

class MemoryPool:
    def __init__(self, size):
        self.size = size
        self.memory = [0] * size
        self.allocates = {}
    def request(self, size):
        if size <= 0 or size > self.size:
            return 'error'
        
        start = 0
        while start < self.size:
            # 找空闲内存起点
            while start < self.size and self.memory[start] != 0:
                start += 1
            if start + size > self.size:
                return 'error'
            # 找空闲内存终点
            end = start
            while end < self.size and self.memory[end] == 0:
                end += 1
            # 如果找到空闲内存
            if end - start >= size:
                self.memory[start:start+size] = [1] * size
                self.allocates[start] = size
                return start    
            
            start = end

        return 'error'
    
    def release(self, address):
        if address not in self.allocates:
            return 'error'

        size = self.allocates[address]
        self.memory[address : address + size] = [0] * size
        del self.allocates[address]

        return None

def main():
    # 5
    n = int(input())
    memoryPool = MemoryPool(100)

    res = []
    '''
    REQUEST=10
    REQUEST=20
    RELEASE=0
    REQUEST=20
    REQUEST=10
    '''
    for _ in range(n):
        op = input().split('=')
        if op[0] == 'REQUEST':
            size = int(op[1])
            res.append(memoryPool.request(size))
        elif op[0] == 'RELEASE':
            address = int(op[1])
            res.append(memoryPool.release(address))

    '''
    0
    10
    30
    0
    '''
    for s in res:
        if s != None:
            print(s)

if __name__ == '__main__':
    main()