2017-01-10 20 views
0

このユースケースでは、コレクションのアイテム群をxに格納する必要があります。 xにアイテムを挿入したくない(重複していない)。私はまた、挿入の順序については気にしません。 xのサイズは大きく異なります(<は10個、10万に達します)。この場合、どのような種類のコレクションを使用しますか?

Setを使用することで重複はなく、注文ポイントはありませんが、xを作成して操作を実行すると、すべてのアイテムを効率的かつ迅速に繰り返し処理する必要があります。 Setは依然として最良の選択でしょうか?

Listには(重複を避けるために)各挿入の前の要素が含まれているか、Setのメンバーを繰り返し処理するのがより高価なのでしょうか?ベストプラクティス/効率性とコストに関するアドバイスは本当にありがとうございます。ありがとうございます。

+0

のような検索操作が 'List'と(1)' Map' 'で' Oに '' O(n)となります何かを行うことができます。あなたが要素の順序を気にせず、重複を望まないなら、 'Set'のために行くべきです。 'Set'を反復することは問題ではないはずです。あなたは' Iterator'または強化された 'for'ループを使ってそれを行うことができます。 – user2004685

+2

私は 'Set'にも投票し、**実証済み**あなたのアプリケーションで問題がない限り、パフォーマンスについては考えません。 –

答えて

1

Listに既に要素が含まれているかどうかを確認するのは非常に高価です。 Setオーバー

反復処理は少しListを反復処理よりも遅いが、大規模なので、唯一の一定の係数によって、Listの要素の封じ込めのためのチェックは要素ごとに線形時間がかかりますし、作るのに対し、全体のことは二次ではありません。

-1

xの構築後にxを構築するためにセットを使用すると、空間の複雑さを犠牲にして時間の複雑さを改善するために、内容を配列または他のタイプに単純にコピーできます。

1

アイテムがすでに存在するかどうかを素早く確認できるようにする必要がある場合は、HashSetが内部的にHashMapを使用しているので、必ずすべての参照がO(1)です。 このルックアップのリストは非常に高価ですが、すべての要素を1つずつチェックするためです。

すべての要素を繰り返し処理する必要がある場合は、ListとSetを使用しても違いはありません。

これは、HashSetがより多くのメモリを使用することに注意していますが、数十万は問題にならないはずです。

だから、HashSetはあなたのケースでは明らかに勝者です。

1

追加操作と削除操作がO(1)(ハッシュコードが均等に分散していると仮定)で実行されるため、LinkedHashSetを使用することをお勧めします。要素を追加/削除する場合はHashSetよりも効率が悪いかもしれませんが、多数の要素を追加した後に多くの要素が削除された場合は、より良い反復処理が必要です。

検索のためにO(n)を要求することは、一般的にこの場合は避けるべきことです。

0

データを重複しないようにマップに挿入し、マップをリストに変換することをおすすめします。

は、Java 8を使用している場合は、この

List<Object> result = map.entrySet().stream() 
      .map(x -> x.getKey()) 
      .collect(Collectors.toList()); 
関連する問題