斯卡拉概率优先级队列 - 优先

我有个优先级队列，其中包含多个任务，以数字非唯一的优先级每个任务有几率出列，如下所示：斯卡拉概率优先级队列 - 优先

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

斯卡拉概率优先级队列 - 优先

回答

相关问题