順序を維持するリストの実装

StackOverflow https://stackoverflow.com//questions/10675446

質問

既存のものはありますか 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.* 現時点では新しいライブラリを導入するのは難しいためです。

注記：(更新4) この種のリストの実装ではパフォーマンスが不十分であることがわかりました。一般的なアプローチは 2 つあります。

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

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

更新2: TreeSet 提供されたコンパレータ (MyComparator) 等価性をチェックし、それに基づいて要素が等しいと想定して除外します。このコンパレータは、「一意性」フィルタリングではなく、順序付けの目的でのみ必要です (要素の自然な順序付けが等しくないため)。

更新 3: PriorityQueue としては機能しません List （必要に応じて）「並べ替えられた」順序でそれを走査する方法がないため、並べ替えられた順序で要素を取得するには、コレクションから要素を削除する必要があります。

アップデート：

同様の質問:
Java に適したソートされたリスト
Javaのソートされた配列リスト

役に立ちましたか？

解決

新たな要件への対応。私は 2 つの可能性を感じています。

  • JavaDoc の目的を実行する PriorityQueue 言います：

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

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

  • を建てる リスト 新しい要素を追加すると自動的にソートされるだけです。これは本当に痛いです...リンク構造を使用した場合、効率的な挿入ソートを行うことができますが、局所性は悪くなります。配列ベースの構造を使用した場合、挿入ソートは面倒ですが、トラバーサルの方が優れています。反復/走査が頻繁でない場合は、リストの内容を並べ替えずに保持し、要求に応じてのみ並べ替えることもできます。

  • の使用を検討してください。 優先キュー 私が提案したように、順番に反復する必要がある場合は、ラッパー反復子を作成します。

    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)) エンキューおよびデキューメソッドの時間 (offer, poll, remove() そして add); 線形 の時間 remove(Object) そして contains(Object) メソッド。そして 絶え間ない 取得方法の時間 (peek, element, 、 そして size).

また、によって生成されるイテレータにも注意する必要があります。 PriorityQueue 期待どおりに行動しないでください。

の Iterator メソッドで提供される iterator() 優先キューの要素を特定の順序で走査することは保証されていません。順序付けられた走査が必要な場合は、使用を検討してください。 Arrays.sort(pq.toArray()).

グアバが提供していることに今気づきました。 MinMaxPriorityQueue. 。この実装は、JDK で提供されるリンクされたフォームではなく、配列に基づいています。 PriorityQueue, したがって、タイミング動作が異なる可能性があります。パフォーマンスを重視する作業を行っている場合は、検討してみるとよいでしょう。注では、big-O 時間がわずかに異なります (線形および対数) が、これらすべての時間も制限されている必要があり、これは役立つ可能性があります。

はありません List 実装自体は順序を維持しますが、おそらく探しているのは次の実装です。 SortedSet. 。あ TreeSet が最も一般的です。他の実装では、 ConcurrentSkipListSet より具体的な用途向けです。注意してください。 SortedSet は順序付けを提供しますが、重複エントリは許可されません。 List.

参照:

他のヒント

おそらく使用しているはずです ツリーセット:

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

例：

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

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

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

コンパレーターを制御できない場合、またはコンパレーターを挿入以外の目的で使用している場合、この解決策は機能しません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top