Scalaの確率プライオリティキュー - 優先

Question

によって確率でデキュー次のように私は、いくつかのタスクを保持しているプラ​​イオリティキュー、数値が非一意のプライオリティを持つ各タスクを持っている：

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) 

私は次を取得したいですタスク：

pq.dequeue() 

しかし、この方法で、私はいつもタスクCが同じ優先順位でもありますにもかかわらず、バックタスクを取得します。

1. 優先度の高いアイテムをランダムに取得するにはどうすればよいですか？それは50/50のチャンスで、タスクaまたはタスクcのいずれかを取得することです。
2. どのように優先順位に従って確率でアイテムをランダムに取得するのですか？それは45％のタスクa、10％のタスクb、45％のタスクcを得ることです。

Answer 1

これは良い出発点でなければなりません：私は、加重確率で値を生成するた、select機能を実装していませんでしたが、それを行うにはあまりにも難しいことではありません

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

。その機能を実装するには、タイプK => Doubleを持つ追加のマッピング関数（priorityに似ています）が必要です。ここで、Doubleは特定のキーバケットに接続された確率の重みです。これはすべてのことをやや難しくしているので、気にする価値はないようです。

また、これは非常に特定の要件のセットのようです。分散スケジューリングや宿題に非常に興味があります。