斯卡拉概率優先級隊列 - 優先

我有個優先級隊列，其中包含多個任務，以數字非唯一的優先級每個任務有機率出列，如下所示：斯卡拉概率優先級隊列 - 優先

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具有相同的優先級。

如何隨機獲取其中一個具有最高優先級的項目？那是得到任務a或任務c，有50/50的機會。
如何隨機獲取任何項目，並根據優先級的概率？那是得到45％的任務a，10％的任務b和45％的任務c。

來源

2016-11-28 Romi Kuntsman

您可以根據輪盤選擇算法訂購優先級 –

我不知道Scala，但在許多語言中，我確實知道我會爲優先級實現一個自定義比較器，將該選項隨機化爲二級排序標準否則這些優先事項將被視爲平等。 – pjs

這看起來很有趣https://www.codatlas.com/github.com/apache/kafka/HEAD/core/src/main/scala/kafka/utils/timer/TimingWheel.scala –

這應該是一個很好的起點：

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

我沒有實現select功能，這將產生加權概率值，但應該不會太難的事。爲了實現該功能，您需要額外的映射功能（類似於priority），其類型爲K => Double，其中Double是附加到特定密鑰桶的概率權重。這使得一切都變得更加混亂，所以它似乎不值得打擾。

此外，這似乎是一組非常特殊的要求。你要麼對分佈式調度或作業感興趣。

來源

2016-11-29 08:30:12

斯卡拉概率優先級隊列 - 優先

回答

相關問題