Java - PriorityQueueよりも速いものを探しています

Question

私は大量のデータでJavaを使用しています。

[私はできるだけ多くの問題を単純化しよう]

実際に私は、int型のKEYと（ゲッター&セッターとの）二重の重さを含む小さなクラス（要素）を持っています。

私はファイルからこれらのオブジェクトをたくさん読んで、私は最高の（ほとんどの重量）Mオブジェクトを取得する必要があります。

実際に私は、2つの要素を比較するためにコンパイラが書かれたPriorityQueueを使用していますが、動作しますが、速度が遅すぎます。

これを行うにはもっと速い方法が分かっていますか？

は、Mは、適当に小さい場合は、すべての要素をソートすると、コンピューティング多くの時間を無駄にするあなたに

Answer 1

ヒープベースの優先度キューは、この問題の優れたデータ構造です。正常性チェックと同じように、キューを正しく使用していることを確認してください。

最高のウエイトアイテムが必要な場合は、分-キューを使用します。ヒープの先頭が最も小さいアイテムです。すべてのアイテムを最大待ち行列に追加し、完了したら上位のMアイテムを調べるのは効率的ではありません。

各アイテムについて、キューにM個未満のアイテムがある場合は、現在のアイテムを追加します。それ以外の場合は、ヒープの先頭を確認します。現在のアイテムよりも小さい場合は破棄し、現在のアイテムを追加します。それ以外の場合は、現在の項目を破棄します。すべてのアイテムが処理されると、キューには最高重量のアイテムMが含まれます。

一部のヒープには、ヒープの先頭を置き換えるためのショートカットAPIがありますが、JavaのQueueはそうではありません。それでも、big-Oの複雑さは同じです。

Answer 2

ありがとうございます。最初のM個のオブジェクトを優先順位キュー（ヒープ、最上部の最小要素など）に入れ、残りの要素を反復するだけです。要素がヒープの先頭よりも大きい場合は、要素をヒープに追加します。

また、統計的なしきい値を見つけるために、配列全体を一度反復することができます。統計的なしきい値は、より大きな値を持つM個以上のオブジェクトがあることを確かめることができます（値に関していくつかの仮定が必要です。通常配布される）。より大きな値を持つすべての要素にソートを制限することができます。

Answer 3

@Tnay：比較を実行しないことについての注意点があります。残念ながら、あなたのサンプルコードはまだ1つを実行します。これは、問題を解決：

また

public int compare(ListElement i, ListElement j) { 
    return i.getValue() - j.getValue(); 
} 

、あなた、またビッグスどちらもメソッドを比較し、彼らがいるので、これは非常にトリッキーなバグであるいくつかのソートアルゴリズムの問​​題点であってもよく、0を返すことがないため、厳密には正しくあり別の実装に切り替えると表示されます。 the Java docsから

：

実装は、すべてのxおよびyについて（（Y、X）を比較されたい）== -sgn（（x、y）を比較されたい）そのSGNを保証しなければなりません。

これは、重要な一定係数の高速化を実行する場合としない場合があります。 これをericksonのソリューションと組み合わせると、（Mのサイズに応じて）もっと速くするのは難しいでしょう。 Mが非常に大きい場合、最も効率的な解決策は、配列のJavaの組み込みqsortを使用してすべての要素をソートし、最後に配列の一端を切り捨てることです。

Answer 4

n個のアイテムのトップmを得るための複雑さをO（n log m）とする、「ヒープの先頭のピーク」アルゴリズムに加えて、もう2つのソリューションがあります。

解決策1：フィボナッチヒープを使用します。

JDKのPriorityQueue実装は、バランスの取れたバイナリヒープです。 Fibonacci heapの実装より多くのパフォーマンスを絞ることができるはずです。償却された一定時間の挿入があり、バイナリヒープに挿入するときにヒープのサイズに複雑さΩ（log n）があります。あなたがすべての要素についてそれをしているなら、あなたはΩ（n log n）にいます。 Fibヒープを使用してn個のアイテムのトップmを見つけることは、複雑さO（n + m log n）を有する。これをヒープにm個の要素を挿入するだけの提案と組み合わせると、線形時間に近いO（n + m log m）が得られます。

解決策2：リストをM回横断します。

O（n）回の集合でk番目に大きい要素を得ることができるはずです。すべてをリストに読み込んで、以下を実行してください：

kthLargest(k, xs) 
    Pick a random pivot element p from the list 
    (the first one will do if your list is already random). 
    Go over the set once and group it into two lists. 
    Left: smaller than p. 
    Right: Larger or equal to p. 
    If the Right list is shorter than k, return kthLargest(k - right.size, Left) 
    If the Right list is longer than k, return kthLargest(k, right) 
    Otherwise, return p. 

これはあなたにO（n）時間を与えます。それをm回実行すると、時間がO（nm）のセット内のトップmのオブジェクトを得ることができるはずです。これは、十分に大きいnと十分に小さいmのn log nよりも厳密に小さくなります。たとえば、トップ10を100万アイテム以上にすると、バイナリヒープ優先度キューを使用する場合の半分の時間がかかりますが、それ以外はすべて等しいことになります。