Re: Random weighted selection...
Tom,
Thanks for writing.
On May 10, 9:27 am, Tom Anderson <t...@urchin.earth.li> wrote:
interface Job extends Runnable {
public int priority();
}
Then:
Job pickJob(List<Job> jobs, Random rnd) {
int totalPriority = 0;
for (Job job: jobs) totalPriority += job.priority();
int index = rnd.nextInt(totalPriority);
for (Job job: jobs) {
index -= job.priority();
if (index < 0) return job;
}
assert false; return null; // should be unreachable!
}
This seems to be what Seamus suggested, no?
Another approach would be to put the jobs in priority order, then pick
from the list in such a way that earlier items are more likely to be
picked.
This is exactly the nature of my initial post. A weighted random
choice, or choices. Well, as long as I understand your use of
"earlier".
You can do this easily by walking the list, and picking the
current item with a given fixed probability. If that was 50%, then you'd
have a 50% chance of picking the first item, 25% of picking the second,
12.5% of picking the third, etc. This doesn't assign equal probability to
jobs of equal priority, but if you're careful, it does assign greater
probability to jobs submitted earlier, which could be an advantage.
I think the priority re-assessor would take care of all that. THe
choice is what is important.
class QueuedJob implements Comparable<QueuedJob> {
public final Job job;
public final int serialNumber;
public QueuedJob(Job job, int serialNumber) {
this.job = job
this.serialNumber = serialNumber;
}
public int compareTo(QueuedJob that) {
int difference = -compare(this.job.prio=
rity(), that.job.priority());
if (difference == 0) difference = c=
ompare(this.serialNumber, that.serialNumber);
return difference;
}
private int compare(Integer a, Integer b) {
return a.compareto(b);
}
public boolean equals(Object obj) {
if ((obj == null) || !(obj instanceof=
QueuedJob)) return false;
QueuedJob that = (QueuedJob)obj;
return (this.job.equals(that.job)) && (th=
is.serialNumber == that.serialNumber);
}
}
class JobQueue {
private SortedSet<QueuedJob> qjobs = new TreeSet<Queued=
Job>();
private int counter = 0;
private Random rnd = new Random();
private float p = 1.0 / 3.0; // or whatever
public void enqueue(Job job) {
qjobs.add(new QueuedJob(job, counter));
++counter; // ignore obvious problem with=
wrapping
}
public Job pop() {
Iterator<QueuedJob> it = qjobs.iterator=
();
while (it.hasNext()) {
if (rnd.nextFloat() <= =
p) return pop(it);
}
// might not picky any of the above, so:
return pop(qjobs.iterator());
}
private Job pop(Iterator<QueuedJob> it) {
Job job = it.next().job;
it.remove();
remove job;
}
}
Tom, is there an alternative to the costly and time consuming
iteration? This was not part of what I had recalled in the initial
post in this thread, but...
What is the jobs were in an ArrayList, or other Collection(), and the
basic parameters were known about the list/collection/array.
You know what is easy/fast to learn:
The total # of elements
The highest priority
The lowest priority
How many elements will be selected (pulled out of the array)
Why couldn't you do _one_ iteration, and make your choice as to
whether to include an item at the same time that item comes up in the
iteration? Would sorting/ordering even be necessary? Without testing,
that would seem to be the least task intensive way to make a selection-
even if not a random weighted one.
Hmm... Your example made me think of this. Not sure if it holds water,
though! :)
Thanks!
pat
:)