16

List提供されたものに基づいて順序を維持する Javaの既存の実装はありComparatorますか?

次の方法で使用できるもの：

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

someTに従ってリスト内の順序が維持されるように挿入されますcmp

（@andersojの提案で、もう1つのリクエストで質問を完了しています）

また、要素を削除せずにソートされた順序でリストをトラバースできるようにしたい、つまり:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

通過する必要があります。

すべての提案は大歓迎です (Collections.sort順序付けされていない完全なリストで使用するように私に指示することを除いて) が、現時点で新しいライブラリを導入するのは難しいため、java.*最終的に何かを好むでしょう。org.apache.*

注: (UPDATE4)この種のリストの実装ではパフォーマンスが不十分になることに気付きました。2 つの一般的なアプローチがあります。

  1. Linked構造（一種の）Bツリーまたは類似のものを使用する
  2. 配列と挿入を使用する (二分探索あり)

いいえ 1. CPU キャッシュ ミスに問題があります。 いいえ 2. 配列内の要素のシフトに問題があります。

UPDATE2: TreeSet提供されたコンパレータ (MyComparator) を使用して等しいかどうかをチェックし、それに基づいて要素が等しいと仮定してそれらを除外するため、機能しません。「一意性」フィルタリングではなく、順序付けのためだけにそのコンパレータが必要です（自然な順序付けによる要素は等しくないため）

UPDATE3： 「ソート」された順序でトラバースする方法がないためPriorityQueue、（必要に応じて）機能しませんList

アップデート：

類似の質問:
Java のソート済みリストに適した Java の
ソート済み配列リスト

4

3 に答える 3

17

おそらくTreeSetを使用する必要があります。

要素は、使用されるコンストラクターに応じて、自然順序付けを使用するか、セットの作成時に提供される Comparator によって順序付けられます。

例：

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

これはセットであるため、重複したエントリは許可されないことに注意してください。これは、特定のユースケースで機能する場合と機能しない場合があります。

于 2012-05-20T17:09:20.443 に答える
9

新しい要求への対応。2 つの可能性があります。

  • JavaDoc forのPriorityQueue言うことをしてください：

    このクラスとその反復子は、 Collection および Iterator インターフェースのすべてのオプション メソッドを実装します。メソッドで提供される Iterator はiterator()、特定の順序で優先度キューの要素をトラバースすることが保証されていません。順序付けされたトラバーサルが必要な場合は、 の使用を検討してArrays.sort(pq.toArray())ください。

    これにより、要件を考えると最高のパフォーマンスが得られると思います。これが受け入れられない場合は、達成しようとしていることをよりよく説明する必要があります。

  • 新しい要素が追加されると自動的にソートされるリストを作成します。これは本当に痛いです...連結構造を使えば効率的な挿入ソートができますが、局所性が悪いです。配列に裏打ちされた構造を使用した場合、挿入ソートは面倒ですが、トラバーサルの方が優れています。反復/トラバーサルが頻繁に行われない場合は、リストの内容をソートせずに、オンデマンドでのみソートすることができます。

  • 私が提案したようにPriorityQueueの使用を検討し、順番に反復する必要がある場合は、ラッパー反復子を記述します。

    class PqIter implements Iterator<T>
{
   final PriorityQueue<T> pq;
   public PqIter(PriorityQueue <T> source)
   {
     pq = new PriorityQueue(source); 
   }

   @Override
   public boolean hasNext()
   {
     return pq.peek() != null
   }

   @Override
   public T next()
   { return pq.poll(); }

   @Override
   public void remove()
   { throw new UnsupportedOperationException(""); }
}

  • グァバを使用TreeMultiSet。次のコードをテストしましたIntegerが、正しいことをしているようです。

    import com.google.common.collect.TreeMultiset;

public class TreeMultiSetTest { 
  public static void main(String[] args) {
    TreeMultiset<Integer> ts = TreeMultiset.create();
    ts.add(1);  ts.add(0); ts.add(2);
    ts.add(-1); ts.add(5); ts.add(2);

    for (Integer i : ts) {
      System.out.println(i);
    } 
  } 
}

以下は、を使用したときに発生した一意性/フィルタリングの問題に対処していSortedSetます。イテレータも必要なようですが、これは機能しません。

本当に必要なものが順序付きリストのようなものである場合は、PriorityQueue. 

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

さまざまな操作の時間プロパティについて、API ドキュメントに記載されている内容に注意してください。

実装に関する注意: この実装は、エンキューおよびデキュー メソッド ( 、、および) にO(log(n))時間を提供します。およびメソッドの線形時間。検索方法 ( 、、および)の定数時間。offerpollremove()addremove(Object)contains(Object)peekelementsize

PriorityQueueによって生成されたイテレータは、期待どおりに動作しないことにも注意してください。

Iterator提供されたメソッドは、iterator()特定の順序でプライオリティ キューの要素をトラバースすることは保証されていません。順序付けされたトラバーサルが必要な場合は、 の使用を検討してArrays.sort(pq.toArray())ください。

Guava がMinMaxPriorityQueue. この実装は、JDK の で提供されるリンク形式ではなく、配列に基づくため、PriorityQueueタイミング動作が異なる可能性があります。パフォーマンスに敏感な何かをしている場合は、見てみたいと思うかもしれません。音符はわずかに異なる (線形および対数) big-O 時間を示しますが、これらすべての時間も制限されている必要があり、これは役立つ場合があります。

List順序付けを維持する実装自体はありませんが、探している可能性が高いのは の実装ですSortedSet。ATreeSetが最も一般的です。もう 1 つの実装である aConcurrentSkipListSetは、より具体的な用途向けです。SortedSetは順序付けを提供しますが、 のように重複エントリを許可しないことに注意してくださいList。

参照:

于 2012-05-20T17:09:58.993 に答える
-1

同様の問題があり、TreeSet の使用を考えています。「等しい」要素を除外しないようにするために、コンパレータを変更して、0 を返す代わりに (-1,1) の間の乱数を返すか、常に 1 を返すようにします。

Comparator を制御できない場合、または Comparator を別の目的で使用している場合、このソリューションを挿入してもうまくいきません。

于 2014-02-26T08:29:05.200 に答える