2

我已经实现了从头部提取项目的例程，更新它的优先级并使用这样的非阻塞方法将其放回队列（使用 AtomicReference）

def head(): Entry = {
  def takeAndUpdate(e: Entry, success: Boolean): Entry = {
    if (success) {
      return e
    }
    val oldQueue = queueReference.get()
    val newQueue = oldQueue.clone()
    val item = newQueue.dequeue().increase()
    newQueue += item
    takeAndUpdate(item.e, queueReference.compareAndSet(oldQueue, newQueue))
  }
  takeAndUpdate(null, false)
}

现在我需要找出队列中的任意条目，更改它的优先级并将其放回队列。似乎 PriorityQueue 不支持这一点，那么我应该使用哪个类来完成所需的行为？

它与更改优先级队列中项目的优先级有关

4

1 回答 1

2

使用不可变树图 ( immutable.TreeMap) 来完成此操作。您必须以某种方式找到您想要的条目 - 最好的方法是将Key用于查找条目的信息部分 ( ) 与键相关联，以及您希望返回的实际条目与映射中的值（称之为Entry）。

queueReference用重命名treeReference。在您创建集合的代码部分，使用immutable.TreeMap[Key, Entry](<list of elements>).

然后像这样修改代码：

def updateKey(k: Key) {
  @annotation.tailrec def update(): (Key, Entry) = {
    val oldTree = treeReference.get()
    val entry = oldTree(k)
    val newPair = modifyHoweverYouWish(k, entry)
    val newTree = (oldTree - k) + newPair
    if (treeReference.compareAndSet(oldTree, newTree)) newPair
    else update()
  }
  update()
}

如果compareAndSet失败，您必须像在源代码中那样重复。最好@tailrec如上所示使用，以确保函数是尾递归并防止潜在的堆栈溢出。

或者，您可以使用immutable.TreeSet- 如果您知道对Entry对象的确切引用，则可以使用它通过-如上所述删除元素，然后在调用increase(). 代码几乎相同。

于 2012-08-28T11:05:36.417 回答