CODEWITHSUNDEEP
scaladata-structurespriority-queue
Romi Kuntsman
Romi Kuntsman

Reputation: 482

Scala Probabilistic Priority Queue - dequeue with probability by priority

I have a priority queue, which holds several tasks, each task with a numeric non-unique priority, as follows:

import scala.collection.mutable

class Task(val name: String, val priority: Int) {
  override def toString = s"Task(name=$name, priority=$priority)"
}

val task_a = new Task("a", 5)
val task_b = new Task("b", 1)
val task_c = new Task("c", 5)

val pq: mutable.PriorityQueue[Task] =
    new mutable.PriorityQueue()(Ordering.by(_.priority))

pq.enqueue(task_a)
pq.enqueue(task_b)
pq.enqueue(task_c)

I want to get the next task:

pq.dequeue()

But this way, I'll always get back task a, even though there's also task c with the same priority.

  1. How to get one of the items with the highest priority randomly? That is to get either task a or task c, with 50/50 chance.
  2. How to get any of the items randomly, with probability according to priority? That is to get 45% task a, 10% task b, and 45% task c.

Upvotes: 2

Views: 213

Answers (1)

Daniel Spiewak
Daniel Spiewak

Reputation: 55123

This should be a good starting point:

abstract class ProbPriorityQueue[V] {
  protected type K
  protected implicit def ord: Ordering[K]
  protected val impl: SortedMap[K, Set[V]]
  protected val priority: V => K

  def isEmpty: Boolean = impl.isEmpty

  def dequeue: Option[(V, ProbPriorityQueue[V])] = {
    if (isEmpty) {
      None
    } else {
      // I wish Scala allowed us to collapse these operations...
      val k = impl.lastKey
      val s = impl(k)

      val v = s.head
      val s2 = s - v

      val impl2 = if (s2.isEmpty)
        impl - k
      else
        impl.updated(k, s2)

      Some((v, ProbPriorityQueue.create(impl2, priority)))
    }
  }
}

object ProbPriorityQueue {

  def apply[K: Ordering, V](vs: V*)(priority: V => K): ProbPriorityQueue = {
    val impl = vs.foldLeft(SortedMap[K, Set[V]]()) {
      case (acc, v) =>
        val k = priority(v)

        acc get k map { s => acc.updated(k, s + v) } getOrElse (acc + (k -> Set(v)))
    }

    create(impl, priority)
  }

  private def create[K0:, V](impl0: SortedMap[K0, Set[V]], priority0: V => K0)(implicit ord0: Ordering[K0]): ProbPriorityQueue[V] =
    new ProbPriorityQueue[V] {
      type K = K0
      def ord = ord0
      val impl = impl0
      val priority = priority0
    }
}

I didn't implement the select function, which would produce a value with weighted probability, but that shouldn't be too hard to do. In order to implement that function, you will need an additional mapping function (similar to priority) which has type K => Double, where Double is the probability weight attached to a particular key bucket. This makes everything somewhat messier, so it didn't seem worth bothering about.

Also this seems like a remarkably specific set of requirements. You're either doing a very interested bit of distributed scheduling, or homework.

Upvotes: 1

Related Questions