一、项目背景详细介绍

在一些场景中，如抽奖系统、游戏掉落、广告推荐等，需要按照预设的不等概率分布随机选择元素，而不仅仅是均匀分布。比如有三个奖品 A、B、C，权重分别为 50%、30%、20%，希望抽奖时 A 被选中的概率是 0.5、B 是 0.3、C 是 0.2。实现“按概率生成随机数”算法，是对基础随机数生成的扩展，也是了解如何将权重映射到区间并高效查询的关键。

---

二、项目需求详细介绍

1. 输入权重数组

   • 输入一个正数数组 weights[]，长度为 n，表示 n 个元素对应的权重，可以是整数或浮点数。

2. 初始化预处理

   • 提供方法 void init(double[] weights)，对权重数组进行预处理，将其转换为可快速查询的结构（如前缀和、别名法表等）。

3. 随机生成索引

   • 提供方法 int randomIndex()，返回一个 [0, n) 范围内的整数 i，使得 P(i) = weights[i] / sum(weights)。

4. 性能要求

   • init 时间可为 O(n) 或 O(n log n)；

   • randomIndex 必须在 O(log n) 或 O(1) 内完成，以满足高并发场景。

5. 两种实现方案

   • 前缀和二分查找：O(n) 初始化，O(log n) 查询；

   • Vose 别名法（Alias Method）：O(n) 初始化，O(1) 查询。

6. 命令行工具模式

   • 提供 Main 类，解析命令行参数：

     • --weights w1,w2,…,wn：权重列表；

     • --method prefix|alias：选择实现；

     • --trials m：抽样次数，统计各索引出现频率并输出。

7. 单元测试覆盖

   • 使用 JUnit 5 对两种算法测试：小规模权重、极端权重（含零权重）、随机分布，验证分布近似正确。

8. 可扩展性

   • 支持动态更新权重（如在线加权），可选重建或增量维护别名表。

---

三、相关技术详细介绍

1. Java 随机数

   • java.util.Random 或 ThreadLocalRandom 生成基础均匀随机 [0,1)；

2. 前缀和 + 二分查找

   • 构建累加和数组 prefix[i] = sum(weights[0..i])；

   • 生成 r = uniform(0, total)，在 prefix 上用 Arrays.binarySearch 或手写二分找最小 i 满足 prefix[i] > r。

3. 别名法（Alias Method）

   • 维持两个大小为 n 的数组：alias[] 和 prob[]，初始化时将权重映射到等概率区间，并分配别名；

   • 查询时生成 i = uniformInt(0, n), u = uniform(0,1)，若 u < prob[i] 返回 i，否则返回 alias[i]。

4. 命令行解析

   • Apache Commons CLI：解析 --weights、--method、--trials 参数与帮助信息。

5. 测试与统计

   • JUnit 5：测试算法正确性；

   • 简易统计打印抽样结果，与理论概率比较。

---

四、实现思路详细介绍

1. 工具类 WeightedRandom

   • 私有构造与两种静态内部实现：PrefixSum 和 AliasMethod，均实现接口：

public interface Sampler {
    int next();
}

• • init 返回 Sampler 实例。

• 前缀和实现

  • 构造时计算 double[] prefix 与 total；

  • next()：生成 r = random.nextDouble() * total，return Arrays.binarySearch 转换后或手写。

• 别名法实现

  • 构造时按经典 Vose 算法生成 prob[] 与 alias[]；

  • next()：int i = random.nextInt(n)，if random.nextDouble() < prob[i] return i; else return alias[i];

• 命令行入口 Main

  • 解析并拆分字符串参数到 double[] weights；

  • 根据 --method 选择实现，构造相应 Sampler；

  • 执行 trials 次 next()，统计结果数组并打印相对频率。

• 单元测试

  • 对小型 weights={1,2,3} 抽大样本统计，验证近似比例 1:2:3；

  • 测试含零权重元素始终不被抽中；

  • 边界测试 weights 全相同或仅一个非零权重。

五、完整实现代码

// 文件：src/main/java/com/example/random/WeightedRandom.java
package com.example.random;

import java.util.Arrays;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * WeightedRandom 提供按权重随机抽取接口
 */
public class WeightedRandom {

    public interface Sampler {
        int next();
    }

    // 前缀和实现
    public static class PrefixSampler implements Sampler {
        private final double[] prefix;
        private final double total;

        public PrefixSampler(double[] weights) {
            int n = weights.length;
            prefix = new double[n];
            double sum = 0;
            for (int i = 0; i < n; i++) {
                if (weights[i] < 0) throw new IllegalArgumentException("权重不能为负");
                sum += weights[i];
                prefix[i] = sum;
            }
            if (sum <= 0) throw new IllegalArgumentException("权重之和必须大于 0");
            total = sum;
        }

        @Override
        public int next() {
            double r = ThreadLocalRandom.current().nextDouble() * total;
            int idx = Arrays.binarySearch(prefix, r);
            if (idx >= 0) return idx;
            return -idx - 1;
        }
    }

    // 别名法实现（Vose 别名法）
    public static class AliasSampler implements Sampler {
        private final int[] alias;
        private final double[] prob;
        private final int n;

        public AliasSampler(double[] weights) {
            n = weights.length;
            double sum = 0;
            for (double w : weights) {
                if (w < 0) throw new IllegalArgumentException("权重不能为负");
                sum += w;
            }
            if (sum <= 0) throw new IllegalArgumentException("权重之和必须大于 0");

            // 归一化到 n 份
            double[] norm = new double[n];
            for (int i = 0; i < n; i++) norm[i] = weights[i] * n / sum;

            alias = new int[n];
            prob = new double[n];
            Deque<Integer> small = new ArrayDeque<>();
            Deque<Integer> large = new ArrayDeque<>();
            for (int i = 0; i < n; i++) {
                if (norm[i] < 1.0) small.add(i);
                else large.add(i);
            }

            while (!small.isEmpty() && !large.isEmpty()) {
                int l = small.removeLast();
                int g = large.removeLast();
                prob[l] = norm[l];
                alias[l] = g;
                norm[g] = norm[g] + norm[l] - 1;
                if (norm[g] < 1.0) small.add(g);
                else large.add(g);
            }
            // 剩余
            while (!large.isEmpty()) {
                prob[large.removeLast()] = 1.0;
            }
            while (!small.isEmpty()) {
                prob[small.removeLast()] = 1.0;
            }
        }

        @Override
        public int next() {
            int i = ThreadLocalRandom.current().nextInt(n);
            double u = ThreadLocalRandom.current().nextDouble();
            return u < prob[i] ? i : alias[i];
        }
    }

    /**
     * 工厂方法，根据 method 返回不同 Sampler
     * @param weights 权重数组
     * @param method  "prefix" 或 "alias"
     */
    public static Sampler create(double[] weights, String method) {
        if ("alias".equalsIgnoreCase(method)) {
            return new AliasSampler(weights);
        }
        return new PrefixSampler(weights);
    }
}

// 文件：src/main/java/com/example/cli/Main.java
package com.example.cli;

import com.example.random.WeightedRandom;
import com.example.random.WeightedRandom.Sampler;
import org.apache.commons.cli.*;

import java.util.Arrays;

/**
 * Main 类演示按权重抽样并统计频率
 */
public class Main {
    public static void main(String[] args) {
        Options opts = new Options();
        opts.addOption(null, "weights", true, "权重列表，例如: --weights 50,30,20");
        opts.addOption(null, "method",  true, "实现方法: prefix|alias");
        opts.addOption(null, "trials",  true, "抽样次数，默认为1000000");

        HelpFormatter hf = new HelpFormatter();
        CommandLineParser parser = new DefaultParser();
        try {
            CommandLine cmd = parser.parse(opts, args);
            String wstr = cmd.getOptionValue("weights");
            String method = cmd.getOptionValue("method", "prefix");
            int trials = Integer.parseInt(cmd.getOptionValue("trials", "1000000"));

            if (wstr == null) {
                throw new ParseException("必须指定 --weights");
            }
            double[] weights = Arrays.stream(wstr.split(","))
                                     .mapToDouble(Double::parseDouble)
                                     .toArray();

            Sampler sampler = WeightedRandom.create(weights, method);
            long[] counts = new long[weights.length];
            for (int i = 0; i < trials; i++) {
                counts[sampler.next()]++;
            }
            System.out.println("实验次数: " + trials);
            for (int i = 0; i < counts.length; i++) {
                System.out.printf("索引 %d: 理论=%.4f, 实测=%.4f%n",
                    i,
                    weights[i] / Arrays.stream(weights).sum(),
                    counts[i] / (double)trials
                );
            }
        } catch (ParseException pe) {
            System.err.println("参数解析错误: " + pe.getMessage());
            hf.printHelp("java -jar weighted-random.jar", opts);
        }
    }
}

// 文件：src/test/java/com/example/random/WeightedRandomTest.java
package com.example.random;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

import java.util.stream.IntStream;

/**
 * WeightedRandom 单元测试
 */
public class WeightedRandomTest {

    @Test
    void testPrefixSamplerDistribution() {
        double[] w = {1,2,3};
        WeightedRandom.Sampler s = new WeightedRandom.PrefixSampler(w);
        int trials = 300_000;
        long[] cnt = new long[3];
        for (int i = 0; i < trials; i++) cnt[s.next()]++;
        double p0 = cnt[0]/(double)trials,
               p1 = cnt[1]/(double)trials,
               p2 = cnt[2]/(double)trials;
        assertTrue(Math.abs(p0-1/6.0) < 0.01);
        assertTrue(Math.abs(p1-2/6.0) < 0.01);
        assertTrue(Math.abs(p2-3/6.0) < 0.01);
    }

    @Test
    void testAliasSamplerDistribution() {
        double[] w = {5,0,5};
        WeightedRandom.Sampler s = new WeightedRandom.AliasSampler(w);
        int trials = 200_000;
        long[] cnt = new long[3];
        for (int i = 0; i < trials; i++) cnt[s.next()]++;
        assertEquals(0, cnt[1]);
        assertTrue(cnt[0] > 0);
        assertTrue(cnt[2] > 0);
    }

    @Test
    void testInvalidWeights() {
        assertThrows(IllegalArgumentException.class,
            () -> new WeightedRandom.PrefixSampler(new double[]{0,0}));
        assertThrows(IllegalArgumentException.class,
            () -> new WeightedRandom.AliasSampler(new double[]{-1,1}));
    }
}

六、代码详细解读

• WeightedRandom.PrefixSampler

  • 构造时计算累加前缀 prefix[i] = sum(weights[0..i]) 和总和 total；

  • next() 生成 [0, total) 随机数 r，在 prefix 数组上二分查找最小索引 i 使得 prefix[i] > r。

• WeightedRandom.AliasSampler

  • 构造时按 Vose 别名法准备大小为 n 的 prob[] 和 alias[]：

    1. 归一化权重为均匀基准 norm[i] = weight[i]*n/sum；

    2. 将 norm 分成小于 1 和大于等于 1 两组，配对填充表；

  • next() 随机选索引 i = uniformInt(0,n)，再生成 u = uniform(0,1)，若 u < prob[i] 返回 i，否则返回 alias[i]。

• Main

  • 解析 --weights、--method、--trials 参数；

  • 构造对应 Sampler 并进行 trials 次抽样，统计计数后打印理论概率与实测概率对比。

• 测试

  • testPrefixSamplerDistribution：对 {1,2,3} 进行 30 万次抽样，验证实测概率在 ±1% 以内；

  • testAliasSamplerDistribution：对包含零权重的 {5,0,5} 抽样，验证中间索引永不出现；

  • testInvalidWeights：非法权重（全为 0 或含负数）构造应抛 IllegalArgumentException。

---

七、项目详细总结

本项目实现了两种按权重随机抽样算法：

• 前缀和+二分：初始化 O(n)，查询 O(log n)，实现简单。

• 别名法：初始化 O(n)，查询 O(1)，适合超高并发场景。

通过对比实测概率和理论概率，验证了两种算法的正确性与性能差异。项目结构清晰，接口统一，易于在实际系统中集成。

---

八、项目常见问题及解答

Q1：权重全为零或负数怎么办？
应在初始化时校验抛异常，权重之和必须大于零，且各权重非负。

Q2：前缀法和别名法各适用场景？

• 前缀法实现简单、无需额外空间（O(n) 前缀数组）即可，适合 n 较小或查询频率不高的场景；

• 别名法初始化复杂，但查询 O(1)，适合大规模元素和高并发查询。

Q3：如何动态更新权重？

• 对于前缀法，需重新构建前缀数组；

• 对于别名法，增删需重建别名表或使用增量算法（复杂）。

Q4：浮点精度影响结果吗？
若权重之和或前缀和非常大或非常小，浮点运算误差可能影响二分索引，可考虑使用 BigDecimal 或缩放权重。

Q5：如何扩展到多维或分层抽样？
可将分层视为两级权重抽样，先按大类权重抽取，再在子类中再次调用相同算法。

---

九、扩展方向与性能优化

1. 并行初始化
   利用并行流构建前缀数组或别名表，提高构造速度。

2. 基准测试
   使用 JMH 对不同 n、不同权重分布、不同算法进行性能对比。

3. 固定点运算
   用整型前缀和和随机整数避免浮点误差，提高精度。

4. 内存压缩
   对大规模元素，将 alias 和 prob 压缩至更紧凑的数据结构。

5. 多语言互操作
   提供 REST 服务或 JNI 接口，供 Python、Go 等语言调用。