0

任意の数のレコードから最も低い 10 個の値を見つけたいとしましょう。レコードをループしているときに、最大サイズの 10 に達するまでレコードを構造に追加します。その後、リスト内の最高のレコードより大きくないレコードを追加するたびに、現在の最高の最大数のレコードを保持して削除されます。

または、より簡単に言えば、オブジェクトの (おそらく非常に大きな) リストを処理し、メモリ効率の良い方法で特定の数だけを保持するにはどうすればよいでしょうか?

これを行うある種のデータ構造があったことを思い出しているようですが、どうやらグーグルの仕事がうまくいっていないようです。それがどんな構造であっても、どこかにJava実装があると思います。

4

2 に答える 2

2

N 個の値をすべてメモリに保持する場合は、バイナリ最小ヒープを使用して配列をヒープ化できます。

その構築には O(n) の償却時間がかかり、10 個の最小要素を取得するには O(10*log(10))、つまり O(1) かかります。

于 2012-08-03T20:12:10.533 に答える
1

これを行う簡単な方法は、max-heap (バイナリ ヒープなど) を実装し、次のようにすることです (疑似コード ahoy!)。

List elms; // original elements
Heap heap; // heap we store in

for element e in elms:
    push e onto heap
    if heap contains more than 10 elements:
        pop the max element from heap

この後heap、10 個の最小要素が含まれます。

バイナリ ヒープを想定すると、必要な要素の数である tihs にO(k)余分なスペースとO(n lg k)時間がかかりkます。

于 2012-08-02T17:43:16.133 に答える