I'm trying to implement a kind of 'weighted queue extractor' to extract elements from different queues having different priorities. I just have to choose the queue I've to get an element from.
Let's say I have n queues, each with a priority. Priority indicates how many elements need to be extracted from the queue relative to the others. For instance, if I have n=2 queues where one (A) has a priority of 5 and the other (B) has a priority of 10, after 15 extractions from the queues, I should have taken out 5 elements from queue A and 10 from queue B. The extractions should occur uniformly.
As an example, I should extract 2 elements from queue B, then one element from queue A, and so forth. If I have 3 queues — A, B, C — with priorities 1, 3, 6, then every 10 extractions should yield 1 element from queue A, 3 from queue B, and 6 from queue C. For example, in this sequence: C B C A C B C C B C (so I got 1 from A, 3 from B, 6 from C).
My idea is to envision each queue as a runner. In this scenario, runner A is slow, moving at 1 step/sec, runner B at 3 s/s, and runner C at 6 s/s. The runner reaching the finish line first goes back a fixed distance, A+B+C steps (in this case, 1+3+6=10). The others continue at their own pace, covering the distance according to their speed. Every time I send someone back, I extract an element from that queue. Consider this example:
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
So, after 10,000 iterations, I expect to have extracted 1000 elements from group A, 3000 from group B, and 6000 from group C. However, I obtained 1346, 2885, 5769. I suspect an error in the algorithm, but I'm unsure where or what it might be.
This is the class I wrote:
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]));
}
}
}
Probably, known the first 10 extractions, I can just repeat them... but I prefer to fix the algorithm.
Any hints would be appreciated. :)
PS - I also suppose that I could create a function f(k) that, given an extraction number, reports the exact queue element (so, it's O(1) and it doesn't need an algorithm). In the previosu example, f(0)=2 (aka C), f(5)=1 (aka B), f(3)=0 (aka A).
I found the algorithm issue. Whenever I find a positive number, I have to extract that element and decrease its value of the related priority. If I don't have positive elements, I have to add the queue priority to the value. Example:
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
Fixed the algorithm, the result is correct:
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];
}
}
}