問題タブ [priority-queue]

私は、メモリからドキュメント ID の長いリストを読み取り、一致する ID を探すクエリ プロセッサに取り組んでいます。見つかった場合は、docid (int) とドキュメントのランク (double) を含む DOC 構造体を作成し、それを優先キューにプッシュします。私の問題は、検索された単語に長いリストがある場合に、DOC をキューにプッシュしようとすると、次の例外が発生することです。 :bad_alloc メモリ位置 0x0012ee88..

単語に短いリストがある場合、うまく機能します。コードのいくつかの場所で DOC をキューにプッシュしようとしましたが、それらはすべて特定の行まで機能します。その後、上記のエラーが発生します。読み込まれた最長のリストが 1 MB 未満であり、割り当てたすべてのメモリを解放しているため、何が問題なのか完全に途方に暮れています。DOC を保持する容量のあるキューに DOC をプッシュしようとすると、突然 bad_alloc 例外が発生するのはなぜですか?

このような質問は、すべてのコードを見ないと答えられないことはわかっていますが、ここに投稿するには長すぎます。私はできる限り多くのことを書いていますが、誰かが私に答えてくれることを切望しています。

NextGEQ 関数は、docid の圧縮ブロックのリストをブロックごとに読み取ります。つまり、ブロック内 (別のリスト内) の最後の docid が、渡された docid よりも大きいことがわかった場合、ブロックを解凍し、正しいものが見つかるまで検索します。各リストは、圧縮された各チャンクの長さとチャンク内の最後の docid を含むリストに関するメタデータで始まります。data.query は、メタデータの先頭を指します。data.metapointer は、関数が現在あるメタデータ内の任意の場所を指します。また、data.blockpointer は、圧縮されていない docid のブロックの先頭を指します (存在する場合)。すでに解凍されていることがわかった場合は、検索するだけです。以下では、関数を初めて呼び出すと、ブロックが解凍され、docid が検索されます。その後のキューへのプッシュは機能します。2回目はありません」解凍する必要さえありません。つまり、新しいメモリは割り当てられませんが、その後、キューにプッシュすると bad_alloc エラーが発生します。

編集：コンパイルできるように、コードをさらにクリーンアップしました。OpenList() 関数と NextGEQ 関数も追加しましたが、後者は長いですが、問題はそのどこかでヒープの破損が原因であると思われるためです。どうもありがとう！

どうもありがとう、bsg。

両方のエントリが他のペアのエントリよりも厳密に小さい場合はペアが別のペアよりも小さく、両方のエントリが他のペアのエントリよりも厳密に大きい場合は他のペアよりも大きいと見なされる整数のペアを優勢に並べ替えようとしています。ペア。他のすべてのケースは、比類のないものと見なされます。

私がこれを解決したいのはComparator、上記を実装する a を定義することですが、比較できない場合には例外をスローし、それを a に提供しPriorityQueueます。もちろん、ペアを挿入している間、優先キューは新しいエントリをヒープ内の正しい位置までバブリングしながらいくつかの比較を行います。これらの多くは比較できます。ただし、バブリング プロセス中に、この新しいペアとは比較にならないペアが検出され、例外がスローされる場合があります。これが発生した場合、の状態はどうなりますPriorityQueueか? 挿入しようとしていたペアは、例外がスローされる前の最後の位置でヒープに配置されますか? PriorityQueue's remove(Object o)この方法を使用するPriorityQueueと、一貫した状態に復元されますか?

ありがとう

C ++標準ライブラリのドキュメントでいくつかの関数を検索しているときに、優先キューのプッシュとポップには一定の時間が必要であることを読みました。

http://www.cplusplus.com/reference/stl/priority_queue/push/

定数（priority_queue内）。ただし、push_heapは対数時間で動作することに注意してください。

私の質問は、プッシュとポップのためにO（1）で優先キューを維持するためにどのようなデータ構造が使用されているかということです。

PriorityNode は次のように定義されています。

ここで Comparator を使用し、プライオリティ キューを実装するのが非常に困難です。正しい方向を教えてください。

プライオリティ キューを使用して多くの作業が行われる、複雑なジョブ割り当てアプリケーションのコーディングを終えたところです。しかし、デプロイしたところ、Web サーバーで PHP 5.2 が実行されていることがわかりました。

SPLPriorityQueue のドロップイン代替品としてサーバーできる PHP<5.3 の実装はありますか?

オブジェクトを優先キューに追加しようとすると、nullポインタ例外が発生し続けます

キューを初期化します：

そしてここで私はそれに追加しようとします：

なぜこれが機能しないのですか？NodeObjectを追加する直前に作成するため、NodeObjectがnullではないことはわかっています。

どちらの実装が「重く」ありませんか: PriorityQueue または並べ替えられた LinkedList (コンパレーターを使用)?

すべての商品を揃えたい。挿入は非常に頻繁に行われ、場合によってはすべてのリストを実行していくつかの操作を行う必要があります。

Collections.binarySearch() メソッドを使用して PriorityQueue 内の要素を検索できますか? それ以外の場合、検索アルゴリズムを PriorityQueue に適用するにはどうすればよいですか?

私はこれを持っています（クラスEventoはComparableを実装しています）：

そして、私はこのエラーを受け取りました：「型 Collections のメソッド binarySearch(List>, T) は、引数 (PriorityQueueCAP, Evento) には適用できません」

なんで？

前もって感謝します！

着信クエリを受け入れて実行するサーバーアプリケーションがあります。クエリが多すぎる場合はキューに入れ、他のクエリの一部が実行された場合は、キューに入れられたクエリも実行する必要があります。異なる優先度のクエリを渡したいので、priority_queueを使用するのが最善の選択だと思います。

たとえば、受け入れているクエリの量（a）が限界に達し、新しいクエリがキューに保存されます。（a）からのクエリの一部が実行される場合、すべてのクエリの優先度は1（最低）になります。プログラムは、キューから最も優先度の高いクエリを選択して実行します。それでも問題ありません。現在、誰かがキューに追加される優先度5のクエリを送信しています。これは最も優先度の高いクエリであるため、実行中のクエリが制限に達しなくなるとすぐに、アプリケーションはこのクエリを実行します。優先度1の500個のクエリがキューに入れられても、誰かが常に優先度5のクエリを送信しているために実行されないという最悪のケースがあります。したがって、これらの500個のクエリは非常に長い間キューに入れられます。これを防ぐために、優先度の高いクエリよりも優先度の低いすべてのクエリの優先度を上げたいと思います。この例では、優先度が5未満です。したがって、優先度が5のクエリが削除された場合キューのうち、優先度が5未満の他のすべてのクエリは0.2増やす必要があります。このように、優先度の高いクエリが100個ある場合でも、優先度の低いクエリはキューに入れられません。

誰かが優先順位の問題を解決するのを手伝ってくれることを本当に望んでいます：

私のクエリはオブジェクトで構成されているので、次のようなものが機能する可能性があると思いました。

これは宿題ではありません。

最後の N 個のアイテムを最小値で保存するために、小さな「優先キュー」(現時点では配列として実装) を使用しています。これは少し遅いです - O(N) アイテムの挿入時間。現在の実装では、配列内の最大のアイテムを追跡し、配列に収まらないアイテムを破棄しますが、操作の数をさらに減らしたいと考えています。

次の要件に一致するプライオリティ キュー アルゴリズムを探しています。

1. queue は配列として実装できますが、これはサイズが固定で、拡張できません。キュー操作中の動的メモリ割り当ては固く禁じられています。
2. 配列に収まらないものはすべて破棄されますが、キューはこれまでに遭遇した最小の要素をすべて保持します。
3. O(log(N)) の挿入時間 (つまり、要素をキューに追加するには、最大で O(log(N)) かかる必要があります)。
4. (オプション) キュー内の *最大* アイテムに対する O(1) アクセス (キューには *最小* アイテムが格納されるため、最大のアイテムが最初に破棄され、操作の数を減らすためにそれらが必要になります)
5. 実装/理解が容易。理想的には、二分探索に似たもので、一度理解すると永遠に記憶されます。
6. 要素をソートする必要はありません。これまでに遭遇した N 最小値を維持する必要があります。それらが必要になったら、それらすべてに一度にアクセスします。したがって、技術的にはキューである必要はありません。N個の最後の最小値を保存する必要があるだけです。

最初はバイナリ ヒープを使用することを考えていました (配列を介して簡単に実装できます) が、配列がそれ以上大きくならない場合、うまく動作しないようです。リンクされたリストと配列では、物事を移動するのに余分な時間が必要になります。stl プライオリティ キューは大きくなり、動的割り当てを使用します (ただし、これについては間違っている可能性があります)。

それで、他のアイデアはありますか？

--EDIT--
STL 実装には興味がありません。STL 実装 (数人が提案) は、関数呼び出しの数が多いため、現在使用されている線形配列よりも動作が少し遅くなります。

実装ではなく、プライオリティ キューアルゴリズムに興味があります。