5

それぞれの重み ( で表されるInteger) に従って、固定数のアイテムを Web ページに表示しようとしています。これらのアイテムが見つかるリストは、実質的に任意のサイズにすることができます。

頭に浮かぶ最初の解決策は、 を実行して、Collections.sort()を経由してアイテムを 1 つずつ取得することListです。たとえば、上位 8 つの項目を準備するために使用できる、よりエレガントなソリューションはありますか?

4

10 に答える 10

6

ただ行くCollections.sort(..)。十分効率的です。

このアルゴリズムは、n log(n) のパフォーマンスを保証します。

リストのいくつかの特徴的なプロパティを知っている場合は、具体的なケースに対してより効率的なものを実装しようとすることができますが、それは正当化されません。さらに、たとえば、リストがデータベースから取得された場合、コードではなくデータベースで並べ替えることができます。LIMIT

于 2010-04-12T20:34:50.193 に答える
5

オプション:

  1. 途中で見つかった上位 N 個の重みを維持しながら 、線形検索を実行します。なんらかの理由でページを表示する間にソート結果を再利用できない場合 (リストが急速に変化している場合など)、これは長いリストをソートするよりも高速です。

    更新:線形検索は必然的に並べ替えよりも優れていることを修正しました。より良い選択アルゴリズムについては、ウィキペディアの記事「Selection_algorithm - k 最小または最大要素の選択」を参照してください。

  2. List重量順にソートされた (元のものまたは並列のもの) を手動で維持します。Collections.binarySearch()などのメソッドを使用して、新しいアイテムを挿入する場所を決定できます。

  3. Collections.sort()を呼び出して、各変更後、バッチ変更後、または表示の直前に (おそらく、既に並べ替えられたリストの並べ替えを避けるために変更フラグを維持します) List、重量順に並べ替えられた(元のものまたは並列のもの) を維持します。

  4. ソートされた重みの順序を維持するデータ構造を使用してください:プライオリティ キュー、ツリー セットなど。独自のデータ構造を作成することもできます。

  5. 上位 N 項目の 2 番目の (場合によっては重み順) データ構造を手動で維持します。このデータ構造は、元のデータ構造が変更されるたびに更新されます。元のリストとこの「トップ N キャッシュ」を一緒にラップする独自のデータ構造を作成できます。

于 2010-04-12T21:30:29.483 に答える
3

max-heapを使用できます。

データがデータベースに由来する場合は、その列にインデックスを配置し、ORDER BY と TOP または LIMIT を使用して、表示する必要があるレコードのみをフェッチします。

于 2010-04-12T20:34:02.900 に答える
3

ドルを使用：

List<Integer> topTen = $(list).sort().slice(10).toList();

ドルを使用せずに を使用してから、sort()を使用しCollections.sort()て最初の n 個のアイテムを取得しlist.sublist(0, n)ます。

于 2010-04-12T20:42:59.737 に答える
3

または優先キュー。

于 2010-04-12T20:35:11.923 に答える
2

これらの上位Nを抽出するアイテムのリストは任意のサイズである可能性があり、大きいと思われるので、上記の単純なsort()回答（合理的なサイズの入力に完全に適しています）を拡張します。ここでの作業のほとんどは、上位 N を見つけることです。それらの N を並べ替えるのは簡単です。あれは：

Queue<Integer> topN = new PriorityQueue<Integer>(n);
for (Integer item : input) {
  if (topN.size() < n) {
    topN.add(item);        
  } else if (item > topN.peek()) {
    topN.add(item);          
    topN.poll();
  }
}

List<Integer> result = new ArrayList<Integer>(n);
result.addAll(topN);
Collections.sort(result, Collections.reverseOrder());

ここでのヒープ (最小ヒープ) は、少なくともサイズが制限されています。すべてのアイテムからヒープを作成する必要はありません。

于 2010-04-12T21:25:37.837 に答える
1

いいえ、そうではありません。少なくとも Java の組み込みメソッドを使用していません。

リストから最大 (または最小) N 個のアイテムを操作よりも速く取得する賢い方法がありますO(n*log(n))が、そのためにはこのソリューションを手作業でコーディングする必要があります。アイテムの数が比較的少ない場合 (数百を超えない)、それを使用して並べ替えCollections.sort()、上位 N の番号を取得することが IMO への道です。

于 2010-04-12T20:36:22.000 に答える
1

数にもよります。n をキーの総数として定義し、m を表示する数として定義します。
全体を並べ替える:O(nlogn)
毎回配列をスキャンして、次に大きい数を探す:O(n*m)
では、問題は、n と m の関係は?
の場合m < log n、スキャンがより効率的になります。
それ以外の場合は m >= log n、並べ替えが改善されることを意味します。（エッジケースでm = log nは実際には問題になりませんが、並べ替えにより、配列を並べ替えるという利点も得られます。これは常に素晴らしいことです。

于 2010-04-12T22:07:16.480 に答える
0

リストのサイズが N で、取得するアイテムの数が K の場合、リストに対して Heapify を呼び出す必要があります。これにより、リスト (配列など、インデックス可能である必要があります) が優先キューに変換されます。( http://en.wikipedia.org/wiki/Heapsortの heapify 関数を参照)

ヒープの一番上にあるアイテム (最大アイテム) を取得するには、O (lg N) 時間かかります。したがって、全体の時間は次のようになります。

O(N + k lg N)

k が N よりもはるかに小さいと仮定すると、これは O (N lg N) よりも優れています。

于 2010-04-13T00:24:41.293 に答える
0

ソートされた配列を保持したり、別のデータ構造を使用したりすることができない場合は、次のようなことを試すことができます。O 時間は大きな配列の並べ替えに似ていますが、実際にはこれの方が効率的です。

small_array = big_array.slice( number_of_items_to_find );
small_array.sort();
least_found_value = small_array.get(0).value;

for ( item in big_array ) {  // needs to skip first few items
  if ( item.value > least_found_value ) {
    small_array.remove(0);
    small_array.insert_sorted(item);
    least_found_value = small_array.get(0).value;
  }
}

small_array は Object[] にすることができ、実際に配列を削除して挿入する代わりに、スワップを使用して内側のループを実行できます。

于 2010-04-13T01:36:14.897 に答える