scala - 优先级队列中的不同元素
问题描述
我正在使用这个有界优先级队列的实现,https://gist.github.com/ryanlecompte/5746241,它工作得很好。但是,我希望这个队列不包含任何具有相同排序“ord”的元素。我怎样才能做到这一点?
我试图通过给出函数 lteq 而不是 lt 来更新 MaybeReplaceLowest 函数。
private def maybeReplaceLowest(a: A) {
if (ord.lteq(a, head)) {
dequeue()
super.+=(a)
}
}
但我认为它不起作用,因为与新元素具有相同顺序的元素可能不在头部。有什么办法可以快速解决这个问题?
非常感谢。
解决方案
Scala PriorityQueue是使用Array
. 这对于查找操作非常低效,您需要为每个插入执行此操作(以检查该元素是否已存在于队列中。
对于TreeSet是查找和有序存储的理想选择。但由于这是一个密封类(scala-2.12.8),我创建了复合类
import scala.collection.mutable
class PrioritySet[A](val maxSize:Int)(implicit ordering:Ordering[A]) {
var set = mutable.TreeSet[A]()(ordering)
private def removeAdditional(): this.type = {
val additionalElements = set.size - maxSize
if( additionalElements > 0) { set = set.drop(additionalElements) }
this
}
def +(elem: A): this.type = {
set += elem
removeAdditional()
}
def ++=(elem: A, elements: A*) : this.type = {
set += elem ++= elements
removeAdditional()
}
override def toString = this.getClass.getName + set.mkString("(", ", ", ")")
}
这可以用作
>>> val set = new PrioritySet[Int](4)
>>> set ++=(1000,3,42,2,5, 1,2,4, 100)
>>> println(set)
PrioritySet(5, 42, 100, 1000)