ArrayListJava では、 with アイテムを構築してから以下を呼び出すことができます。
Collections.sort(list, comparator);
リストの作成時に Comparator を渡す方法はありますTreeMapか?
目標は、リストに要素を追加できるようにすることであり、リストの末尾に自動的に追加する代わりに、リストは に基づいてソートされたままにComparatorなり、 によって決定されるインデックスに新しい要素を挿入しComparatorます。したがって、基本的に、新しい要素が追加されるたびにリストを再ソートする必要がある場合があります。
Comparatorこの方法で、または他の同様の手段でこれを達成する方法はありますか?
ArrayListの動作を変更できます
List<MyType> list = new ArrayList<MyType>() {
public boolean add(MyType mt) {
super.add(mt);
Collections.sort(list, comparator);
return true;
}
};
注：PriorityQueueはリストではありません。コレクションの種類を気にしない場合は、TreeMapと同じですがコレクションであるTreeSetを使用するのが最も簡単です。PriorityQueueの唯一の利点は、重複を許可することです。
注：大規模なコレクションの場合、再ソートはあまり効率的ではありません。バイナリ検索を使用してエントリを挿入する方が高速です。（しかしもっと複雑です）
編集：多くはあなたがするために「リスト」を必要とすることに依存します。ArrayList、LinkedList、PriorityQueue、TreeSet、またはその他の並べ替えられたコレクションの1つにListラッパーを記述し、実際に使用されるメソッドを実装することをお勧めします。そうすることで、コレクションの要件を十分に理解し、コレクションが正しく機能することを確認できます。
EDIT（2）：代わりにbinarySearchを使用することに非常に興味があったので。;）
List<MyType> list = new ArrayList<MyType>() {
public boolean add(MyType mt) {
int index = Collections.binarySearch(this, mt);
if (index < 0) index = ~index;
super.add(index, mt);
return true;
}
};
誰もが提案してPriorityQueueいます。ただし、a の内容を繰り返し処理PriorityQueueすると、要素がソートされた順序にならないことに注意してください。peek()メソッド、poll()などから「最小限の」要素を取得することのみが保証されます。
ATreeSetの方が似合いそうです。注意点は、 として、Set重複する要素を含めることはできず、インデックスを使用したランダム アクセスをサポートしていないことです。
SortedListJDK に実装がないのには、おそらく十分な理由があります。個人的には、JDK で自動ソートを 1 つ持つ理由が思い浮かびません。
時期尚早の最適化がうまくいかなかったのです。リストが挿入されるほど頻繁に読み取られない場合、理由もなく繰り返しソートするサイクルを無駄にしています。読み取りの直前にソートすると、はるかに反応的になりboolean、リストを読み取る前にソートする必要があるかどうかを示す場所があれば、さらに優れています。
Iterator問題は、 orfor eachループでリストをトラバースするときの順序だけを本当に気にすることです。そのためCollections.sort()、反復するコードの前に呼び出す方が、挿入のたびにリストを常にソートしたままにしようとするよりもおそらくパフォーマンスが向上します。
重複のためにあいまいさがありますがList、重複をどのように決定論的に順序付けますか? がありSortedSet、それは独自性のために理にかなっています。ただし、 a の並べ替えはList、重複の副作用や、すべてのオブジェクトを作成するなどのその他の制約から、より複雑になる可能性があります。Comparableまたは、コードで示すように、Comparator代わりに作業を実行できる a が必要です。
.add()自動ソートが役立つ非常に特別な状況がある場合、実装をListサブクラス化し、オーバーライドしてカスタムコンストラクターに渡すことを行うことができます。代わりに使用した理由は、そもそも自然な挿入ソート順です。また、常にソートしたい場合はかなり役に立たないインデックスを作成する機能もあります。これは、おそらく理想的ではない何らかの方法で処理する必要があります。Javadocによると;List.add()Collections.sort(this, comparator)LinkedListArrayListArrayListList.add()List
void add(int index, Object element)
指定された要素をこのリストの指定された位置に挿入します (オプションの操作)。
したがって、スローするだけでもかまいません。または、メソッドの JavaDoc で文書化する場合は、をUnSupportedOperationException無視しindexてデリゲートすることもできます。.add(Object element);
通常、多くの挿入/削除とソートが必要な場合LinkedListは、`List' を使用するとパフォーマンス特性が向上するため、 を使用します。
簡単な例を次に示します。
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
public class SortedList<E> extends LinkedList<E>
{
private Comparator<E> comparator;
public SortedList(final Comparator<E> comparator)
{
this.comparator = comparator;
}
/**
* this ignores the index and delegates to .add()
* so it will be sorted into the correct place immediately.
*/
@Override
public void add(int index, Object element)
{
this.add(element);
}
@Override
public boolean add(final E e)
{
final boolean result = super.add(e);
Collections.sort(this, this.comparator);
return result;
}
}
または、 を取得するときにのみソートすることもできますIterator。ソートされた順序が を反復処理するときにのみ重要である場合、これはよりパフォーマンス指向になりListます。これは、すべての反復の前に呼び出す必要のないクライアント コードのユース ケースをカバーし、Collections.sort()その動作をクラスにカプセル化します。
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
public class SortedList<E> extends LinkedList<E>
{
private Comparator<E> comparator;
public SortedList(final Comparator<E> comparator)
{
this.comparator = comparator;
}
@Override
public Iterator<E> iterator()
{
Collections.sort(this, this.comparator);
return super.iterator();
}
}
もちろん、エラーがComparatorあったnullかどうか、エラーが発生した場合にどうするかを確認するために、エラーのチェックと処理が必要になりますが、これでアイデアが得られます。重複を処理する決定論的な方法はまだありません。
Guava を使用している場合は、使用する必要があります。
Ordering.immutableSortedCopy()反復して完了する必要がある場合のみ。
より効率的なランダムアクセスを備えた TreeSet (または重複が必要な場合は TreeMultiset) のようなものは可能ですが、Java で実装されているとは思えません。ツリーの各ノードにその左側のサブツリーのサイズを記憶させることで、時間内にインデックスによって要素にアクセスできるようになりますO(log(size))。これは悪くありません。
これを実装するには、基になる TreeMap のかなりの部分を書き直す必要があります。
SortedSet と List の主な違いは次のとおりです。
自動ソートと（合理的な高速）インデックスアクセスの許可という、両方の融合が必要なようです。データのサイズと、インデックス付きの読み取りまたは新しい要素の追加が発生する頻度に応じて、これらは私の考えです:
いずれにせよ、SortedSet と List のインターフェイスとコントラクトは実際には互換性がないため、List 部分を読み取り専用 (または読み取りと削除専用) にして、設定と追加を許可せず、追加のオブジェクトを追加するためのオブジェクト (おそらく Collection インターフェースを実装)。
コモンズ-コレクションにはTreeBag
最初に提案PriorityQueueしましたが、その反復順序は定義されていないため、キューのクローンの先頭を空になるまで取得して反復しない限り、使用できません。
あなたはおそらく反復順序に関心があるので、私はあなたがiterator()メソッドをオーバーライドできると信じています：
public class OrderedIterationList<E> extends ArrayList<E> {
@Override
public Iterator<E> iterator() {
Object[] array = this.toArray(); // O(1)
Arrays.sort(array);
return Arrays.asList(array).iterator(); // asList - O(1)
}
}
ソートされたコレクションのスナップショットを保存しmodCount、コレクションが変更されていないかどうかを確認するために使用することで、これを改善できます。
ユースケースに応じて、これはPeterの提案よりも効率が悪い場合と高い場合があります。たとえば、複数のアイテムを追加して繰り返す場合です。（反復の間にアイテムを追加せずに）、これはより効率的かもしれません。
要素の追加/インデックス/削除/取得に O(n) 時間未満でソートされた構造を持つ唯一の方法は、ツリーを使用することです。その場合、操作は通常 O(log2n) を持ち、トラバースは O(1) のようになります。
O(n) は単なる連結リストです。
編集:バイナリ検索を使用してリンクされたリストに挿入します。バイナリ構造を使用せず、小さなサイズではない挿入操作の場合、これが最適です。
@Peter: O(log2n) の比較 (遅い) と挿入と O(n) の移動を伴うアルゴがあります。LinkedList をオーバーライドする必要がある場合は、そのままにしてください。しかし、それは可能な限りきちんとしています。簡単に理解できるように、アルゴリズムをできるだけきれいに保ちます。少し最適化することができます。
package t1;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
public class SortedList {
private static <T> int binarySearch(ListIterator<? extends Comparable<? super T>> i, T key){
int low = 0;
int high= i.previousIndex();
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid;
}
return -(low + 1); // key not found
}
private static <T> T get(ListIterator<? extends T> i, int index) {
T obj = null;
int pos = i.nextIndex();
if (pos <= index) {
do {
obj = i.next();
} while (pos++ < index);
} else {
do {
obj = i.previous();
} while (--pos > index);
}
return obj;
}
private static void move(ListIterator<?> i, int index) {
int pos = i.nextIndex();
if (pos==index)
return;
if (pos < index) {
do {
i.next();
} while (++pos < index);
}
else {
do {
i.previous();
} while (--pos > index);
}
}
@SuppressWarnings("unchecked")
static <T> int insert(List<? extends Comparable<? super T>> list, T key){
ListIterator<? extends Comparable<? super T>> i= list.listIterator(list.size());
int idx = binarySearch(i, key);
if (idx<0){
idx=~idx;
}
move(i, idx);
((ListIterator<T>)i).add(key);
return i.nextIndex()-1;
}
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<Integer>();
LinkedList<Integer> unsorted = new LinkedList<Integer>();
Random r =new Random(11);
for (int i=0;i<33;i++){
Integer n = r.nextInt(17);
insert(list, n);
unsorted.add(n);
}
System.out.println(" sorted: "+list);
System.out.println("unsorted: "+unsorted);
}
また、これが Java 標準ライブラリーに存在しないことにも驚かされます。(しかし、JDK チームに新しいクラスの追加を提案できたことを幸運に思います! 私はそれで運が良かったことはありません。)
関数が適切な推移的な関係であると仮定すると、compareToこれに対する最速のアルゴリズムは (リストが書き込まれた回数とほぼ同じ回数読み取られると仮定して) List.add、バイナリ検索を実行して new の挿入ポイントを見つけるメソッドでオーバーライドすることです。挿入前のアイテム。これは追加要素数で O(log(N)) です。
同様の問題に直面しているときに作成したindexed-tree-mapを検討してください。インデックスで要素にアクセスし、並べ替え順序を維持しながら要素のインデックスを取得できます。重複は、同じキーの下の値として配列に入れることができます。
java.util.List明らかな解決策は、インターフェイスを実装Comparatorし、コンストラクターへの引数としてa を取る独自のクラスを作成することです。適切な場所でコンパレータを使用します。つまり、addメソッドは既存のアイテムを繰り返し処理し、新しいアイテムを適切な場所に挿入します。などのメソッドの呼び出しを禁止add(int index, Object obj)します。
実際、誰かがすでにこれを作成している必要があります... Google で簡単に検索すると、少なくとも 1 つの例が見つかります。
http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html
ListIterator インターフェースのコントラクトは少し面倒ですが、このメソッドはリストの 1 回のスキャン (挿入ポイントまで) を使用して挿入を実行します。
private void add(Integer value) {
ListIterator<Integer> listIterator = list.listIterator();
Integer next = null;
while (listIterator.hasNext()) {
next = listIterator.next();
if (next.compareTo(value) > 0) {
break;
}
}
if (next == null || next.compareTo(value) < 0) {
listIterator.add(value);
} else {
listIterator.set(value);
listIterator.add(next);
}
}
これを行う最善の方法は、リストの add 実装をオーバーライドすることです。LinkedList を使用すると、効率的な挿入が可能になるため、これを実演します。
public boolean add(Integer e)
{
int i = 0;
for (Iterator<Integer> it = this.iterator(); it.hasNext();)
{
int current = it.next();
if(current > e)
{
super.add(i, e);
return true;
}
i++;
}
return super.add(e);
}
上記のコードは、常にソートされる整数のソート済みリストを作成します。他のデータ型で動作するように簡単に変更できます。ただし、ここでは関数の使用を避ける必要がありますadd(index, value)。これは、明らかに並べ替えを壊してしまうからです。
上記の人々は Arrays.sort() を使用することを提案しましたが、特にリストに追加するたびにソートメソッドを呼び出す必要があるため、効率が大幅に低下する可能性があるため、私はそれを避けます。
私は優先キューがその仕事をするだろうと信じています。
警告（同じドキュメントページから）：
このクラスとそのイテレータは、およびIteratorインターフェイスのすべてのオプションメソッドを 実装します。提供されたメソッド は
Collection、特定の順序でプライオリティキューの要素をトラバースすることが保証されていません。順序付きトラバーサルが必要な場合は、の使用を検討して ください。Iteratoriterator()Arrays.sort(pq.toArray())