每日算法 — 使用java实现打地鼠：蓄水池抽样与流式反应时间在线中位数估计

引言

打地鼠（Whack-a-Mole）是一款考验反应速度的经典街机游戏：地鼠随机从多个洞口冒出，玩家需要在其缩回之前用锤子击中。从算法视角看，打地鼠蕴含了两个有趣的统计问题：一是地鼠出现位置的随机抽样（可建模为带权随机抽样），二是玩家反应时间的流式统计分析（需要在游戏进行过程中实时更新统计量）。本文将引入蓄水池抽样（Reservoir Sampling）算法，将其创新性地应用于打地鼠场景中的在线中位数估计——在不知道总样本量的情况下，实时维护一个反应时间样本集，并高效计算中位数，为动态难度调整提供数据支持。

问题建模

场景定义

假设打地鼠游戏有 $M$ 个洞口，地鼠按某种概率分布随机出现。玩家的每次击打都会产生一个反应时间 $t_i$（从地鼠出现到被击中的毫秒数）。随着游戏进行，反应时间序列 $t_1, t_2, …, t_N$ 以流式方式到达，$N$ 在游戏结束前未知。

核心算法挑战

1. 在线中位数估计：需要在每次击打后即时更新中位数，用于动态调整地鼠停留时间（反应快的玩家对应更短停留时间）
2. 内存限制：无法存储全部反应时间（流式数据可能无限长）
3. 均匀采样保证：蓄水池抽样确保每个反应时间被选入样本集的概率相等

蓄水池抽样原理

蓄水池抽样能够在数据流长度为 $N$ 且 $N$ 未知的情况下，从流中均匀随机选取 $k$ 个样本，保证每个元素被选中的概率均为 $k/N$。

算法流程：
1. 前 $k$ 个元素直接放入蓄水池
2. 对于第 $i$ 个元素（$i > k$），以 $k/i$ 的概率替换蓄水池中的某个随机元素

双堆结构维护中位数

在蓄水池中维护两个堆：
– 最大堆（小半部分）：存储较小的一半数据，堆顶为较小部分的最大值
– 最小堆（大半部分）：存储较大的一半数据，堆顶为较大部分的最小值

中位数规则：
– 当蓄水池大小为奇数时，中位数为最大堆的堆顶
– 当蓄水池大小为偶数时，中位数为两个堆顶的平均值

Java实现

项目结构

src/
├── game/
│   ├── Mole.java           // 地鼠模型
│   ├── Hole.java           // 洞口模型
│   └── WhackAMoleGame.java // 游戏主控
├── sampling/
│   ├── ReservoirSampler.java // 蓄水池抽样器
│   └── OnlineMedian.java     // 在线中位数估计器
├── stats/
│   └── ReactionTimeStats.java // 统计量计算
└── Main.java

Mole.java & Hole.java

package game;

import java.util.Random;

/**
 * 地鼠出现事件
 */
public class MoleEvent {
    public final long appearTime;   // 地鼠出现时间戳（毫秒）
    public final int holeIndex;     // 出现的洞口编号
    public final long stayDuration; // 地鼠计划停留的毫秒数

    public MoleEvent(long appearTime, int holeIndex, long stayDuration) {
        this.appearTime = appearTime;
        this.holeIndex = holeIndex;
        this.stayDuration = stayDuration;
    }
}

/**
 * 玩家击打事件
 */
public class WhackEvent {
    public final long whackTime;    // 击打时间戳
    public final int holeIndex;     // 击打的洞口
    public final boolean hit;       // 是否命中
    public final long reactionTime; // 反应时间（出现到击打）

    public WhackEvent(long whackTime, int holeIndex, boolean hit, long reactionTime) {
        this.whackTime = whackTime;
        this.holeIndex = holeIndex;
        this.hit = hit;
        this.reactionTime = reactionTime;
    }
}

/**
 * 洞口管理器
 * 负责按概率分布选择地鼠出现的洞口
 */
public class HoleManager {
    private final int numHoles;
    private final double[] probabilities; // 每个洞口的出现概率
    private final Random rand;

    public HoleManager(int numHoles, Random rand) {
        this.numHoles = numHoles;
        this.rand = rand;
        this.probabilities = new double[numHoles];
        // 默认均匀分布
        for (int i = 0; i < numHoles; i++) {
            probabilities[i] = 1.0 / numHoles;
        }
    }

    /**
     * 按概率分布随机选择一个洞口
     */
    public int selectHole() {
        double r = rand.nextDouble();
        double cumulative = 0.0;
        for (int i = 0; i < numHoles; i++) {
            cumulative += probabilities[i];
            if (r <= cumulative) return i;
        }
        return numHoles - 1;
    }

    public int getNumHoles() { return numHoles; }

    /**
     * 动态调整洞口概率（可根据游戏策略改变）
     */
    public void setProbability(int hole, double prob) {
        probabilities[hole] = prob;
    }
}

ReservoirSampler.java — 蓄水池抽样器

package sampling;

import java.util.*;

/**
 * 通用蓄水池抽样器
 * 从长度未知的数据流中均匀随机抽取k个样本
 * 保证每个元素被选中的概率 = k/N（N为流的总长度）
 *
 * @param <T> 样本类型
 */
public class ReservoirSampler<T> {
    private final int capacity;     // 蓄水池容量k
    private final List<T> reservoir; // 蓄水池
    private final Random rand;
    private long streamCount;        // 已处理的流元素总数

    public ReservoirSampler(int capacity, Random rand) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("蓄水池容量必须大于0");
        }
        this.capacity = capacity;
        this.rand = rand;
        this.reservoir = new ArrayList<>(capacity);
        this.streamCount = 0;
    }

    /**
     * 处理流中的下一个元素
     * @param element 流中的新元素
     */
    public void feed(T element) {
        streamCount++;

        if (reservoir.size() < capacity) {
            // 前k个元素直接放入蓄水池
            reservoir.add(element);
        } else {
            // 第i个元素（i > k），以 k/i 的概率替换蓄水池中的随机元素
            long i = streamCount; // 当前元素序号（1-based）
            int j = rand.nextInt((int) Math.min(i, Integer.MAX_VALUE));
            if (j < capacity) {
                reservoir.set(j, element);
            }
        }
    }

    /**
     * 批量处理多个元素
     */
    public void feedAll(Collection<T> elements) {
        for (T e : elements) feed(e);
    }

    public List<T> getReservoir() {
        return new ArrayList<>(reservoir);
    }

    public int getCapacity() { return capacity; }
    public long getStreamCount() { return streamCount; }
    public int getCurrentSize() { return reservoir.size(); }

    /**
     * 清空蓄水池，重新开始采样
     */
    public void reset() {
        reservoir.clear();
        streamCount = 0;
    }

    /**
     * 验证抽样的均匀性（辅助测试用）
     * 理论上每个元素被选中的概率 = min(1, k/i) 的累积效果 = k/N
     */
    public static <T> void validateUniformity(List<T> stream, int k, int trials) {
        Map<T, Integer> countMap = new HashMap<>();
        Random r = new Random(42);

        for (int t = 0; t < trials; t++) {
            ReservoirSampler<T> sampler = new ReservoirSampler<>(k, r);
            for (T e : stream) sampler.feed(e);
            for (T e : sampler.getReservoir()) {
                countMap.merge(e, 1, Integer::sum);
            }
        }

        double expected = (double) k * trials / stream.size();
        System.out.println("均匀性验证（期望每个元素被选中约" + String.format("%.1f", expected) + "次）：");
        for (Map.Entry<T, Integer> entry : countMap.entrySet()) {
            System.out.printf("  元素 %s: 实际=%d, 期望=%.1f%n",
                entry.getKey(), entry.getValue(), expected);
        }
    }
}

OnlineMedian.java — 在线中位数估计器

package sampling;

import java.util.*;

/**
 * 基于双堆结构的在线中位数估计器
 * 配合蓄水池抽样，在流式数据环境下实时维护中位数
 *
 * 数据结构：
 * - maxHeap（小半部分）：存储较小的那一半数据，堆顶是较小部分的最大值
 * - minHeap（大半部分）：存储较大的那一半数据，堆顶是较大部分的最小值
 * - 中位数：奇数时取maxHeap堆顶，偶数时取两堆顶平均
 */
public class OnlineMedian {
    // 最大堆用于存储较小的一半数据（Java的PriorityQueue默认是最小堆，需要反转）
    private final PriorityQueue<Long> maxHeap;
    // 最小堆用于存储较大的一半数据
    private final PriorityQueue<Long> minHeap;

    public OnlineMedian() {
        // 最大堆：使用Comparator.reverseOrder()
        this.maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        // 最小堆：默认自然顺序
        this.minHeap = new PriorityQueue<>();
    }

    /**
     * 向数据流中添加一个新值，并维护双堆平衡
     * 时间复杂度：O(log n)
     */
    public void add(long value) {
        if (maxHeap.isEmpty() || value <= maxHeap.peek()) {
            maxHeap.offer(value);
        } else {
            minHeap.offer(value);
        }

        // 维护平衡：两个堆的大小差不超过1，且maxHeap可以比minHeap多1个元素
        rebalance();
    }

    /**
     * 批量添加多个值
     */
    public void addAll(Collection<Long> values) {
        for (long v : values) add(v);
    }

    private void rebalance() {
        // maxHeap最多比minHeap大1
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    /**
     * 获取当前中位数
     * 时间复杂度：O(1)
     */
    public double getMedian() {
        if (maxHeap.isEmpty()) {
            throw new IllegalStateException("数据为空，无法计算中位数");
        }

        if (maxHeap.size() == minHeap.size()) {
            // 偶数个：取两个堆顶的平均值
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            // 奇数个：maxHeap多一个元素，取maxHeap堆顶
            return maxHeap.peek();
        }
    }

    /**
     * 获取当前 MAD（Median Absolute Deviation，中位数绝对偏差）
     * 用于衡量反应时间的离散程度，比标准差更鲁棒
     * MAD = median(|x_i - median|)
     */
    public double getMAD() {
        if (maxHeap.isEmpty()) return 0.0;

        double median = getMedian();
        List<Long> allData = getAllData();
        List<Double> absDeviations = new ArrayList<>();
        for (long v : allData) {
            absDeviations.add(Math.abs(v - median));
        }
        Collections.sort(absDeviations);
        int n = absDeviations.size();
        if (n % 2 == 1) {
            return absDeviations.get(n / 2);
        } else {
            return (absDeviations.get(n / 2 - 1) + absDeviations.get(n / 2)) / 2.0;
        }
    }

    /**
     * 获取四分位距 IQR = Q3 - Q1
     */
    public double getIQR() {
        List<Long> sorted = getAllData();
        Collections.sort(sorted);
        int n = sorted.size();
        if (n < 4) return 0.0;

        double q1 = getPercentile(sorted, 0.25);
        double q3 = getPercentile(sorted, 0.75);
        return q3 - q1;
    }

    private double getPercentile(List<Long> sorted, double p) {
        double pos = p * (sorted.size() - 1);
        int lower = (int) Math.floor(pos);
        int upper = (int) Math.ceil(pos);
        double weight = pos - lower;
        return sorted.get(lower) * (1 - weight) + sorted.get(upper) * weight;
    }

    public List<Long> getAllData() {
        List<Long> all = new ArrayList<>();
        all.addAll(maxHeap);
        all.addAll(minHeap);
        return all;
    }

    public int size() {
        return maxHeap.size() + minHeap.size();
    }

    public void clear() {
        maxHeap.clear();
        minHeap.clear();
    }

    @Override
    public String toString() {
        return String.format("OnlineMedian{size=%d, median=%.1f, MAD=%.1f, IQR=%.1f}",
            size(), getMedian(), getMAD(), getIQR());
    }
}

ReactionTimeStats.java — 反应时间统计分析器

package stats;

import sampling.OnlineMedian;
import sampling.ReservoirSampler;
import java.util.*;

/**
 * 打地鼠游戏反应时间统计分析器
 * 结合蓄水池抽样和在线中位数，为动态难度调整提供实时统计支持
 */
public class ReactionTimeStats {
    private final ReservoirSampler<Long> sampler; // 蓄水池抽样器
    private final OnlineMedian onlineMedian;        // 在线中位数（基于全部数据）
    private final int reservoirSize;                // 蓄水池容量

    // 动态难度调整参数
    private long baseStayDuration;   // 基础停留时间（毫秒）
    private long minStayDuration;    // 最短停留时间
    private long maxStayDuration;    // 最长停留时间

    public ReactionTimeStats(int reservoirSize, long baseStayDuration,
                             long minStayDuration, long maxStayDuration,
                             Random rand) {
        this.reservoirSize = reservoirSize;
        this.sampler = new ReservoirSampler<>(reservoirSize, rand);
        this.onlineMedian = new OnlineMedian();
        this.baseStayDuration = baseStayDuration;
        this.minStayDuration = minStayDuration;
        this.maxStayDuration = maxStayDuration;
    }

    /**
     * 记录一次击打事件的反应时间
     */
    public void recordReactionTime(long reactionTime) {
        sampler.feed(reactionTime);
        onlineMedian.add(reactionTime);
    }

    /**
     * 基于蓄水池样本计算的中位数估计
     * 适用于大数据流场景（内存受限）
     */
    public double getReservoirMedian() {
        List<Long> samples = sampler.getReservoir();
        if (samples.isEmpty()) return baseStayDuration;
        List<Long> sorted = new ArrayList<>(samples);
        Collections.sort(sorted);
        int n = sorted.size();
        if (n % 2 == 1) return sorted.get(n / 2);
        return (sorted.get(n / 2 - 1) + sorted.get(n / 2)) / 2.0;
    }

    /**
     * 基于全部数据的精确中位数（仅保留最近数据）
     * 如果数据量超过蓄水池容量，则回退到蓄水池估计
     */
    public double getMedian() {
        if (onlineMedian.size() <= reservoirSize) {
            return onlineMedian.getMedian();
        }
        return getReservoirMedian();
    }

    /**
     * 动态调整地鼠停留时间
     * 策略：中位数反应时间越短，停留时间越短（难度越高）
     * @return 调整后的停留时间（毫秒）
     */
    public long adjustStayDuration() {
        double median = getMedian();
        double mad = onlineMedian.getMAD();

        // 自适应公式：
        // 停留时间 = 基础时间 * (反应时间中位数 / 基准反应时间)
        // 加入MAD作为"反应时间稳定性"的调节因子
        long baselineReaction = 500; // 基准反应时间500ms

        double ratio = median / baselineReaction;
        // MAD越小说明反应越稳定，可以适当降低停留时间
        double stabilityFactor = Math.max(0.5, 1.0 - (mad / 1000.0) * 0.3);

        long adjusted = (long) (baseStayDuration * ratio * stabilityFactor);
        return Math.max(minStayDuration, Math.min(maxStayDuration, adjusted));
    }

    /**
     * 判断玩家当前状态
     */
    public PlayerState assessPlayerState() {
        double median = getMedian();
        double mad = onlineMedian.getMAD();

        if (median < 300 && mad < 100) return PlayerState.EXPERT;
        if (median < 500 && mad < 200) return PlayerState.SKILLED;
        if (median < 800) return PlayerState.NOVICE;
        return PlayerState.BEGINNER;
    }

    /**
     * 打印当前统计报告
     */
    public void printReport() {
        System.out.println("=== 反应时间统计报告 ===");
        System.out.println("  总样本数: " + sampler.getStreamCount());
        System.out.println("  蓄水池大小: " + sampler.getCurrentSize() + "/" + reservoirSize);
        System.out.println("  蓄水池中位数: " + String.format("%.1f", getReservoirMedian()) + " ms");
        if (onlineMedian.size() <= reservoirSize) {
            System.out.println("  精确中位数: " + String.format("%.1f", onlineMedian.getMedian()) + " ms");
        }
        System.out.println("  MAD: " + String.format("%.1f", onlineMedian.getMAD()) + " ms");
        System.out.println("  IQR: " + String.format("%.1f", onlineMedian.getIQR()) + " ms");
        System.out.println("  玩家水平: " + assessPlayerState());
        System.out.println("  建议停留时间: " + adjustStayDuration() + " ms");
    }

    public enum PlayerState {
        BEGINNER("新手"), NOVICE("初级"), SKILLED("熟练"), EXPERT("专家");
        public final String label;
        PlayerState(String label) { this.label = label; }
    }
}

WhackAMoleGame.java — 游戏主控

package game;

import stats.ReactionTimeStats;
import java.util.*;

/**
 * 打地鼠游戏模拟器
 * 演示蓄水池抽样与在线中位数在动态难度调整中的应用
 */
public class WhackAMoleGame {
    private final HoleManager holeManager;
    private final ReactionTimeStats stats;
    private final Random rand;

    private long currentStayDuration; // 当前地鼠停留时间
    private int score;
    private int totalMoles;
    private int hitMoles;

    public WhackAMoleGame(int numHoles, int reservoirSize, Random rand) {
        this.rand = rand;
        this.holeManager = new HoleManager(numHoles, rand);
        this.stats = new ReactionTimeStats(
            reservoirSize,
            1500,   // 基础停留1.5秒
            400,    // 最短0.4秒
            3000,   // 最长3秒
            rand
        );
        this.currentStayDuration = 1500;
        this.score = 0;
    }

    /**
     * 模拟一局游戏
     * @param numRounds 进行的轮数
     */
    public void play(int numRounds) {
        System.out.println("=== 打地鼠游戏开始 ===");
        System.out.println("洞口数量: " + holeManager.getNumHoles());
        System.out.println("蓄水池容量: " + stats);

        for (int round = 1; round <= numRounds; round++) {
            // 1. 地鼠出现
            int hole = holeManager.selectHole();
            long appearTime = System.currentTimeMillis();
            MoleEvent mole = new MoleEvent(appearTime, hole, currentStayDuration);

            // 2. 模拟玩家反应（反应时间与当前停留时间和玩家"能力"相关）
            long reactionTime = simulatePlayerReaction();
            boolean hit = reactionTime <= currentStayDuration;
            long whackTime = appearTime + reactionTime;

            WhackEvent whack = new WhackEvent(whackTime, hole, hit, reactionTime);

            // 3. 记录统计
            if (hit) {
                stats.recordReactionTime(reactionTime);
                score += 10;
                hitMoles++;
            }
            totalMoles++;

            // 4. 动态调整难度
            if (round % 10 == 0) {
                currentStayDuration = stats.adjustStayDuration();
                System.out.println("\n--- 第" + round + "轮后难度调整 ---");
                stats.printReport();
            }
        }

        // 最终报告
        System.out.println("\n=== 游戏结束 ===");
        System.out.println("总轮数: " + numRounds);
        System.out.println("命中率: " + hitMoles + "/" + totalMoles +
            " (" + String.format("%.1f", 100.0 * hitMoles / totalMoles) + "%)");
        System.out.println("总得分: " + score);
        stats.printReport();
    }

    /**
     * 模拟玩家反应时间
     * 使用正态分布模拟，均值随游戏进行逐渐降低（玩家变强）
     */
    private long simulatePlayerReaction() {
        // 模拟一个反应时间在 200ms - 1200ms 之间的玩家
        double mean = 600 - stats.getMedian() * 0.2; // 自适应：反应越快均值越低
        double std = 150;
        long reaction = (long) (mean + rand.nextGaussian() * std);
        return Math.max(100, Math.min(2000, reaction));
    }

    public int getScore() { return score; }
}

Main.java

import game.WhackAMoleGame;
import sampling.ReservoirSampler;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Random rand = new Random(42);

        // 演示1：蓄水池抽样的均匀性验证
        System.out.println("=== 演示1：蓄水池抽样均匀性验证 ===");
        List<Integer> stream = new ArrayList<>();
        for (int i = 1; i <= 100; i++) stream.add(i);
        ReservoirSampler.validateUniformity(stream, 10, 10000);

        // 演示2：打地鼠游戏与动态难度调整
        System.out.println("\n=== 演示2：打地鼠游戏（蓄水池+在线中位数） ===");
        WhackAMoleGame game = new WhackAMoleGame(9, 50, rand);
        game.play(100);
    }
}

算法复杂度分析

总结

本文将蓄水池抽样算法创新性地应用于打地鼠游戏的反应时间分析，实现了在流式数据环境下的在线中位数估计。该方法的核心优势包括：

1. 内存恒定：无论游戏进行多少轮，内存占用始终为O(k)，k为蓄水池容量
2. 统计无偏：蓄水池抽样保证每个反应时间被选中的概率相等，统计结果具有代表性
3. 实时响应：双堆结构使中位数查询为O(1)，支持每轮游戏结束后的即时难度调整
4. 鲁棒度量：引入MAD和IQR替代标准差，对异常反应时间（如玩家分神）更具鲁棒性

该框架可扩展至任何需要”流式数据统计+动态决策”的游戏AI场景，如音乐节奏游戏的判定窗口自适应、赛车游戏的AI速度匹配等。