加权队列元素提取算法修正求助：结果偏离预期问题

问题背景 #

我需要实现一个加权队列提取器，核心目标是按优先级比例从不同队列中提取元素，且元素分布需均匀：

• 示例1：2个队列A(优先级5)、B(优先级10)，15次提取后需从A取5个、B取10个，提取序列要均匀分布
• 示例2：3个队列A(1)、B(3)、C(6)，每10次提取需得到1个A、3个B、6个C，比如预期序列：C B C A C B C C B C

我采用跑步者模型实现：将每个队列视为跑步者，速度等于对应优先级，最先到达终点的跑步者退回总优先级（所有队列优先级之和）步数，退回时从对应队列提取元素。但测试10000次迭代后，预期提取量为A=1000、B=3000、C=6000，实际得到1346、2885、5769，结果严重偏离预期。

当前Java实现代码：

import java.util.Arrays;

public class FairQueue
{

    private int[] values;
    private int[] priorities;
    private int total = 0;

    public FairQueue(int[] priorities, int[] values)
    {
        this.values = values;
        this.priorities = priorities;
        for (int priority : priorities) {
            total += priority;
        }
        if (this.values == null) {
            this.values = Arrays.copyOf(priorities, priorities.length);
        }
    }

    public int getIndex()
    {
        int toret = -1;
        while (toret == -1) {
            for (int i = 0; i < values.length; i++) {
                if (values[i] <= 0) {
                    values[i] += priorities[i];
                } else { // got positive value
                    if (toret == -1) {
                        toret = i;
                    } else { // if I find a better positive
                        if (values[toret] < values[i]) {
                            // should it run? 
                            // values[toret] += priorities[toret];
                            toret = i;
                        }
                    }
                }

            }
        }
        // go back!
        values[toret] -= total;
        return toret;
    }

    int getTotal()
    {
        return total;
    }

    private static final int ITERATIONS = 1000;
    // with { 1,2,3,4 } it works fine!
    // private static final int[] PRIORITIES = new int[] { 1, 2, 3, 4 };
    private static final int[] PRIORITIES = new int[] { 1, 3, 6 };

    public static void main(String[] args)
    {

        FairQueue f = new FairQueue(PRIORITIES, null);
        int[] res = new int[PRIORITIES.length];
        for (int i = 0; i < ITERATIONS * f.getTotal(); i++) {
            res[f.getIndex()]++;
        }
        for (int i = 0; i < PRIORITIES.length; i++) {
            System.out.println(String.format("p[%d]=%d: %d elemn (%.2f)", i, PRIORITIES[i], res[i],
                    (1.0 * res[i]) / PRIORITIES[i]));
        }


    }
}

问题排查 #

你的跑步者模型核心逻辑完全错误，导致提取比例偏离：

1. 选择逻辑搞反：跑步者模型的正确逻辑是选择当前“位置”（values值）最小的队列（代表最先到达终点），但你当前的逻辑是选择values最大的队列，直接颠倒了选择方向。
2. 位置更新逻辑混乱：你在遍历过程中边检查边更新<=0的values，这种局部更新会破坏跑步者前进的同步性，导致队列的位置计算错误。

算法修正方案 #

修正后的跑步者模型需保证所有跑步者同步前进，再选择位置最小的队列，具体步骤：

1. 每次提取前，所有队列的values加上对应优先级（模拟跑步者同步前进）
2. 找到values最小的队列（最先到达终点）
3. 将该队列的values减去总优先级（退回起点）
4. 返回该队列索引

修正后的代码 #

构造函数修正

初始化values为全0，保证所有跑步者从同一起点出发：

public FairQueue(int[] priorities, int[] values) {
    this.priorities = priorities;
    for (int priority : priorities) {
        total += priority;
    }
    this.values = (values == null) ? new int[priorities.length] : values;
}

getIndex()方法修正

public int getIndex() {
    // 所有跑步者同步前进
    for (int i = 0; i < values.length; i++) {
        values[i] += priorities[i];
    }
    // 找到当前位置最小的队列
    int minIndex = 0;
    for (int i = 1; i < values.length; i++) {
        if (values[i] < values[minIndex]) {
            minIndex = i;
        }
    }
    // 退回总优先级步数
    values[minIndex] -= total;
    return minIndex;
}

测试修正后的代码，10000次迭代后会得到符合预期的提取比例：A≈1000、B≈3000、C≈6000，且提取序列均匀分布。

O(1)提取函数f(k)实现思路 #

要实现根据提取次数k直接返回队列索引的O(1)函数，可利用数学映射模拟跑步者模型的等价逻辑：

1. 对于第k次提取（从0开始计数），计算每个队列i的(k+1)*priorities[i] / total的小数部分
2. 选择小数部分最小的队列（对应跑步者模型中位置最小的队列）

实现代码 #

public static int getIndexO1(int k, int[] priorities) {
    int total = 0;
    for (int p : priorities) {
        total += p;
    }
    double minFraction = Double.MAX_VALUE;
    int resultIndex = 0;
    for (int i = 0; i < priorities.length; i++) {
        double ratio = (double)(k + 1) * priorities[i] / total;
        double fraction = ratio - Math.floor(ratio);
        if (fraction < minFraction) {
            minFraction = fraction;
            resultIndex = i;
        }
    }
    return resultIndex;
}

这个函数无需维护状态，直接通过数学计算返回对应队列索引，保证提取比例和分布均匀性与修正后的跑步者模型一致。

内容的提问来源于stack exchange，提问作者Sampisa