問題タブ [priority-queue]

プライオリティ キューがどのパラメーターでソートする必要があるかを認識させるのに苦労しています。カスタム クラスで less than 演算子をオーバーロードしましたが、使用していないようです。関連するコードは次のとおりです。

Node.h

Node.cpp

getTotalCost() は int を返します

main.cpp

私は何が欠けているか、間違っていますか？

並行キューの概念を理解するのに問題があります。キューはFIFO、つまり先着順のデータ構造であることを理解しています。

ここで、スレッドセーフと解釈する同時実行部分を追加すると（それが正しくない場合はお知らせください）、状況が少しあいまいになります。同時実行とは、さまざまなスレッドがキューに追加したり、キューから削除（アイテムの処理）したりする方法を意味しますか？並行性は、この操作に順序付けの感覚を提供していますか？

並行キューの機能の一般的な説明をいただければ幸いです。ここでの同様の投稿は、私が望んでいたほど一般的ではありません。

また、同時優先キューなどはありますか？その使用法は何でしょうか？

このテーマに関する簡単な説明や役立つリンクを事前に感謝します。

重複の可能性:
.Net の優先キュー

この質問は似ていますが、正確に知りたいです：

プライオリティ キューの .Net にクラス/構造体/... はありますか? このために持っているSTLのように priority_queue。カスタマイズされた並べ替えをサポートする比較関数を受け入れます。

私が .Net で見つけた最良のものは、キーで値をソートするSortedList< Key, Value >です。したがって、1 つの解決策は、Key クラスのカスタムCompareインターフェイスを実装することです。しかし、要素をキーと値のペアに分けることはできません。カスタム関数を使用して値に応じてキューに入れる必要があるアトミック要素があります。

それで、要素を並べ替えるための比較関数を受け入れる.Netのコレクションクラスはありますか?

この機能をサポートする .Net クラス (おそらくHashSet ) を派生させる方法はありますか?

ノート：

• 多くのサードパーティがこのために非常に優れたクラスを実装していることを知っています。おそらく良い例はPowerCollectionsです。しかし、.Net の既存のクラスを使用した迅速でシンプルなソリューションが必要です
• 私は.Net Framework 3.5を使用しています

私は2セットのAnimalオブジェクトを持っています。動物間の距離は、その特性を調べる特定のアルゴリズムを使用して定義されます。距離を最小化する 2 つのセット (それぞれから 1 つ) からペアを見つける方法を設計しようとしています。

私が持っていたアイデアの 1 つは、パラメーター化Tupleされたクラスを作成してペアを組むことAnimalsです。2 つのメンバー間の距離に従ってPriorityQueue並べ替えるには、コンパレータを使用して を作成します。Tuple<Animal>次に、 から最初のペアを選択しPriorityQueueます。

これは良いデザインですか、それとも無駄ですか？m と n が各コレクションのサイズである場合、O(m+n) 時間で実行されると思います。

パラメータ化されたクラスの場合Tuple、でのみ機能する Comparator を使用するとどのように機能しAnimalますか?

findMinimalPairこの方法を使用して、オブジェクトのグラフの距離を最小化するスパニング ツリーを作成したいと考えていAnimalます。からペアを継続的にポップしPriorityQueue、各ペアに各コレクションのメンバーが 1 つずつ含まれていることを確認して、これを行ったらどうなるでしょうか。

これが基本的な例です。距離は次のとおりです。

コレクションが次のとおりであると仮定します。

A0

A1、A2、A3

タプルを距離順にソートすると、次のようになります。

したがって、A3 が最も近いことがわかります。次に、A3 が最初のコレクションに移動されます。

A0、A3

A1、A2

繰り返しますが、最小ペアを確認します。

今A2が取られています。それがどのように機能するか見てください。

これが私がやったことです。コメント?

priority_queue を使用しようとしていますが、プログラムが常にエラー メッセージ HEAP CORRUPTION DETECTED で失敗します。

ここにスニペットがあります：

クラス Message にはオーバーロードされた演算子 > および < があります

ここで私はキューをいっぱいにします：

メインプログラムでは：

何が問題なのかわかりません。8個くらいプッシュすると発生し、オンラインで失敗する

< キュー > で

:(

メッセージ クラスの定義は次のとおりです。非常に単純です。

};

ポルカ - メッセージ

条件変数に関する私の現在の理解では、すべてのブロックされた (待機中の) スレッドは基本的な FIFO キューに挿入され、その最初の項目は signal() が呼び出されたときに呼び出されます。

このキューを変更 (または新しい構造を作成) して優先キューとして実行する方法はありますか? 私はしばらくそれについて考えてきましたが、CV とミューテックスに固有の既存のキュー構造によって、私が経験した解決策のほとんどが妨げられてしまいます。

ありがとう！

（私の場合）画像のダウンロードを優先する必要があります。

これを行うには、独自の downloadqueue メカニズムを構築せずにこれを実行できるプラグイン (できれば jQuery 用) を使用することをお勧めします。

次のシナリオを検討してください。

あなたはウェブページを持っています。Web ページは、特定のユーザーに 3 つの画像を表示できます。これらの画像は、ユーザーの要求に応じて一度に 1 つずつ表示されます。

次に、ユーザーが選択するまで画像を上から下にロードすることが理想的です。次に、彼の選択がキューを上に移動し、次の列になるようにします (彼が選択するたびに)。

もちろん、画像が 3 つしかないページでは、これは実際には問題になりませんが、画像が増えると重要になります。

私は現在、画像を表示するために background-image のみを使用しており、そのままにしておきたいと思っています。

ああ、また、画像の読み込み中に「spinner.gif」を表示したいと思います。

助言がありますか？

ありがとう。

更新これに基づいて独自のキューシステムを作成することになりました：http://jqueryfordesigners.com/image-loading/

PriorityQueueを使用して、グラフのトポロジカルソートを実行したいと思います。簡潔にするために、コンパレータには匿名の内部クラスを使用したいと思います。ただし、g見ているノードの程度を判断するには、グラフにアクセスする必要があります。これは可能ですか？

修正されたコード

プリム法を使用してMSTを解決するコードを作成しました。この種の実装（優先キューを使用）はO（E + VlogV）= O（VlogV）である必要があることを読みました。ここで、Eはエッジの数、Vはエッジの数ですが、コードを見ると単純に見えません。誰かが私のためにこれを片付けることができれば私はそれをいただければ幸いです。

私には、実行時間はこれであるように思われます：

whileループにはO（E）回かかります（すべてのエッジを通過するまで）そのループ内で、O（logE）時間かかるQから要素を抽出します。そして、2番目の内側のループにはO（V）時間がかかります（すべての頂点を追加する必要があるため、このループがV回実行されることは明らかですが、毎回このループを実行するわけではありません）

私の結論は、実行時間は次のとおりです。O（E（logE + V））= O（E * V）。

これは私のコードです：

簡単に言えば、私はグラフを実装していて、現在はクルスカルに取り組んでいます。優先キューが必要です。優先度キューの私の定義は、最小のキーを持つ要素が最初に来るということですか? これは間違っていますか？重み付けされたエッジ (または数値) をキューに挿入すると、並べ替えられないためです。

これはこれを出力します。[1、54、51、102、99、55]。これは、私が望むようにソートされていません! はい、エッジ オブジェクトから数値を抽出し、その int に基づいて比較するプライオリティ キューに入るコンパレータを作成しました。それで、これはうまくいくはずですか、それとも、このデータ構造がどのように機能するかという概念全体を完全に誤解したのでしょうか?