Javaでストリームを解析中に見つかった最大値を追跡する最良の方法

Question

大きなファイルを1行ずつ解析して、各行の部分文字列を読み込みます。私は各部分文字列から1行につき〜30の整数値を取得し、ファイルから最も高い5の値を返す必要があります。どのようなデータ構造が、5つの最大値を追跡するのに最も効率的でしょうか？

Answer 1

ソート順のLinkedList挿入を使用できます。それぞれ新しいint、あなたはそれが最大であることを確認するために最後をチェックします。次に、降順で繰り返し、newInt>ノードのintであれば、そこに新しいintを挿入し、長さ5を維持するためにremoveLast（）を挿入します。

配列も機能しますが、シャッフルする必要があります。

Answer 2

TreeSet（基本的にソートされたセット）を使用し、セットに追加するたびにfirst（最低）の要素を削除します。 これは、重複をdicardします。

SortedSet<Integer> set = new TreeSet<>(); 
for (...) { 
    ... 
    if (set.size() < 5) { 
     set.add(num); 
    } else if (num > set.first()) { 
     set.remove(set.first()); 
     set.add(num); 
    } 
} 

Answer 3

グアバライブラリは、O（N）時間とO（K）の空間にIterableから最大k個の要素を返すOrdering.greatestOf方法を有しています。

実装はパッケージプライベートTopKSelectorクラスにあります。

Answer 4

この問題は通常、heap,で解決されますが、（おそらく反直感的に）最小ヒープを使用します（最小の要素はヒープの「トップ」です）。

アルゴリズムは、基本的にはこれです：

 
    for each item parsed 
     if the heap contains less than n items, 
     add the new item to the heap 
     else 
     if the new item is "greater" than the "smallest" item in the heap 
      remove the smallest item and replace it with the new item 

作業が完了したら、あなたは最低から最大にヒープから要素をpopすることができます。

か、具体的に：

static <T extends Comparable<T>> List<T> top(Iterable<? extends T> items, int k) { 
    if (k < 0) throw new IllegalArgumentException(); 
    if (k == 0) return Collections.emptyList(); 
    PriorityQueue<T> top = new PriorityQueue<>(k); 
    for (T item : items) { 
     if (top.size() < k) top.add(item); 
     else if (item.compareTo(top.peek()) > 0) { 
     top.remove(); 
     top.add(item); 
     } 
    } 
    List<T> hits = new ArrayList<>(top.size()); 
    while (!top.isEmpty()) 
     hits.add(top.remove()); 
    Collections.reverse(hits); 
    return hits; 
    } 

あなたはtop of the heap efficiently,に新しい項目を比較することができますし、厳密にすべての時間を注文したすべての要素を維持する必要はありませんので、これは完全に注文したよりも高速ですTreeSetのようなコレクション。

5つの要素の非常に短いリストについては、配列の反復処理が高速になる場合があります。しかし、 "トップヒット"コレクションのサイズが大きくなると、このヒープベースのメソッドが勝つでしょう。