我正在尝试实现一种“加权队列提取器”，以从具有不同优先级的不同队列中提取元素。我只需选择要从中获取元素的队列。
假设我有 n 个队列，每个队列都有一个优先级。优先级指示相对于其他元素需要从队列中提取多少元素。例如，如果我有 n=2 个队列，其中一个 (A) 的优先级为 5，另一个 (B) 的优先级为 10，那么在从队列中提取 15 次之后，我应该从队列 A 中取出 5 个元素，队列 B 中的 10 个。提取应该统一进行。
举个例子，我应该从队列 B 中提取 2 个元素，然后从队列 A 中提取 1 个元素，依此类推。如果我有 3 个队列 — A、B、C — 优先级分别为 1、3、6，则每 10 次提取应从队列 A 中生成 1 个元素，从队列 B 中生成 3 个元素，从队列 C 中生成 6 个元素。例如，按以下顺序： C B C A C B C C B C（所以我从 A 得到 1，从 B 得到 3，从 C 得到 6）。
我的想法是将每个队列想象成一个跑步者。在此场景中，跑步者 A 速度较慢，以 1 步/秒的速度移动，跑步者 B 的移动速度为 3 秒/秒，跑步者 C 的移动速度为 6 秒/秒。到达终点线的跑步者首先向后退固定距离，A+B+C 步（在本例中，1+3+6=10）。其他人继续按照自己的步调，根据自己的速度走完距离。每次我送某人回来时，我都会从该队列中提取一个元素。考虑这个例子：
A B C
1 3 6 --> Who is the largest posotive? 6 (i.e., C). I move it back by 10 steps.
1 3 -4 --> Who is the largest positive? 3 (i.e., B). I move it back by 10 steps. C is negative, so I advance it at its pace (6).
1 -7 2 --> Who is the largest positive? 2 (i.e., C), and I move it back by 10 steps. B is negative, so I advance it at its pace (3).
1 -4 -8 --> Who is the largest positive? 1 (i.e., A), and I move it back by 10 steps; B and C are negative, so I advance them at their respective paces.
-9 -1 -2 --> No positive values... I advance them without extracting anyone.
-8 2 4 --> I take the largest positive, the 4 (i.e., C), and move them back by 10 steps, etcetera.
-7 2 -6 --> I get the 2 (aka B) and move it back 10 steps, then I advance the others at their respective paces
-6 -8 0 --> skip
-5 -5 6 --> I get the 6 (aka C) and move it back 10 steps, and let the others run at their pace
-4 -2 -4 --> skip
-3 1 2 --> I get the 2 (aka C) and move him back
-2 1 -8 --> I get 1 (aka B) and move him back
-1 -9 -2 --> skip
0 -6 4 --> I get 4 (aka C) and move him back
因此，经过 10,000 次迭代后，我期望从 A 组中提取 1000 个元素，从 B 组中提取 3000 个元素，从 C 组中提取 6000 个元素。但是，我获得了 1346、2885、5769。我怀疑算法中存在错误，但我'我不确定它可能在哪里或是什么。
这是我写的课程：
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]));
}
}
}
可能，已知前 10 次提取，我可以重复它们......但我更喜欢修复算法。
任何提示将不胜感激。 :)
PS - 我还认为我可以创建一个函数 f(k)，给定提取编号，报告确切的队列元素（因此，它是 O(1) 并且不需要算法）。在前面的示例中，f(0)=2（又名 C）、f(5)=1（又名 B）、f(3)=0（又名 A）。
我发现算法问题。 每当我找到一个正数时，我就必须提取该元素并减少其相关优先级的值。如果我没有正元素，我必须将队列优先级添加到该值中。示例：
A B C
---------
1 3 6 -> A
-9 3 6 -> B
-9 -7 6 -> C
-9 -7 -4
-8 -4 2 -> C
-8 -4 -8
-7 -1 -2
-6 2 4 -> B
-6 -8 4 -> C
-6 -8 -6
-5 -5 0 -> C
-5 -5 -10
-4 -2 -4
-4 1 2 -> B
-4 -9 2 -> C
-4 -9 -8
-3 -6 -2
-2 -3 4 -> C
-2 -3 -6
-1 0 0 -> B
-1 -10 0 -> C
-1 -10 -10
0 -7 -3 -> A
etc etc
修正算法，结果正确：
public int getIndex() {
while (true) {
for (int i = 0; i < values.length; i++) {
// any positive value?
if (values[i] >= 0) {
values[i] -= total;
return i;
}
}
// no positive values here
for (int i = 0; i < values.length; i++) {
values[i] += priorities[i];
}
}
}