毕业设计：实现一个简化版在线判题系统

这一课你将能做到

1. 设计一个在线判题系统的核心架构
2. 实现代码编译、运行、比对结果的完整流程
3. 运用所学的数据结构优化判题性能

为什么要学

毕业设计是检验你综合能力的试金石。把 12 节课的知识串起来，解决一个真实问题。这不仅巩固知识，还能写进简历，证明你不仅会做题，还会设计系统。

人话：就像学完所有武功招式后，打一套完整的拳法。判题系统涉及进程管理、资源限制、安全防护、性能优化，是数据结构与算法的综合应用。

先建立图像

用户提交 → 消息队列 → 判题机集群 → 编译 → 沙箱运行 → 结果比对 → 更新排行榜
              ↓                                              ↓
           Redis 缓存                                    MySQL 存储

核心挑战:
- 安全: 防止恶意代码 (fork炸弹、文件读写)
- 性能: 限制时间/内存，快速比对
- 公平: 统一环境，消除机器差异

跟着做

步骤 1：系统设计

// 核心类设计
public class JudgeSystem {
    // 提交记录
    static class Submission {
        String id;
        String code;
        String language; // "java", "python", "cpp"
        int timeLimit;   // 毫秒
        int memoryLimit; // MB
    }
    
    // 判题结果
    static class JudgeResult {
        String status;  // "AC", "WA", "TLE", "MLE", "RE", "CE"
        long timeUsed;  // 毫秒
        long memoryUsed; // KB
        String message;
    }
    
    // 测试用例
    static class TestCase {
        String input;
        String expectedOutput;
    }
}

步骤 2：编译模块

import java.io.*;
import java.nio.file.*;

public class Compiler {
    public static JudgeResult compileJava(String code, String workDir) throws IOException {
        // 写入 Main.java
        Path sourcePath = Paths.get(workDir, "Main.java");
        Files.write(sourcePath, code.getBytes());
        
        // 编译
        ProcessBuilder pb = new ProcessBuilder("javac", "Main.java");
        pb.directory(new File(workDir));
        pb.redirectErrorStream(true);
        Process process = pb.start();
        
        try {
            int exitCode = process.waitFor();
            if (exitCode != 0) {
                String error = new String(process.getInputStream().readAllBytes());
                return new JudgeResult("CE", 0, 0, error);
            }
            return new JudgeResult("OK", 0, 0, "编译成功");
        } catch (InterruptedException e) {
            return new JudgeResult("CE", 0, 0, "编译被中断");
        }
    }
    
    public static void main(String[] args) throws IOException {
        String code = "public class Main { public static void main(String[] args) { System.out.println(\"Hello\"); } }";
        JudgeResult res = compileJava(code, "/tmp/judge/123");
        System.out.println(res.status);
    }
}

步骤 3：沙箱运行（简化版）

import java.io.*;
import java.util.concurrent.*;

public class Sandbox {
    public static JudgeResult run(String workDir, TestCase tc, int timeLimit, int memoryLimit) {
        try {
            ProcessBuilder pb = new ProcessBuilder("java", 
                "-Xmx" + memoryLimit + "m",  // 内存限制
                "-XX:MaxRAM=" + memoryLimit + "m",
                "Main");
            pb.directory(new File(workDir));
            pb.redirectErrorStream(true);
            
            Process process = pb.start();
            
            // 提供输入
            try (PrintWriter writer = new PrintWriter(process.getOutputStream())) {
                writer.print(tc.input);
                writer.flush();
            }
            
            // 定时器检查 TLE
            boolean finished = process.waitFor(timeLimit, TimeUnit.MILLISECONDS);
            if (!finished) {
                process.destroyForcibly();
                return new JudgeResult("TLE", timeLimit, 0, "超出时间限制");
            }
            
            // 读取输出
            String output = new String(process.getInputStream().readAllBytes());
            int exitCode = process.exitValue();
            
            if (exitCode != 0) {
                return new JudgeResult("RE", 0, 0, "运行时错误，退出码: " + exitCode);
            }
            
            // 比对结果（忽略行尾空格和多余空行）
            if (compareOutput(output.trim(), tc.expectedOutput.trim())) {
                return new JudgeResult("AC", 0, 0, "通过");
            } else {
                return new JudgeResult("WA", 0, 0, "答案错误");
            }
            
        } catch (Exception e) {
            return new JudgeResult("RE", 0, 0, e.getMessage());
        }
    }
    
    private static boolean compareOutput(String actual, String expected) {
        String[] aLines = actual.split("\n");
        String[] eLines = expected.split("\n");
        if (aLines.length != eLines.length) return false;
        for (int i = 0; i < aLines.length; i++) {
            if (!aLines[i].trim().equals(eLines[i].trim())) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        TestCase tc = new TestCase("1 2", "3");
        JudgeResult res = run("/tmp/judge/123", tc, 2000, 256);
        System.out.println(res.status);
    }
}

步骤 4：性能优化——线程池与缓存

import java.util.concurrent.*;
import java.util.*;

public class JudgePool {
    private final ExecutorService executor;
    private final Map<String, JudgeResult> cache; // 编译结果缓存
    
    public JudgePool(int poolSize) {
        this.executor = Executors.newFixedThreadPool(poolSize);
        this.cache = new ConcurrentHashMap<>();
    }
    
    public CompletableFuture<JudgeResult> judge(Submission sub, List<TestCase> testCases) {
        return CompletableFuture.supplyAsync(() -> {
            String workDir = "/tmp/judge/" + sub.id;
            
            // 检查编译缓存
            String cacheKey = sub.code.hashCode() + "";
            if (cache.containsKey(cacheKey)) {
                return cache.get(cacheKey);
            }
            
            try {
                // 编译
                JudgeResult compileRes = Compiler.compileJava(sub.code, workDir);
                if (!compileRes.status.equals("OK")) {
                    return compileRes;
                }
                
                // 运行所有测试用例
                for (TestCase tc : testCases) {
                    JudgeResult runRes = Sandbox.run(workDir, tc, sub.timeLimit, sub.memoryLimit);
                    if (!runRes.status.equals("AC")) {
                        return runRes;
                    }
                }
                
                JudgeResult ac = new JudgeResult("AC", 0, 0, "全部通过");
                cache.put(cacheKey, ac);
                return ac;
                
            } catch (Exception e) {
                return new JudgeResult("SE", 0, 0, "系统错误: " + e.getMessage());
            }
        }, executor);
    }
    
    public void shutdown() {
        executor.shutdown();
    }
    
    public static void main(String[] args) throws Exception {
        JudgePool pool = new JudgePool(4);
        Submission sub = new Submission();
        sub.id = "test001";
        sub.code = "public class Main { public static void main(String[] args) { java.util.Scanner sc = new java.util.Scanner(System.in); System.out.println(sc.nextInt() + sc.nextInt()); } }";
        sub.timeLimit = 2000;
        sub.memoryLimit = 256;
        
        TestCase tc = new TestCase("1 2", "3");
        CompletableFuture<JudgeResult> future = pool.judge(sub, Arrays.asList(tc));
        System.out.println(future.get().status);
        pool.shutdown();
    }
}

步骤 5：排行榜（堆的应用）

import java.util.*;

public class Leaderboard {
    static class User {
        String name;
        int acCount;
        long totalTime;
        User(String n, int c, long t) { name = n; acCount = c; totalTime = t; }
    }
    
    // 大顶堆：AC 数多者优先，相同则时间少者优先
    private PriorityQueue<User> heap = new PriorityQueue<>(
        (a, b) -> a.acCount != b.acCount 
            ? b.acCount - a.acCount 
            : Long.compare(a.totalTime, b.totalTime)
    );
    
    public void addUser(String name, int acCount, long totalTime) {
        heap.offer(new User(name, acCount, totalTime));
    }
    
    public List<String> getTopN(int n) {
        List<String> res = new ArrayList<>();
        PriorityQueue<User> copy = new PriorityQueue<>(heap);
        for (int i = 0; i < n && !copy.isEmpty(); i++) {
            res.add(copy.poll().name);
        }
        return res;
    }
    
    public static void main(String[] args) {
        Leaderboard lb = new Leaderboard();
        lb.addUser("Alice", 10, 5000);
        lb.addUser("Bob", 10, 3000);
        lb.addUser("Charlie", 8, 2000);
        System.out.println(lb.getTopN(3)); // [Bob, Alice, Charlie]
    }
}

讲清楚要点

1. 安全第一：真实判题系统用容器（Docker）或 chroot 隔离，禁止文件/网络/系统调用。简化版用 JVM 沙箱。
2. 资源限制：-Xmx 限制堆内存，外部监控限制 CPU 时间和真实内存。
3. 结果比对：精确比对（严格模式）和忽略空白（宽松模式）。浮点数要设误差范围。
4. 性能关键：编译缓存（相同代码不重复编译）、线程池并行判题、消息队列削峰。

你可能会懵的地方

• 为什么用线程池不是进程池？ Java 进程启动慢（~100ms），线程池轻量。但安全隔离需要进程/容器。真实系统：Java 用 JVM 沙箱+安全策略，C++ 用容器。

• 怎么防止死循环代码？ 外部定时器强制 kill。JVM 内部无法可靠终止线程（Thread.stop 已废弃），必须用进程。

• 排行榜为什么用堆不用排序？ 每次更新排序是 O(n log n)，堆更新是 O(log n)，取 Top K 是 O(K log n)。数据量大时堆更优。

• 测试用例怎么存储？ 数据库存元数据（题目 ID、输入输出文件路径），文件系统存实际数据。大文件不放数据库。

• 怎么支持多种语言？ 抽象编译/运行接口，每种语言实现具体逻辑。Java 用 javac，Python 直接 python script.py，C++ 用 g++。

错法对照

错法	问题	正解
直接运行用户代码不隔离	恶意代码破坏系统	容器/沙箱隔离，限制系统调用
编译不缓存	重复编译浪费时间	按代码哈希缓存编译结果
结果比对逐字符	格式差异导致 WA	忽略行尾空格和多余空行
单线程判题	并发量低	线程池+消息队列
排行榜用数组排序	更新慢	用堆或有序集合（TreeMap）

卡点急救

1. Java 程序内存超限：-Xmx 设小一点，或用 -XX:MaxRAM 限制真实内存。
2. 多测试用例 TLE：预热 JVM（先跑一个 dummy 用例），或允许 Java 更长时限。
3. 结果比对错误：打印实际输出和期望输出的十六进制，检查不可见字符。

面试常问

• 设计一个判题系统的核心挑战？ 安全隔离（防恶意代码）、资源限制（时间/内存）、高并发（多用户同时提交）、结果准确（精确比对）。

• 怎么实现代码查重？ 提取 AST（抽象语法树）计算相似度，或用 SimHash/MinHash 做文本指纹。

• 排行榜数据量大怎么优化？ Redis Sorted Set（ZSET）缓存，定期同步到 MySQL。或分片：按时间段/题目分排行榜。

自测三问

1. 判题系统为什么要限制内存和时间？
2. 排行榜用堆和用排序各有什么优劣？
3. 如何防止用户提交死循环代码？

小结一句话

判题系统是数据结构与算法的综合应用：哈希表做缓存，堆做排行榜，队列做任务调度，沙箱保安全；掌握它，就掌握了从做题到设计系统的跨越。

延伸

• Java 官方文档：Process API
• 恭喜完成全部课程！建议：继续刷题巩固，参与开源项目，阅读《算法导论》深入理论。