問題タブ [priority-queue]

オブジェクトのプライオリティ キューが必要ですが、次のエラーが発生し続けます。

ここに私のコードからの抜粋:

何か案は？Node クラスを公開して、独自のファイルに入れる必要がありますか?

1億を超えるレコードを持つ優先キューを持つアプリケーションを実装する必要があります。私の問題は、このすべてのデータをメモリに保持できないため、ディスクに保存する必要があることです。このすべての情報をディスクに保存できるキャッシュソリューションはありますか？

私は、数百のデバイスに関連付けられた数千のタスクを実行するアプリケーションに取り組んでおり、各タスクの実行開始までに 5 ミリ秒未満、完了までに平均 100 ミリ秒かかります。

条件は次のとおりです。

1. 各デバイスは、一度に 1 つのタスクしか処理できません。たとえば、1 つのタスクは、後続のタスクが処理される前に、割り当てられたデバイスで実行を終了する必要があります。
2. スケジューラは効率的でなければなりません。現在、特定のデバイスのワーク キューの処理には、そのタスクの合計よりも時間がかかります。

現在の実装の基本的な説明は次のとおりです。

各デバイスには、そのデバイスに関連付けられたタスクで満たされたワーク キューが含まれています。

タスクがキューに入れられると、そのデバイスの作業キューがグローバル実行キュー (キューのキュー) に配置されます。グローバル実行キューは、デバイスのタスク オブジェクトをデキューし、1 つを処理してから、グローバル実行キューの後ろにデバイス キューを配置するワーカー スレッドによって消費されます。その特定のデバイスが再びキューから取り出されると、ワーカー スレッドはタスクが完了したかどうかを確認し、完了した場合は次のタスクが実行されます。このプロセスは、すべてのデバイス キューからグローバル ランキュー内のタスクがなくなるまで続きます。

改善のための提案はありますか？私はこれを明確に述べましたか？そうでない場合はお知らせください。明確にするために最善を尽くします。

ご覧いただきありがとうございます。よろしく。

基礎となるコンテナとしてベクトルでpriority_queueを使用しています。ただし、ヒープのサイズは非常に大きくなると思います。動的ベクトル容量のサイズ変更に関する問題を認識しています。そのため、priority_queue の基礎となるベクターに十分なスペースを最初に割り当てる方法を探しています。これを達成するための提案はありますか？

ありがとう

Java 標準ライブラリのプライオリティ キューの実装は、少しわかりにくい最小プライオリティ キューのようです。それを最大のものに変えるために、カスタムコンパレータオブジェクトを作成しました。

もっとエレガントな解決策があるかどうか疑問に思っていました。基本的に、ダイクストラなどを実装するために使用できる一般的な優先度キューは必要ありません。逆に動作するものがあることにさえ気づきませんでした:/

何が速いですか：優先キューに挿入するか、遡及的に並べ替えますか？

最後に並べ替える必要のあるアイテムをいくつか生成しています。複雑さの点で何が速いのか疑問に思いました。priority_queueまたは同様のデータ構造に直接挿入するか、最後に並べ替えアルゴリズムを使用しますか？

こんにちは私はリンクリストを使用してJavaで優先キューを最初から実装しようとしていますが、挿入時に要素を並べ替えるのに問題があります。これが私のこれまでのプログラムです。どんな助けでも大歓迎です。

現在出力：

更新：addSortを次のように変更しました：

これにより、nullポインタ例外がスローされます。

MultiMap を使用してプライオリティ キューを実装する必要があります。Google Collections の MultiMap を使用しています。次のコードは、MultiMap を作成し、そこにいくつかの要素を追加します。

今私の問題は pop メソッドを書く方法ですか?

for ループが必要であり、MultiMap を反復処理する必要があると思います。

最低のキーが最高の優先度であるべきなので、C++ では最初の要素へのポインターを設定し、それをインクリメントします。Javaでそれを行う方法は？

私は、アイテムがキュー内のどこかにあるかどうかを通知する検索/検索機能という要件を追加したプライオリティ キューの実装を検討しています。したがって、関数は次のようになります。insert、del-min、find です。

ヒープと自己平衡二分探索木のどちらを使用するべきかわかりません。PQ は通常、ヒープで実装されているようですが、検索機能も必要なので、二分探索木を使用する利点があるかどうか疑問に思っています。

さらに、平均して、削除よりも挿入の方が多くなります。d-ary heapも検討しています。基本的に、毎秒が重要です。

ありがとう！

2つのパラメータを指定できますか? たとえば、文字列と対応する整数を優先キーに追加したいとします。次に、その整数で並べ替えます。文字列または整数のいずれかを追加する方法は知っていますが、両方を追加する方法はわかりません。誰かが私を正しい方向に向けて、私がこれを正しい方法で行っているかどうかを教えてください。