問題タブ [priority-queue]

私はいくつかのオブジェクトのpriority_queueを持っています:

ときどき、オブジェクトの 1 つの優先度が変わることがあります。効率的な方法でキュー内のそのオブジェクトの優先度を更新できる必要があります。現在、私はこの方法を使用していますが、これは機能しますが非効率的です:

当時はちょっと急いでいたので、この方法で実装しました。これが、問題なく動作することを確認できる最速の方法でした。ただし、これよりも良い方法があるはずです。本当に私が欲しいのは、次のいずれかの方法です。

• 優先度が変更されたインスタンスを抽出し、新しい優先度値を持つ新しいインスタンスを挿入します
• 変更された優先度でインスタンスを更新してから、正しくソートされるようにキューを更新します

これを行う最善の方法は何ですか？

プログラムの別の部分で使用するために、Java の PriorityQueue クラスを clojure でラップしたいと考えています。私が理解しようとしているのは、これを巧妙な方法で実行し、優先キューを不変にする方法があるかどうかです。これを行う良い方法はありますか、それとも PriorityQueue を変更可能なデータ構造として使用したほうがよいでしょうか?

PriorityQueue並べ替えたいものを並べ替えるにはどうすればよいですか?

offerまた、とaddメソッドに違いはありますか?

注意してください、私は答えを求めていません。なぜ物事が機能するのかについて単純に興味があります

クラス割り当て用のプリンター シミュレーターの優先キューを実装する必要があります。インターネットで例を見た後、優先キューを正しく配置するために operator< がオーバーロードされていることに気付きました。

問題のコード: java2s プライオリティ キューの例

operator< をオーバーロードする必要があるのはなぜですか? 比較を行うために「<」はどこで使用されていますか? 演算子のオーバーロードを実装すると、キュー STL の動作が変わりますか?

この実装は、私にはまったく直感的ではないように思えます。代わりに operator> がオーバーロードされていないのはなぜですか? priority_queue が正しく機能するために operator< をオーバーロードする必要があることをどのように学習すればよいでしょうか?

PriorityQueue 内のオブジェクトの優先度が変更された場合、Java にはヒープを再評価する簡単な方法がありますか? 私はその兆候を見つけることができませんが、Javadoc何らかの方法でそれを行う必要がありますよね? 現在、オブジェクトを削除してから再度追加していますが、ヒープで更新を実行するよりも明らかに遅いです。

私の CS クラスでは、Prim のアルゴリズムを Java で実装する必要があり、プライオリティ キュー ステップに問題があります。私はプライオリティ キューを使用した経験があり、それらが一般的に機能することを理解していますが、特定のステップで問題が発生しています。

キー値 (ノードに接続されている最も軽いエッジであると想定) と親ノードを含むノード クラスを作成しました。私の問題は、ノードを優先キューに追加する方法を理解していないことです。親が NIL に設定され、キーが ∞ に設定されている場合、すべてのノードを優先キューに追加しても意味がありません。

scala.collection.mutable.PriorityQueue で使用したいクラスがありますが、この 1 つの目的のためだけに Ordered[A] にしたくありません。PriorityQueue に関して使用したい順序を、クラスの自然な順序とは見なしません。

したがって、私の PriorityQueue では、値を「順序」で並べ替えたいと思います。ただし、2 つのオブジェクトが同じシーケンスを持っているからといって、それらの「値」の内容が異なる可能性があるため、それらが自然に等しくなるわけではありません。

ここで、Java では、別の Comparator オブジェクトを PriorityQueue に提供できると便利です。私の Comparator は、単に「シーケンス」に関してオブジェクトを並べ替え、それらの「値」を無視します。

PriorityQueue クラスは、「A <% Ordered[A]」でパラメータ化する必要があります

私が読んだことから、これは、私のクラスが Ordered[A] を拡張する必要があるか、Ordered[A] への「暗黙的な定義」型変換を提供する必要があることを意味します。

Java ソリューションはより「機能的」であるように思われ、クラス階層に強制的に参加させたり、クラスにモンキーパッチを適用したりする代わりに、Comparator 関数のようなオブジェクトを渡すことができます。

PrioirityQueue の使用に代わる方法があることは理解していますが、ここで Scala の学習曲線にぶつかりそうで、この設計上の決定を十分に検討せずにあきらめたくありません。

これは Scala ライブラリでの不幸な決定にすぎないのでしょうか、それとも PriorityQueue をより使いやすく「機能的」にする何らかの呼び出し規約を誤解しているのでしょうか?

ありがとう

最初にヒューリスティックに基づいて要素の優先度を決定する優先度キューを使用しています。要素がデキューされると、ヒューリスティックが更新され、現在キューにある要素のキーが増加する場合があります。

O(1) キーの減少操作を償却したヒープ (具体的にはフィボナッチ ヒープ) があることは知っていますが、キーの増加操作に同様の境界を持つヒープ構造はありますか?

私のアプリケーションでは、これはパフォーマンスの問題ではありません (バイナリ ヒープは正常に動作します)。これは、単に学術的な好奇心の問題です。

編集：明確にするために、キーを減らすのではなく、キーを増やす操作の時間が O(logn) よりも速いデータ構造を探しています。私のアプリケーションは、ヒューリスティックが優先度を過大評価するため、キーを減らすことはありません。

Erlang での優先受信は、次のように簡単に実装できます。

私は、Nyström によるPriority Messaging made Easyという論文を読んでいます。そこでは、次の問題が説明されています。

[上記の] [コード] の例の主な問題は、内部ブロッキング受信から評価が再開されたときに、メールボックスに複数のメッセージがある可能性があることを考慮していないことです。最悪のシナリオでは、潜在的に膨大な数の要素のうち、最初の要素を除くすべてが優先メッセージになる可能性があります。このシナリオでは、実際には、意図したこととは正反対のことを達成したことになります。

私はこれを完全に理解していません。

質問 (1): 1 つのメッセージがメッセージ キューに到着するとすぐに、内部ブロッキング受信が「呼び出される」(つまり再開される) と仮定しますよね? 内部ブロッキング受信から再開するのにかかる短い時間内に、キューで待機している大量のメッセージが既にあると想定するのは現実的ですか?

質問 (2): また、最悪のシナリオは、1 つの通常のメッセージと多数の優先メッセージを持つキューとして説明されています。すべての receive 句は、最初にキュー内の最初のメッセージに対してチェックされ、次にキュー内の 2 番目のメッセージに対してチェックされるため、...(ソース: この本、69 ～ 70 ページ) ではありません。キューの最後に優先メッセージがあるメッセージ?