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 に答える