Re: Random weighted selection...

On Sat, 9 May 2009, Pat wrote:


I can see how to do it - it's pretty trivial - but i wouldn'd describe it
as elegant. If your jobs looks like:

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!
}

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. 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.

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.priority(), that.job.priority());
  if (difference == 0) difference = compare(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)) && (this.serialNumber == that.serialNumber);
  }
}

class JobQueue {
  private SortedSet<QueuedJob> qjobs = new TreeSet<QueuedJob>();
  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

--
I think the Vengaboys compliment his dark visions splendidly well. -- Mark
Watson, on 'Do you listen to particular music when reading lovecraft?'