16

どちらの実装が「重く」ありませんか: PriorityQueue または並べ替えられた LinkedList (コンパレーターを使用)?

すべての商品を揃えたい。挿入は非常に頻繁に行われ、場合によってはすべてのリストを実行していくつかの操作を行う必要があります。

4

11 に答える 11

32

ALinkedListは最悪の選択です。ArrayList（または、より一般的にはRandomAccess実装者）、またはを使用しPriorityQueueます。リストを使用する場合は、すべての挿入後ではなく、内容を反復処理する前にのみリストをソートしてください。

注意すべきことの1つは、PriorityQueueイテレータが要素を順番に提供しないことです。要素を順番に繰り返すには、実際には要素を削除する（キューを空にする）必要があります。

于 2010-05-20T22:01:29.727 に答える
5

両方を実装してから、実際のデータでパフォーマンス テストを行い、特定の状況でどちらが最適かを確認する必要があります。

于 2010-05-20T21:52:26.863 に答える
3

この問題について小さなベンチマークを作成しました。すべての挿入の終了後にリストをソートしたい場合は、 と の間にほとんど違いはありませんPriorityQueue(LinkedList私のマシンでは LinkedList の方が 5 ～ 10 パーセント高速です)。ただし、ArrayList を使用すると、ほぼ 2 になります。 PriorityQueue よりも数倍速いソート。

リストのベンチマークでは、値を入力してからソートが終了するまでの時間を測定しました。PriorityQueue の場合 - 充填の開始からすべての要素のポーリングの終了まで (エリクソンの回答に記載されているように、削除中に要素が PriorityQueue で順序付けられるため)

于 2012-10-18T21:53:37.963 に答える
2

を使用する場合はLinkedList、アイテムを追加するたびにアイテムを再配置する必要があります。また、挿入が頻繁に行われるため、を使用しませんLinkedList。したがって、この場合はPriorityQueue'sを使用します。リストに一意の要素のみを追加する場合は、SortedSet（1つの実装はTreeSet）を使用することをお勧めします。

于 2010-05-20T21:57:06.727 に答える
1

2つのデータ構造には根本的な違いがあり、思ったほど簡単に交換することはできません。

PriorityQueueのドキュメントによると：

メソッドiterator（）で提供されるイテレータは、特定の順序で優先キューの要素をトラバースすることが保証されていません。

ArrayListを使用し、リストを反復処理する前にのみ、その上でCollections.sort（）を呼び出します。

于 2010-05-20T22:11:10.407 に答える
1

問題PriorityQueueは、要素を順番に取得するためにキューを空にする必要があることです。それがあなたの望むものなら、それは素晴らしい選択です。それ以外の場合はArrayList、ソートされた結果が必要な場合にのみソートする を使用できます。または、項目が (コンパレーターに対して) 異なる場合はTreeSet. TreeSetとはどちらもArrayList、スペースに関してはそれほど「重く」ありません。どちらが速いかは、ユースケースによって異なります。

于 2010-05-20T22:18:10.323 に答える
0

常にソートする必要がありますか？その場合は、ツリーセット（または高速ルックアップを備えた他のSortedSet）のようなものを使用することをお勧めします。

たまにしか並べ替える必要がない場合は、リンクリストを使用して、アクセスが必要なときに並べ替えてください。アクセスする必要がない場合は、並べ替えを解除します。

于 2010-05-20T21:58:02.090 に答える
0

java.util.PriorityQueueは

「優先度ヒープに基づく無制限の優先度キュー」

。ヒープデータ構造は、リンクリストよりもはるかに理にかなっています

于 2010-05-20T22:00:01.773 に答える
0

私は2つのオプションを見ることができますが、どちらがより良いのは、重複するアイテムを持つことができる必要があるかどうかによって異なります。

リストに重複するアイテムを保持する必要がない場合は、SortedSet（おそらくTreeSet）を使用します。

重複するアイテムを維持する必要がある場合は、LinkedListを使用して、新しいアイテムを正しい順序でリストに挿入します。

操作を行うたびにアイテムを削除したい場合を除いて、PriorityQueueは実際には適合しません。

他の人たちと一緒に、プロファイリングを使用して、特定の問題に対する正しい解決策を選択していることを確認してください。

于 2010-06-05T19:24:06.270 に答える
-1

IMHO: LinkedList がある場合、PriorityQueue は必要ありません。LinkedList を使用すると、PriorityQueue を使用するよりも速くキューを並べ替えることができます。例えば

Queue list = new PriorityQueue();
list.add("1");
list.add("3");
list.add("2");
while(list.size() > 0) {
    String s = list.poll().toString();
    System.out.println(s);
}

このコードは長すぎると思います。要素を追加するたびに要素がソートされるためです。しかし、次のコードを使用する場合:

Queue list = new LinkedList();
list.add("1");
list.add("3");
list.add("2");
List lst = (List)list;
Collections.sort(lst);
while(list.size() > 0) {
    String s = list.poll().toString();
    System.out.println(s);
}

このコードは一度だけソートし、PriorityQueue を使用するよりも高速になると思います。そのため、LinkedList を使用する前に一度並べ替えることができれば、いずれにしてもより高速に動作します。また、PriorityQueue が本当に必要ないのと同じようにソートされたとしても、このクラスは本当に必要ありません。

于 2016-07-18T15:39:54.597 に答える