1

ソートアルゴリズムの効率化に関するプロジェクトを行っています。バブルソートを 50 回繰り返して、n 個の数値にかかった平均時間を見つけたとします。しかし、最初の数回の反復は、後続の反復よりも常に遅いことに気付きました

例: 1394ms、1381ms、1001ms、1008ms、1008ms、1011ms...

        long lStartTime = System.currentTimeMillis();
        bubbleSort(R); // R is the array of int
        long lEndTime = System.currentTimeMillis();
        long difference = lEndTime - lStartTime;

その背後にある理由は何ですか？これは、CPU がどのデータ セットをキャッシュに格納するかを判断できるためですか? もしそうなら、それは現実的ではないので、その後の計算時間を分析に使用すべきではありませんか?

ありがとう！

編集：私は他のソートアルゴリズムも行っています。例としてバブルソートですが、挿入を除いて、私が行ったすべてのソートで発生します

public static int[] bubbleSort(int[] S) {
    int counter = 0;
    boolean isUnsort = true;
    while (isUnsort) {
        isUnsort = false;

        for (int i = 0; i < S.length - 1 - counter; i++) {
            if (S[i] > S[i + 1]) {
                int temp = S[i];
                S[i] = S[i + 1];
                S[i + 1] = temp;
                isUnsort = true;
            }

        }
        counter++;
    }
    return S;
}
4

1 に答える 1

4

それはおそらく、バイトコードをより効率的な形式に変換する Just-in Time Compiler です。タイマーを開始する前に、少なくとも 1 つ (できれば数回) のウォームアップ ソートを実行することをお勧めします。また、バブルソートは恐ろしく非効率なソートです。

于 2014-07-16T05:48:41.087 に答える