java - 大きな配列からのデータのサンプリング

Question

基本的に、非常に大きなオブジェクトの配列があり、最も適合しないオブジェクトの 10% を削除する必要があります。

各オブジェクトには、それに関連付けられたフィットネス変数 (double) があります。オブジェクトが適合するかどうかを判断する数値はありません。最も適合しないものが必要です。

最も適合しないオブジェクトを取得 (サンプリング) する最良の方法は何ですか?

1 つの方法として、20% をランダムに選択し、データを並べ替えてから、10% を削除することができます。しかし、これはあまり賢明な方法ではないと思います。

もう一方の方法では、配列を常にソートしてから、最初の 10% を削除します。しかし、大きなオーバーヘッドである挿入/更新中に常に配列をソートし続ける必要があるため、これは非常に良いとは思いません..

Answer 1

k を とyourCollection.length() * 0.1し、 とするn = yourCollection.length()。

k 番目に小さい要素 (QuickSelect または 5 の中央値) を見つけます。ここで重要なのはフィットネスです。と呼びましょうp。これは で実行できますO(n)。

次に、コレクションをトラバースし、フィットネスが p.fitness 未満のすべてのアイテムを削除します。解決策がありO(n)ます。

または、 でヒープを作成し、 でヒープO(n)から要素key=fitnessを削除できます。kO(k * log(n))