6

私は（Javaで）挿入ソート、マージソート、ModifiedMergeSort、クイックソートを実装しました：

ModifiedMergeSortには、要素の「バインド」用の変数があります。並べ替える要素が「バインド」以下の場合は、挿入ソートを使用して並べ替えます。

バージョン1がバージョン3、4、5よりも優れているのはなぜですか？

バージョン2と6の結果は現実的ですか？

これが私の結果です（ミリ秒単位）：

Version 1 - Insertion Sort: Run-Times over 50 test runs
Input Size      Best-Case       Worst-Case      Average-Case
N = 10000       14              19              14.96
N = 20000       59              60              59.3
N = 40000       234             277             243.1

Version 2 - Merge Sort: Run-Times over 50 test runs
Input Size      Best-Case       Worst-Case      Average-Case
N = 10000       1               15              1.78
N = 20000       3               8               3.4
N = 40000       6               9               6.7

Version 3 - Merge Sort and Insertion Sort on 15 elements: Run-Times over 50 test runs
Input Size      Best-Case       Worst-Case      Average-Case
N = 10000       41              52              45.42
N = 20000       170             176             170.56
N = 40000       712             823             728.08

Version 4 - Merge Sort and Insertion Sort on 30 elements: Run-Times over 50 test runs
Input Size      Best-Case       Worst-Case      Average-Case
N = 10000       27              33              28.04
N = 20000       113             119             114.36
N = 40000       436             497             444.2

Version 5 - Merge Sort and Insertion Sort on 45 elements: Run-Times over 50 test runs
Input Size      Best-Case       Worst-Case      Average-Case
N = 10000       20              21              20.68
N = 20000       79              82              79.7
N = 40000       321             383             325.64

Version 6 - Quick Sort: Run-Times over 50 test runs
Input Size      Best-Case       Worst-Case      Average-Case
N = 10000       1               9               1.18
N = 20000       2               3               2.06
N = 40000       4               5               4.26

これが私のコードです：

package com.testing;

import com.sorting.InsertionSort;
import com.sorting.MergeSort;
import com.sorting.ModifiedMergeSort;
import com.sorting.RandomizedQuickSort;

/**
 *
 * @author mih1406
 */
public class Main {
    private static final int R = 50; // # of tests
    private static int N = 0; // Input size
    private static int[] array; // Tests array
    private static int[] temp; // Tests array

    private static long InsertionSort_best = -1;
    private static long InsertionSort_worst = -1;
    private static double InsertionSort_average = -1.0;

    private static long MergeSort_best = -1;
    private static long MergeSort_worst = -1;
    private static double MergeSort_average = -1.0;

    private static long ModifiedMergeSort_V3_best = -1;
    private static long ModifiedMergeSort_V3_worst = -1;
    private static double ModifiedMergeSort_V3_average = -1.0;

    private static long ModifiedMergeSort_V4_best = -1;
    private static long ModifiedMergeSort_V4_worst = -1;
    private static double ModifiedMergeSort_V4_average = -1.0;

    private static long ModifiedMergeSort_V5_best = -1;
    private static long ModifiedMergeSort_V5_worst = -1;
    private static double ModifiedMergeSort_V5_average = -1.0;

    private static long RandomizedQuickSort_best = -1;
    private static long RandomizedQuickSort_worst = -1;
    private static double RandomizedQuickSort_average = -1.0;


    public static void main(String args[]) {
        StringBuilder InsertionSort_text = new StringBuilder(
                "Version 1 - Insertion Sort: Run-Times over 50 test runs\n");

        StringBuilder MergeSort_text = new StringBuilder(
                "Version 2 - Merge Sort: Run-Times over 50 test runs\n");

        StringBuilder ModifiedMergeSort_V3_text = new StringBuilder(
                "Version 3 - Merge Sort and Insertion Sort on 15 elements: Run-Times over 50 test runs\n");

        StringBuilder ModifiedMergeSort_V4_text = new StringBuilder(
                "Version 4 - Merge Sort and Insertion Sort on 30 elements: Run-Times over 50 test runs\n");

        StringBuilder ModifiedMergeSort_V5_text = new StringBuilder(
                "Version 5 - Merge Sort and Insertion Sort on 45 elements: Run-Times over 50 test runs\n");

        StringBuilder RandomizedQuickSort_text = new StringBuilder(
                "Version 6 - Quick Sort: Run-Times over 50 test runs\n");

        InsertionSort_text.append("Input Size\t\t"
                + "Best-Case\t\tWorst-Case\t\tAverage-Case\n");

        MergeSort_text.append("Input Size\t\t"
                + "Best-Case\t\tWorst-Case\t\tAverage-Case\n");

        ModifiedMergeSort_V3_text.append("Input Size\t\t"
                + "Best-Case\t\tWorst-Case\t\tAverage-Case\n");

        ModifiedMergeSort_V4_text.append("Input Size\t\t"
                + "Best-Case\t\tWorst-Case\t\tAverage-Case\n");

        ModifiedMergeSort_V5_text.append("Input Size\t\t"
                + "Best-Case\t\tWorst-Case\t\tAverage-Case\n");

        RandomizedQuickSort_text.append("Input Size\t\t"
                + "Best-Case\t\tWorst-Case\t\tAverage-Case\n");

        // Case N = 10000
        N = 10000;
        fillArray();
        testing_InsertionSort();
        testing_MergeSort();
        testing_ModifiedMergeSort(15);
        testing_ModifiedMergeSort(30);
        testing_ModifiedMergeSort(45);
        testing_RandomizedQuickSort();

        InsertionSort_text.append("N = " + N + "\t\t" + InsertionSort_best
                + "\t\t\t" + InsertionSort_worst + "\t\t\t"
                + InsertionSort_average + "\n");

        MergeSort_text.append("N = " + N + "\t\t" + MergeSort_best
                + "\t\t\t" + MergeSort_worst + "\t\t\t"
                + MergeSort_average + "\n");

        ModifiedMergeSort_V3_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V3_best
                + "\t\t\t" + ModifiedMergeSort_V3_worst + "\t\t\t"
                + ModifiedMergeSort_V3_average + "\n");

        ModifiedMergeSort_V4_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V4_best
                + "\t\t\t" + ModifiedMergeSort_V4_worst + "\t\t\t"
                + ModifiedMergeSort_V4_average + "\n");

        ModifiedMergeSort_V5_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V5_best
                + "\t\t\t" + ModifiedMergeSort_V5_worst + "\t\t\t"
                + ModifiedMergeSort_V5_average + "\n");

        RandomizedQuickSort_text.append("N = " + N + "\t\t" + RandomizedQuickSort_best
                + "\t\t\t" + RandomizedQuickSort_worst + "\t\t\t"
                + RandomizedQuickSort_average + "\n");

        // Case N = 20000
        N = 20000;
        fillArray();
        testing_InsertionSort();
        testing_MergeSort();
        testing_ModifiedMergeSort(15);
        testing_ModifiedMergeSort(30);
        testing_ModifiedMergeSort(45);
        testing_RandomizedQuickSort();

        InsertionSort_text.append("N = " + N + "\t\t" + InsertionSort_best
                + "\t\t\t" + InsertionSort_worst + "\t\t\t"
                + InsertionSort_average + "\n");

        MergeSort_text.append("N = " + N + "\t\t" + MergeSort_best
                + "\t\t\t" + MergeSort_worst + "\t\t\t"
                + MergeSort_average + "\n");

        ModifiedMergeSort_V3_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V3_best
                + "\t\t\t" + ModifiedMergeSort_V3_worst + "\t\t\t"
                + ModifiedMergeSort_V3_average + "\n");

        ModifiedMergeSort_V4_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V4_best
                + "\t\t\t" + ModifiedMergeSort_V4_worst + "\t\t\t"
                + ModifiedMergeSort_V4_average + "\n");

        ModifiedMergeSort_V5_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V5_best
                + "\t\t\t" + ModifiedMergeSort_V5_worst + "\t\t\t"
                + ModifiedMergeSort_V5_average + "\n");

        RandomizedQuickSort_text.append("N = " + N + "\t\t" + RandomizedQuickSort_best
                + "\t\t\t" + RandomizedQuickSort_worst + "\t\t\t"
                + RandomizedQuickSort_average + "\n");

        // Case N = 40000
        N = 40000;
        fillArray();
        testing_InsertionSort();
        testing_MergeSort();
        testing_ModifiedMergeSort(15);
        testing_ModifiedMergeSort(30);
        testing_ModifiedMergeSort(45);
        testing_RandomizedQuickSort();

        InsertionSort_text.append("N = " + N + "\t\t" + InsertionSort_best
                + "\t\t\t" + InsertionSort_worst + "\t\t\t"
                + InsertionSort_average + "\n");

        MergeSort_text.append("N = " + N + "\t\t" + MergeSort_best
                + "\t\t\t" + MergeSort_worst + "\t\t\t"
                + MergeSort_average + "\n");

        ModifiedMergeSort_V3_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V3_best
                + "\t\t\t" + ModifiedMergeSort_V3_worst + "\t\t\t"
                + ModifiedMergeSort_V3_average + "\n");

        ModifiedMergeSort_V4_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V4_best
                + "\t\t\t" + ModifiedMergeSort_V4_worst + "\t\t\t"
                + ModifiedMergeSort_V4_average + "\n");

        ModifiedMergeSort_V5_text.append("N = " + N + "\t\t" + ModifiedMergeSort_V5_best
                + "\t\t\t" + ModifiedMergeSort_V5_worst + "\t\t\t"
                + ModifiedMergeSort_V5_average + "\n");

        RandomizedQuickSort_text.append("N = " + N + "\t\t" + RandomizedQuickSort_best
                + "\t\t\t" + RandomizedQuickSort_worst + "\t\t\t"
                + RandomizedQuickSort_average + "\n");

        System.out.println(InsertionSort_text);
        System.out.println(MergeSort_text);
        System.out.println(ModifiedMergeSort_V3_text);
        System.out.println(ModifiedMergeSort_V4_text);
        System.out.println(ModifiedMergeSort_V5_text);
        System.out.println(RandomizedQuickSort_text);

    }

    private static void fillArray() {
        // (re)creating the array
        array = new int[N];

        // filling the array with random numbers
        // using for-loop and the given random generator instruction
        for(int i = 0; i < array.length; i++) {
            array[i] = (int)(1 + Math.random() * (N-0+1));
        }
    }

    private static void testing_InsertionSort() {
        // run-times arrays
        long [] run_times = new long[R];

        // start/finish times
        long start;
        long finish;
        for(int i = 0; i < R; i++) {
            copyArray();
            // recording start time
            start = System.currentTimeMillis();

            // testing the algorithm
            InsertionSort.sort(temp);

            // recording finish time
            finish = System.currentTimeMillis();

            run_times[i] = finish-start;
        }

        InsertionSort_best = findMin(run_times);
        InsertionSort_worst = findMax(run_times);
        InsertionSort_average = findAverage(run_times);
    }

    private static void testing_MergeSort() {
        // run-times arrays
        long [] run_times = new long[R];

        // start/finish times
        long start;
        long finish;
        for(int i = 0; i < R; i++) {
            copyArray();
            // recording start time
            start = System.currentTimeMillis();

            // testing the algorithm
            MergeSort.sort(temp);

            // recording finish time
            finish = System.currentTimeMillis();

            run_times[i] = finish-start;
        }

        MergeSort_best = findMin(run_times);
        MergeSort_worst = findMax(run_times);
        MergeSort_average = findAverage(run_times);
    }

    private static void testing_ModifiedMergeSort(int bound) {
        // run-times arrays
        long [] run_times = new long[R];

        // setting the bound
        ModifiedMergeSort.bound = bound;

        // start/finish times
        long start;
        long finish;
        for(int i = 0; i < R; i++) {
            copyArray();
            // recording start time
            start = System.currentTimeMillis();

            // testing the algorithm
            ModifiedMergeSort.sort(temp);

            // recording finish time
            finish = System.currentTimeMillis();

            run_times[i] = finish-start;
        }

        if(bound == 15) {
            ModifiedMergeSort_V3_best = findMin(run_times);
            ModifiedMergeSort_V3_worst = findMax(run_times);
            ModifiedMergeSort_V3_average = findAverage(run_times);
        }

        if(bound == 30) {
            ModifiedMergeSort_V4_best = findMin(run_times);
            ModifiedMergeSort_V4_worst = findMax(run_times);
            ModifiedMergeSort_V4_average = findAverage(run_times);
        }

        if(bound == 45) {
            ModifiedMergeSort_V5_best = findMin(run_times);
            ModifiedMergeSort_V5_worst = findMax(run_times);
            ModifiedMergeSort_V5_average = findAverage(run_times);
        }
    }

    private static void testing_RandomizedQuickSort() {
        // run-times arrays
        long [] run_times = new long[R];

        // start/finish times
        long start;
        long finish;
        for(int i = 0; i < R; i++) {
            copyArray();
            // recording start time
            start = System.currentTimeMillis();

            // testing the algorithm
            RandomizedQuickSort.sort(temp);

            // recording finish time
            finish = System.currentTimeMillis();

            run_times[i] = finish-start;
        }

        RandomizedQuickSort_best = findMin(run_times);
        RandomizedQuickSort_worst = findMax(run_times);
        RandomizedQuickSort_average = findAverage(run_times);
    }

    private static long findMax(long[] times) {
        long max = times[0];

        for(int i = 1; i < times.length; i++) {
            if(max < times[i]) {
                max = times[i];
            }
        }

        return max;
    }

    private static long findMin(long[] times) {
        long min = times[0];

        for(int i = 1; i < times.length; i++) {
            if(min > times[i]) {
                min = times[i];
            }
        }

        return min;
    }

    private static double findAverage(long[] times) {
        long sum = 0;
        double avg;

        for(int i = 0; i < times.length; i++) {
            sum += times[i];
        }

        avg = (double)sum/(double)times.length;

        return avg;
    }

    private static void copyArray() {
        temp = new int[N];
        System.arraycopy(array, 0, temp, 0, array.length);
    }
}
4

2 に答える 2

3

現在行っているアプローチには、体系的なエラーがあるようです。あなたが直面している最も明白な実験的問題のいくつかを述べますが、それらがあなたの実験結果の直接の原因ではないかもしれません。

JVMコンパイル

コメントで前に述べたように、JVMはデフォルトでコードをインタープリターモードで実行します。つまり、メソッドで見つかった各バイトコード命令はその場で解釈されてから実行されます。

このアプローチの利点は、各実行の起動時にネイティブコードにコンパイルされるJavaプログラムよりも、アプリケーションの起動時間が短縮されることです。

欠点は、起動時のパフォーマンスに影響はありませんが、そうでない場合よりもパフォーマンスの遅いプログラムが得られることです。

両方の懸念を改善するために、JVMチームはトレードオフを取りました。最初はプログラムが解釈されますが、JVMは、どのメソッド（またはメソッドの一部）が集中的に使用されているかに関する情報を収集し、頻繁に使用されていると思われるメソッドのみをコンパイルします。コンパイルすると、パフォーマンスにわずかな影響がありますが、コードは以前よりもはるかに高速になります。

測定を行うときは、この事実を考慮に入れる必要があります。

標準的なアプローチは、「JVMをウォームアップ」することです。つまり、アルゴリズムを少し実行して、JVMが必要なすべてのコンパイルを実行するようにします。JVMをウォームアップするコードをベンチマークするコードと同じにすることが重要です。そうしないと、コードのベンチマーク中にコンパイルが行われる可能性があります。

時間の測定

時間を測定するときは、System.nanoTime()の代わりにを使用する必要がありSystem.currentTimeMillisます。詳細については説明しません。ここからアクセスできます。

また、注意する必要があります。次のコードブロックは、最初は同等に見えるかもしれませんが、ほとんどの場合、異なる結果が得られます。

totalDuration = 0;
for (i = 0; i < 1000; ++i)
    startMeasure = now();
    algorithm();
    endMeasure = now();
    duration = endMeasure - startMeasure;
    totalDuration += duration;
}

//...

TRIALS_COUNT = 1000;
startMeasure = now();
for (i = 0; i < TRIALS_COUNT; ++i)
    algorithm();
}
endMeasure = now();
 duration = endMeasure - startMeasure / TRIALS_COUNT;

なんで？特に高速なalgorithm()実装の場合、高速であるほど、正確な結果を得るのが難しくなります。

大きな入力値

漸近表記は、の大きな値に対してさまざまなアルゴリズムがどのようにエスカレートするかを理解するのに役立ちますn。小さな入力値にそれらを適用することは、多くの場合無意味です。なぜなら、その大きさで一般的に必要なのは、操作の正確な数とそれに関連するコスト（Jakubが行ったことに似ている）を数えることだからです。Big O表記は、ほとんどの場合、BigOに対してのみ意味があります。Big Oは、アルゴリズムが入力値のサイズを超えて動作する方法を示しますが、少数の場合の動作は示しません。正規の例は、たとえばQuickSortです。これは、大きな配列の場合は重要ですが、サイズ4または5の配列の場合は、通常、選択または挿入ソートよりも遅くなります。ただし、入力サイズは十分に大きいようです。

最後に

そして、チャンが以前に述べたように、ヤクブによって行われた数学的演習は完全に間違っており、考慮されるべきではありません。

于 2013-03-10T19:54:42.833 に答える
-1

複雑さの計算は自分で行います。次の計算では、10000サンプルを想定しています。

挿入ソート： O（n ^ 2）、10000 * 10 000 = 100000000。

マージソート： O（nlogn）、10000 * log10000 =140000。

挿入によるマージ（15）： 15は9（サイズ20の配列）と10（サイズ10の配列）の間にあります2 ^ 10挿入ソート（サイズ10）、次に2 ^ 10 * 10 000マージ：1 024 * 10 * 10（挿入）+ 1 024 * 10 000（マージ）= 10 342400

挿入によるマージ（30）： 30は8（サイズ40の配列）と9（サイズ20の配列）の間にあります2 ^ 9挿入ソート（サイズ20）、次に2 ^ 9 * 10 000マージ：512 * 20 * 20 （挿入）+ 512 * 10 000（マージ）= 5 324 800

挿入とのマージ（45）： 45は7（サイズ80の配列）と8（サイズ40の配列）の間にあります2 ^ 8挿入ソート（サイズ40）、次に2 ^ 8 * 10 000マージ：256 * 40 * 40 （挿入）+ * 10 000（マージ）= 2 969600

クイックソート：最悪の場合のクイックソートはO（n ^ 2）を取りますが、最悪の場合はその限界に達するように特別に作成する必要があります。ほとんどの場合、ランダムに生成されたアルゴリズムを使用すると、平均してO（nlogn）：10000 * log10000 =140000になります。

可能な限り広範囲の入力データを効率的に測定する必要があるため、ソートアルゴリズムのパフォーマンスの測定は非常に困難になる可能性があります。

挿入ソートで表示される数値は、入力番号によって大きく偏ることがあります。配列で0と1のみを使用していて、配列がランダムに生成される場合、実際には、アルゴリズムが解決するのがはるかに簡単な問題になります。与えられたケースでは、平均して配列の半分がすでにソートされており、0と1を互いに比較する必要はありません。問題は、すべての0を左に転送することになります。これには、平均して（log（n / 2））！+n時間しかかかりません。10 000の場合、実際の時間は5 000！+10000 =133888です。

于 2013-03-10T00:51:25.233 に答える