1

サンプルとして、SortedSetインターフェースを実装する単純なMySortedSetをJavaで開発しています。これは、E[]配列である単純な配列でバックアップされます。

それに関していくつか質問があります：

これはクラスです:(私は関連する部分ではなく、コード全体を書いているわけではありません）

public class MySortedSet<E> implements SortedSet<E>, Iterator<E> {

 private E[] array;
 private Comparator<? super E> _comparator;
 private int size = 0;
 private int capacity;

 @SuppressWarnings("unchecked")
 public MySortedSet() {
    this.capacity = 10;
    this.array = (E[]) new Object[this.capacity];
    // this.array = Array.newInstance(Class<E> var,int size);
    // We have to get Class<E> from outside caller.
 }
}

質問3：これはソートされたセットであり、要素がソートされていると想定されているため、コンストラクターの説明があります。

このコンストラクターを使用してソートされたセットを作成する場合、要素は自然な順序付けを使用して順序付けられていると見なされます（つまり、EはComparableを実装します）。

2つの異なるコンストラクターを取得します。1つはパラメータなしで、もう1つは受け入れてComparator<? super E>います。

public MySortedSet() {
    this.capacity = 10;
    this.array = (E[]) new Object[this.capacity];
    // this.array = Array.newInstance(Class<E> var,int size);
    // We have to get Class<E> from outside caller.
}

public MySortedSet(Comparator<? super E> comparator) {
    this._comparator = comparator;
}

渡されない場合は、自然な順序を使用する必要がありますが、メソッドにアクセスするために何らかの方法でcomparator取得する必要があるため、それをどのように実行するかはよくわかりません。各要素を並べ替えるメソッドを比較しながら呼び出すことができるように、呼び出す方法を教えてください。Comparatorcomparesort

コード全体を見たい人は、次のアドレスを参照してください：http ://codepaste.net/4ucvsw完璧ではありませんが、私はそれに取り組んでいます。

質問4：コードガイドによると：

特定のアイテムを検索する最も速い方法はバイナリ検索を使用することであるため、コレクション内のアイテムが常にソートされた順序になっていることを確認する必要があります。これは、見た目ほど難しくはありません。新しいアイテムを挿入するとき、それを挿入している配列はすでにソートされていると想定できます。したがって、必要なのは、新しいアイテムが属する配列内の位置を見つけ、新しいアイテムよりも大きいものをすべて1スロット右にシフトして、新しいアイテムを挿入することです。これは挿入ソートと呼ばれます。

これがsortメソッドロジックです。新しいアイテムがどこに属するかを見つけるために二分探索を行う必要があるので、その場所に新しいアイテムを挿入し、もう1つのスロットを右に移動できます。

しかし、何を見つける必要があるのか​​よくわからないので、ここで二分探索がどのように機能するかはよくわかりません。見つけるアイテムではなく、追加するアイテムが与えられます。代わりに、各要素を追加する必要のある要素と比較し、最後の小さくて最初に大きいアイテムを見つけたら、最初の大きいアイテムのインデックスを取得し、それらを右に移動して、インデックスに新しいアイテムを追加します。 。

4

2 に答える 2

1

回答3：

「自然順序付け」とは、要素をComparable使用せずに比較できるように要素を実装する必要があることを意味しComparatorます。呼び出し元にComparable要素と要素のどちらかを選択Comparatorさせる際の注意点は、コンパイル時のチェックを実行して、要素がこれらの要件の少なくとも1つを満たしていることを確認できないことです。

JavaTreeSetも同様に、をとらないコンストラクターとそうでないコンストラクターを公開しComparatorます。TreeSetのコントラクトは、基本的に、作成時にaを指定しなかった場合にClassCastException、ではない要素を挿入しようとした場合にをスローすることです。この戦略を使用するか、別の戦略を使用するかはあなた次第です。ComparableTreeSetComparator

回答4：

Arrays.binarySearch(Object[], Object)見積もりの​​戦略に基づいて、この正確な目的に使用できるはずです。そのメソッドのドキュメントから：

戻り値：検索キーのインデックス（配列に含まれている場合）。それ以外の場合、(-(insertion point) - 1)。挿入ポイントは、キーが配列に挿入されるポイントとして定義されます。つまり、キーよりも大きい最初の要素のインデックス、またはa.length配列内のすべての要素が指定されたキーよりも小さい場合です。これにより、キーが見つかった場合にのみ、戻り値が0以上になることが保証されることに注意してください。

于 2012-05-28T02:38:29.080 に答える
1

質問3：

実際には、すべてのコレクションは、で暗黙的に定義されている事前定義されたコンパレータで機能するEため、型パラメータを具体化するために使用されるすべてのクラスはであるE必要がありimplement Comparable<E>ます。自然順を探している比較方法はその方法です

int compareTo(E other)

これは、データ構造で使用するクラスによって実装する必要があります。あなたの仕事はあなたのコレクションで使用されるクラスの定義に関係しているのではなく、あなたがそれをするために何をしようとしているのかということだけです。

public class MySortedSet<E> ... {
    private Comparator<? super E> _comparator;

    public int innerCompare(E e1, E e2)
    {
      if (_comparator != null)
        return _comparator.compare(e1,e2);
      else
        return e1.compareTo(e2);
    }

    ...

提供されている場合はカスタムコンパレータを使用し、そうでない場合は自然なコンパレータを使用するようにします。

ComparableとはどちらもComparator同じ原則に従って機能しますが、名前が示すように、最初の1つはデータクラスに関連付けられているため、自然なコンパレータになります。代わりに後者が使用されます。これは、自然な順序に従って異なる方法で並べ替えられる要素を並べ替えるカスタム方法を定義できるためです。

質問4：

つまり、ソートされた配列があると仮定すると、挿入するたびにこの制約を有効に保つ必要があり、アイテムを検索するときにバイナリ検索を実行できるようになります。

要素を正しいインデックス（追加する必要のあるアイテム）に配置することに集中する必要があります。要素の検索に関連するステートメントの部分は、次のように解釈する必要があります。

配列の並べ替えを維持する場合は、追加するすべての要素が正しい位置に配置されるようにすることで実行できます（たとえば、挿入並べ替えを使用）。要素がに含まれているかどうかを確認するときに、配列にバイナリ検索を適用できます。セット。

これは、配列が並べ替えられている場合、配列のセクションの中央の要素を見ると、別の要素が実際にリストに含まれているかどうかを確認するために常に正しい方向を指していることを確認できるためです。

例えば：

1, 2, 6, 11, 21, 30, 45

2をチェックする必要があります。インデックスsize()/2 = 3で要素を取得できます。これは11です。配列がソートされていることをすでに知っているので2 < 11、左半分などで同じことを再帰的に実行できます。

于 2012-05-28T02:41:12.353 に答える