2

私は現在、主に楽しみのために、Java でさまざまな並べ替えアルゴリズムを実装して遊んでいますが、それを「正しく」実行する方法に苦労しています。つまり、s int、longs、Strings、booleans (実際には、これらは Java で比較可能ですか?)、独自のクラスなど、比較可能なものに対して選択した並べ替えアルゴリズムをユーザーが呼び出すことができるようにしたいと考えています。なんでもいい。問題は、これをどのように行うかです。

クラスを使用して並べ替えアルゴリズムを表すことを考えていたため、汎用リストなどを使用して並べ替え対象を内部に格納することを考えていました ( List<E>)。これにより、複数のコンストラクターを使用できるようになり、ユーザーがさまざまな形式 (リスト、配列など) でデータを渡すことができるようになります。これは正しい方法ですか？私の現在の問題は、ユーザーが何かをソートしたいときにクラスを作成する必要がないようにしたいということSystem.out.printlnです。

// Example:

int[] myInts = {5,4,3,2,1};

// This is what I do *not* want.
InsertionSort mySort = new InsertionSort();
int[] sortedInts = mySort.sort(myInts);

// This is more like what I want.
int[] sortedInts = Sorting.insertionSort(myInts);

基本的な質問のように思えるかもしれませんが、プログラミング言語で自分のやり方を学んでいるだけです。夏の仕事のためにソフトウェア会社で働く 2 年生のコンピューティングの学生にとって、これは少しばかげていますが、私の仕事のほとんどにプログラミングの知識がほとんど必要ないことに驚かれることでしょう...それは通常、より多くのデザインの知識です。

編集：

明確にするために、私の3つの主な質問は次のとおりです。

  • ソートを行うクラスをユーザーに作成してもらうのと、ユーザーがインポートするクラスに静的メソッドを作成させるのとではどちらがよいでしょうか?
  • プリミティブ データ型とジェネリック オブジェクトの両方を簡単に処理できますか? 同等の（または同様に）実装する汎用オブジェクトを処理できるようにしたいので、これによりプリミティブに問題が発生します（何も実装しないため;））。
  • 一般的な入力を処理する最良の方法は何ですか?並べ替えを試みる前に何をチェックすればよいですか (たとえば、Comparable を実装するなど)?
4

4 に答える 4

1

あなた自身の質問に答えたと思いますか？ユーザーがインスタンス メソッドを作成してオブジェクトを作成し、呼び出すのではなく、静的メソッドを公開する場合は、それを実行します。Sorting.insertionSort()私にはうまく見えます。

内部的には、好きなものにディスパッチできます。内部では、これをクラスやポリモーフィズムなどで実装したい場合は、先に進んでください。しかし、それは少しやり過ぎのように思えます。ここで継承とポリモーフィズムが大いに役立つかどうかはわかりません。

于 2010-07-20T09:55:37.210 に答える
1

ソート アルゴリズムを実装する通常の方法は、静的メソッドを実装することです。たとえば、Arrays.sort() のソース コードを見てください。このメソッドは、さまざまなパラメーター タイプのさまざまな実装でオーバーロードできます (たとえば、同等のものを実装するオブジェクト、独自のコンパレーターを提供するオブジェクト、プリミティブ配列など)。

ここに私が以前に書いたものがあります：

public static <T> void swap(T[] a, int x, int y) {
    T t=a[x];
    a[x]=a[y];
    a[y]=t;
}

public static <T extends Comparable<? super T>> void mergeInOrder(T[] src, T[] dst, int p1, int p2, int p3, int p4) {
    if (src[p2].compareTo(src[p3])<=0) return; // already sorted!

    // cut away ends
    while (src[p1].compareTo(src[p3])<=0) p1++;
    while (src[p2].compareTo(src[p4])<=0) p4--;

    int i1=p1;
    int i3=p3;
    int di=p1;
    while(di<p4) {
        if (src[i1].compareTo(src[i3])<=0) {
            dst[di++]=src[i1++];
        } else {
            dst[di++]=src[i3++];
            if (i3>p4) {
                System.arraycopy(src,i1,dst,di,p2-i1+1);
                break;
            }
        }
    }

    System.arraycopy(dst, p1, src, p1, (p4-p1)+1);
}

public static <T extends Comparable<? super T>> void mergeSort(T[] src, T[] dst, int start, int end) {
    if (start+1>=end) {
        if (start>=end) return;
        if (src[start].compareTo(src[end])>0) {
            swap(src,start,end);
        }
        return;
    }

    int middle=(start+end)/2;
    mergeSort(src,dst,start, middle);
    mergeSort(src,dst,middle+1, end);
    mergeInOrder(src,dst,start,middle,middle+1,end);
}

private static ThreadLocal<Comparable<?>[]> mergeSortTemp=new ThreadLocal<Comparable<?>[]>();

@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] src) {
    int length=src.length;
    Comparable<?>[] temp=mergeSortTemp.get();
    if ((temp==null)||(temp.length<length)) {
        temp=new Comparable[length*3/2];
        mergeSortTemp.set(temp);
    }
    mergeSort(src,(T[])temp,0,length-1);
}

ただし、独自のインスタンスを生成するクラスとして並べ替えアルゴリズムを実装する正当な理由が 2 つ考えられます。

  • これにより、ソート アルゴリズムのインスタンスをポリモーフィックに渡すことができます。たとえば、ソート アルゴリズムのコレクションを作成していて、それらに対して多くのベンチマークを実行したい場合などに便利です。
  • ソーター インスタンスでプライベートな状態を保持できます。これは、一時ストレージ用に事前に割り当てられた配列を使用するなど、一部の並べ替えアルゴリズムに役立ちます。また、異なるものを同時に使用できるようにしたい場合は、クラス インスタンスに配置するのが理にかなっています。複数のスレッドからインスタンスを並べ替える - 静的メソッドの実装には何らかの形式の同期が必要です (たとえば、上記のコードでの ThreadLocal の使用を参照してください)。
于 2010-07-20T12:07:01.387 に答える
1

binarySearch 操作を提供する方法を例として挙げることができますCollections...そして実際、

int[] sortedInts = Sorting.insertionSort(myInts);

私が個人的に好むとはいえ、よりJavaの方法です

public class Sorting {
     public static <DataType extends Comparable> Iterable<DataType> insertionSort(Iterable<DataType> data);
}
  • <DataType>出力データが入力と同じ型であることを確認する
  • Iterable<DataType>最大限の互換性を確保するために、データ入力データはイテラブルです。明らかに、List を使用すると、内部アイテムの並べ替えが可能になるため、非常に簡単です。ただし、 iterable を使用すると、このメソッドの実装者がリストを変更するためにリストを再作成する必要があり、入力リストが変更されず、出力リストが別のものになることが保証されます。

あなたがあなたの質問を編集しているのを見たので、一点一点返信させてください (その後、回答を選択することを検討してください。既存の質問を際限なく編集するよりも、新しい質問を追加する方が簡単だからです。質問をコミュニティ ウィキにしない限り、この返信のように）

ソートを行うクラスをユーザーに作成してもらうのと、ユーザーがインポートするクラスに静的メソッドを作成させるのとではどちらがよいでしょうか?

私の考えでは、この場合は静的メソッドを使用することをお勧めします。ここでは、作成していないオブジェクトを非常に「基本的な」方法で操作する必要があるためです。

プリミティブ データ型とジェネリック オブジェクトの両方を簡単に処理できますか? 実装する（または同様に）汎用オブジェクトを処理できるようにしたいのでComparable、これによりプリミティブに問題が発生します（何も実装しないため;））。

オートボクシングについて聞いたことがありますか？これは、プライマリ タイプをオブジェクトの「等価物」にする Java 5 の機能です。つまり、int は自動的に Integer に変換され、ご存知のように Comparable を実装しています。

一般的な入力を処理する最良の方法は何ですか?並べ替えを試みる前に何をチェックすればよいですか (たとえば、Comparable を実装するなど)?

私のメソッド宣言 ( ) により、入力データが Comparable を実装しているかどうかのチェックは、ユーザーではなく Java コンパイラーによって行われることに注意してください。これにより、IDE が間違いを示すことができます。

于 2010-07-20T09:10:24.553 に答える
0

これがあなたが苦労しているものかどうかはわかりません...しかし、参照型と（実際の）プリミティブ型の両方で機能するアルゴリズムを実装することはほとんど不可能です. Objectその理由は、Java 型システムには、プリミティブ型とサブタイプを持つ概念的なユニバーサル型がないためです。

これに対する通常の回避策は、対応するラッパー クラスを使用してプリミティブ型をラップすることです。たとえばInteger、 for int、Booleanforboolなど。これにより、(たとえば) anyCollection<T>または anyの並べ替えアルゴリズムを実装できます<T>[]。

このアプローチには、（たとえば）整数の大きな配列に適用すると、パフォーマンス/メモリ使用量の問題があります。パフォーマンス ヒットを使用するか、アルゴリズムとそのサポート クラスをプリミティブ型ごとに個別に実装します。

(インターフェイスで実際の要素の型を公開しない方法で、配列要素のペアの比較と配列要素のペアの交換を抽象化することが可能であるため、ほとんど不可能だと言いました。たとえば、

public interface ArraySortAdapter {
  public abstract int compareElements(Object array, int pos1, int pos2);
  public abstract void swapElements(Object array, int pos1, int pos2);
}

さまざまな配列タイプにさまざまな実装を提供します。例えば

public class IntArraySortAdapter implements ArraySortAdapter {
  public int compareElements(Object array, int pos1, int pos2) {
      int[] intArray = (int[]) array;
      if (intArray[pos1] < intArray[pos2]) {
          return -1;
      } else if (intArray[pos1] > intArray[pos2]) {
          return +1;
      } else {
          return 0;
      }
  }

  ...
}

ただし、控えめに言っても、これは面倒で非効率的です...）

于 2010-07-20T09:58:26.980 に答える