-4

10700レコードを取得しました。できるだけ速く並べ替える必要があります。並べ替えアルゴリズムの種類について読んでいますが、迷子になりました。何を選択するのが最適かわかりませんでした：http: //en.wikipedia.org/wiki/Sorting_algorithm

編集1：アルゴリズムの実行時間を計算するコードを書き留める必要があります

編集1-2：並べ替えと並べ替えの時間を計算する機能を備えた言語はありますか？

そしてもう1つの質問は、アルゴリズムの実装に使用される言語が速度に影響を与えるということです。（たとえば、c ++を使用した場合、javaまたは.Net langよりも高速になりますか??）

これは在宅勤務ではないことに注意してください。

4

3 に答える 3

4

これが宿題の問題でない限り、独自の並べ替えアルゴリズムを実装しないでください。

開発環境ですでに提供されているものを使用してください。堅牢でデバッグされており、自分で作成するものよりもほぼ確実に高速です。

FWIW、.NETのSort()上のメソッドはQuickSortを使用します。List<T>

実際の環境（C ++対.NET対Java）は、非常に少量のメモリでこれを実行しない限り、無視できるほどの影響しか与えません。経験のあるものは何でも使用してください。

于 2011-08-28T08:22:23.090 に答える
2

Javaのこのコードのチャンクは、あなたが求めている数字の少なくともいくつかをどのように決定できるかを示しています。

public class Main {

    private static long test (double[] tosort) {
        Date begin = new Date();
        Arrays.sort(tosort);
        Date end = new Date();
        return end.getTime() - begin.getTime();
    }

    public static void main(String[] args) {
        double[] tosort = new double[10700];

        for (int jj=0;jj<10;jj++) {
            for (int ii=0;ii<tosort.length;ii++) {
                tosort[ii] = Math.random();
            }
            System.out.println("Random data " + test(tosort));
        }

        for (int jj=0;jj<10;jj++) {
            for (int ii=0;ii<tosort.length;ii++) {
                tosort[ii] = ii;
            }
            System.out.println("Presorted data " + test(tosort));
        }

        for (int jj=0;jj<10;jj++) {
            for (int ii=0;ii<tosort.length;ii++) {
                tosort[ii] = tosort.length - ii;
            }
            System.out.println("Inverted data " + test(tosort));
        }

    }

}

Fyi、コードが実行されるたびに実行されたコンピューターだけが、並べ替えルーチンに費やされる1ミリ秒未満にとどまりました。意味のあるデータを取得するには、データサイズを100倍に増やす必要がありました。

  • このコードは、コンパレータコードに必要な時間などを完全に抽象化します（要素はプリミティブダブルであり、他のオブジェクトの比較にはおそらくはるかに長い時間がかかります）
  • ジャストインタイムコンパイラがコードを理解したら、それも少し速くなるはずです
  • 代替の並べ替えアルゴリズムを使用してテスト実行を簡単に追加し、それらがどのように動作するかを確認できます

これらの数値は、ハードウェアの機能、入力データタイプ、コンピューターの負荷などによって異なりますが、少なくとも何が期待できるかを感じることができます。

于 2011-08-28T09:06:54.457 に答える
1

アルゴリズムを実装する必要はありません（これが宿題でない限り）。すべての言語にはソート機能があり、非常に効率的です。たとえば、C ++ではstd::sort、多くの実装でクイックソート（および要素数が少ない場合は挿入ソート）を使用するものを使用します。

于 2011-08-28T08:22:46.330 に答える