問題タブ [priority-queue]

プライオリティ キューまたはヒープ データ構造の .NET 実装を探しています

プライオリティ キューは、任意の間隔で新しい要素をシステムに入力できるため、単純な並べ替えよりも柔軟性が高いデータ構造です。新しいジョブを優先キューに挿入する方が、そのような到着ごとにすべてを再ソートするよりもはるかに費用対効果が高くなります。

基本プライオリティ キューは、次の 3 つの主要な操作をサポートしています。

• 挿入 (Q,x)。キー k を持つアイテム x が与えられた場合、それを優先キュー Q に挿入します。
• Find-Minimum(Q)。優先度キュー Q 内の他のどのキーよりもキー値が小さい項目へのポインターを返します。
• 最小削除 (Q)。キーが最小の優先度キュー Q からアイテムを削除します

私が間違った場所を探していない限り、フレームワークにはありません。誰かが良いものを知っていますか、それとも自分でロールする必要がありますか?

優先度の異なる多数のアイテムを含む IBM WebSphere MQ キュー (Windows 上で実行) があります。

現在、 を使用して合計深度カウントをmqQueue.CurrentDepth取得していますが、キュー内の各優先度レベルのアイテム数を取得したいと考えています。

これを達成する方法はありますか？

更新:これが Hashed Timing Wheels の私の実装です。パフォーマンスと同時実行性を改善するアイデアがあれば教えてください。(2009 年 1 月 20 日)

更新: Hierarchical and Hashed Timing Wheelsを使用してこの問題を解決しました。(2009 年 1 月 19 日)

タイムアウト処理用に最適化された特別な目的のタイマーを Java で実装しようとしています。たとえば、ユーザーは期限のあるタスクを登録でき、タイマーは期限が過ぎたときにユーザーのコールバック メソッドに通知できます。ほとんどの場合、登録されたタスクは非常に短い時間内に完了するため、ほとんどのタスクはキャンセルされるか (例: task.cancel())、将来に再スケジュールされます (例: task.rescheduleToLater(1, TimeUnit.SECOND))。 .

このタイマーを使用して、アイドル状態のソケット接続を検出し (たとえば、10 秒以内にメッセージが受信されない場合に接続を閉じる)、書き込みタイムアウトを検出します (たとえば、書き込み操作が 30 秒以内に終了しない場合に例外を発生させます)。異常なネットワークの問題がない限り、タイムアウトは発生せず、クライアントはメッセージを送信し、応答が送信されます。

java.util.Timer または java.util.concurrent.ScheduledThreadPoolExecutor は、ほとんどのタスクがタイムアウトになると想定しているため、使用できません。タスクがキャンセルされた場合、キャンセルされたタスクは、ScheduledThreadPoolExecutor.purge() が呼び出されるまで内部ヒープに格納されます。これは非常にコストのかかる操作です。(O(NlogN) もしかして?)

CSクラスで学んだ従来のヒープまたは優先度キューでは、要素の優先度の更新は高価な操作でした（多くの場合、要素を削除して再挿入することによってのみ達成できるため、O（logN）新しい優先度値. フィボナッチヒープのようないくつかのヒープには、reduceKey() と min() 操作の O(1) 時間がありますが、少なくとも私が必要としているのは、高速な increaseKey() と min() (または reduceKey() と max()) です。 .

この特定のユースケースに対して高度に最適化されたデータ構造を知っていますか? 私が考えている戦略の 1 つは、すべてのタスクをハッシュ テーブルに保存し、すべてのタスクを 1 秒ごとに反復処理することですが、それほど美しいものではありません。

どのプロセスが最初に実行されるかを処理するために小さなキューを実装しています。これを行うために、データベース内のテーブルを使用しています。テーブルの構造は次のとおりです (SQLite でモックアップしています)。

SQL を記述して、次に実行できるプロセスの行を取得しようとしています。サンプルデータは次のとおりです。

この SQL を使用すると、適切な順序でデータを取得できます。

これにより、優先度番号が最も低い (最も重要な) アイテムが一番上に表示され、それらの優先度番号の中で (タイムスタンプによって) 最も早くキューに入れられたアイテムが一番上に表示されます。

このクエリを実行して最初の行のみを取得することもできますが、キューの先頭にあるプロセスの 1 行を取得する SQL クエリを使用して実行したいと思います (上記の例のデータでは、行id=7)。

自己結合とサブクエリを実行しようとしましたが、メンタルブロックが発生しているに違いありません-正しく取得できないようです.

前もって感謝します！

編集

データベースに依存しないクエリを探していることを忘れていました。私はこれを SQlite でモックアップしていますが、これを DB2 または Oracle で実装する可能性は十分にあります。クエリで "limit 1" タイプの演算子を使用することを考えていましたが、それはデータベース エンジンによって異なります。

STLpriority_queueを使用すると、使用しようとするとすぐに「無効なヒープ」というエラーが表示されますpop()。値をキューにプッシュできtop()ます。キューの は、期待どおりであり、アクセス可能です。pop()、再ヒープに行くと、問題があるようです。

テンプレート化されたクラスへのポインタをキューに保存しています。私は比較をオーバーロードしています：

はpriority_queueクラスのプライベート メンバーです。

負の距離は無限大と見なされ、常に他のものよりも大きいため、過負荷はそのように機能します。無限を表すために、距離は -1 に初期化されます。キューは、最小であるが負でないものを一番上に保持する必要があります。

オーバーロードでポインターを逆参照していますが、そこで行っていることは許容されますか? そして、オーバーロードする必要がある別の演算子はありますか?

コードを添付しますが、添付すると、人々を怖がらせてしまうようです。もっと見るようにリクエストしてください。別のメッセージに添付します。

ポインターへのポインターの配列を動的に宣言します。これらはプッシュされるものです。priority_queue参照によってストアを想定しているためです。したがって、ループで宣言されたポインターをキューに入れるだけでは、そのポインターは範囲外になります。これらのポインターは適切な を指しVertex<type>、関数全体に存在します。

Visual Studio 2008 デバッガーは、「stdthrow.cpp」の 24 行目に移動します。

Unix の C でキューイング メカニズムを使用しています。XML トランザクションを受け入れます。一部のトランザクションには、保存されるレコードが含まれています。他のトランザクションはそれらのトランザクションを要求します。トランザクションは、独自のキューであるファイルに保存されます。先入れ先出し、とてもシンプルです。ファイルの先頭にあるヘッダー領域は、次に読み取る位置と次に書き込む位置を追跡します。ファイルのロックを使用しますが、取得はリモート システムからポーリングされるため、セマフォは使用しません。そして、キューにアクセスするプログラムは 1 つだけです。それはCです。何年もうまく機能しています。

今、システムを拡張する必要があります。トランザクションには、追加の XML タグが含まれます。そのタグの値に基づいて選択的に取得する必要があります。単純なキューから優先キューに移行します。タグにはさまざまな値が含まれる場合があります。AX、BX、CX、FL、TS と言ってください。トランザクションは受信順にキューに追加されます。受信した順に取得するか、タグが FL である次のトランザクションを取得できる必要があります。またはTS。または (CS または FL)。またはAXではありません。

これを行うにはどうすればよいですか？

私たちが必要としているのは、シンプルで速いことです。いくつかのオプションが思い浮かびます:

1. Berkely DB のようなものを使用して、キューをある種のデータベースに変えます。
2. PostgreSQL データベースを利用して、プライオリティ キューとして使用できるテーブルを作成します。
3. 私たちが望むことをするCライブラリを見つけてください。
4. 独自のディスクベースのプライオリティ キューを記述します。

いくつかの制約があります。時間は刻々と過ぎており、これは数週間で行う必要があります。システムへの迅速な挿入のための C。キューにアクセスするプログラム内の他のすべてのビジネス ロジックを変換するのに十分な速さでタップダンスできるなら、おそらく Python でしょう。私たちはデータベースシステムを制御できず、DBA は「自分の」と見なすものに対して厄介な習慣を持っており、これが重要なシステムであるにもかかわらず、アップタイムの信頼性がないため、PostgreSQL を使用しないことを好みます。政治か！DBA はまた、PostgreSQL テーブルを使用することは効率的な方法ではないと述べています。私たちは、ローカライズされたものを好み、それを制御できるようにします。毎分多くのトランザクションを処理するには、電光石火の速さが必要です。

私はどんな提案にもオープンです。提案は多ければ多いほどよい。

重複の可能性:
重複キーを許可する C# のソート可能なコレクション

基本的に、カスタム比較器の実装に入ることなく、辞書を重複キーで機能させたいと思います。次の考え方があります。

ただし、まだオーバーヘッドがあります。辞書に「AllowDuplicates」があればいいのにと思います。

これまでに挿入された最大のアイテムを常にn(順不同で) 保持するデータ構造が必要です。

したがって、nが 3 の場合、いくつかの数字を挿入すると、コンテナーの内容が変更される次のセッションを作成できます。

あなたはアイデアを得る。データ構造の名前は何ですか? これを実装する最良の方法は何ですか? それとも、これはいくつかのライブラリにありますか？

priority_queue逆比較を使用popするため、最小の要素を削除する要素 (委任)を持つコンテナーを使用することを考えています。そのため、insert関数は最初に、挿入される新しい要素が最小の要素よりも大きいかどうかを確認します。もしそうなら、その最小のものを捨てて、新しい要素をプッシュします。

（私はC++実装を念頭に置いていますが、それでも問題は言語に依存しません。）

Java のプライオリティ キューO(log n)は、 put (挿入) とO(log n)poll (検索と min 要素の削除)が複雑なデータ構造です。

C++ STL のmultimapには同じ機能がありますがO(1)、min 要素の取得と削除 (開始と消去) が複雑になります。Java に相当するものはありますか?