大量のデータにJavaを使用しています。
[私は問題を可能な限り単純化しようとしています]
実際、私はintKEYとdoubleWEIGHT（getter＆settersを含む）を含む小さなクラス（Element）を持っています。
私はファイルからこれらのオブジェクトの多くを読み取り、最高の（最も重みのある）Mオブジェクトを取得する必要があります。
実際、私は2つの要素を比較するために作成されたコンパレータを備えたPriorityQueueを使用しており、それは機能しますが、遅すぎます。
あなたはそれをするためのより速い方法を知っていますか（私はあなたがそうすることを知っています）？
ありがとうございました
ヒープベースの優先キューは、この問題に適したデータ構造です。健全性チェックと同様に、キューを正しく使用していることを確認します。
最も重みの高いアイテムが必要な場合は、最小キューを使用します。ここで、ヒープの最上部が最小のアイテムです。すべてのアイテムを最大キューに追加し、M完了時に上位のアイテムを調べるのは効率的ではありません。
Mアイテムごとに、キュー内のアイテムが少ない場合は、現在のアイテムを追加します。それ以外の場合は、ヒープの上部を確認します。現在のアイテムよりも少ない場合は、それを破棄し、代わりに現在のアイテムを追加します。それ以外の場合は、現在のアイテムを破棄します。すべてのアイテムが処理されると、キューにはM最も重みの高いアイテムが含まれます。
一部のヒープには、ヒープの先頭を置き換えるためのショートカットAPIがありますが、JavaにQueueはありません。それでも、big-Oの複雑さは同じです。
n個のアイテムのtop-mを取得するためのO（n log m）の複雑さを提供する、提案された「ヒープの上部をのぞく」アルゴリズムに加えて、さらに2つのソリューションがあります。
解決策1：フィボナッチヒープを使用します。
JDKのPriorityQueueの実装は、バランスの取れたバイナリヒープです。フィボナッチヒープの実装からより多くのパフォーマンスを引き出すことができるはずです。一定時間の挿入は償却されますが、バイナリヒープへの挿入は、ヒープのサイズが複雑さΩ（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が十分に小さい場合はnlognよりも厳密に小さくなります。たとえば、100万を超えるアイテムのトップ10を取得するには、バイナリヒープ優先キューを使用する場合の半分の時間がかかります。他のすべての条件は同じです。
Mが適切に小さい場合、すべての要素をソートすると、多くの計算時間が無駄になる可能性があります。最初のM個のオブジェクトのみを優先キューに入れて（たとえば、ヒープ、最上位の最小要素）、残りの要素を反復処理することができます。要素がヒープの最上位よりも大きいたびに、topを削除してnewをプッシュします。ヒープへの要素。
または、配列全体を1回繰り返して、より大きな値を持つM個を超えるオブジェクトが存在することを非常に確実にできる統計的しきい値を見つけることができます（値に関して、正規分布の場合など、いくつかの仮定が必要になります）。次に、より大きな値を持つすべての要素に並べ替えを制限できます。
@Tnay：比較を行わないことについてのポイントがあります。残念ながら、サンプルコードはまだ1つを実行します。これで問題が解決します。
public int compare(ListElement i, ListElement j) {
return i.getValue() - j.getValue();
}
さらに、yoursとBigGsのcompareメソッドは、0を返さないため、厳密には正しくありません。これは、別の実装に切り替えた場合にのみ表示されるため、非常にトリッキーなバグである一部の並べ替えアルゴリズムで問題になる可能性があります。
Javaドキュメントから：
実装者は、すべてのxとyに対してsgn（compare（x、y））== -sgn（compare（y、x））であることを確認する必要があります。
これにより、一定係数の大幅な高速化が実行される場合と実行されない場合があります。これをエリクソンのソリューションと組み合わせると、おそらくそれをより速く行うのは難しいでしょう（Mのサイズによって異なります）。Mが非常に大きい場合、最も効率的な解決策は、配列でJavaの組み込みqsortを使用してすべての要素をソートし、最後に配列の一方の端を切り取ることです。