1

Cormen＆Coの「Introductionto Algorithms」を読み、Javaにアルゴリズムを実装しました。set()最後のメソッドで挿入ソートコードif-statementに書き込むのは理にかなっているのだろうか？可能であれば、コードをもっと速くしたいです。

public static void insertion(List<Integer> a) {
    List<Integer> aList = a;
    int temp;
    int previousIndex;

    for (int i = 1; i < aList.size(); i++) {
        temp = aList.get(i);
        previousIndex = i - 1;
        while ((previousIndex >= 0) && aList.get(previousIndex) > temp) {
            aList.set(previousIndex + 1, a.get(previousIndex));
            previousIndex--;
        }

        //if(aList.get(previousIndex + 1) > temp){
            aList.set(previousIndex + 1, temp);
        //}

    }
}

初級ならすみません。私はとても初心者です。

4

1 に答える 1

3

これは、コードを最適化して高速化する試みのように見えます。明らかなアイデアは、データの設定を回避するためにデータをテストすることです。これにより、（1）値の読み取りとテストが値の設定よりも高速であり、（2）テストで値の設定が回避される場合が十分にある場合にのみ、実行が高速になります。

IMOは（1）疑わしく、（2）時間を節約するために頻繁に行う必要がありますが、そうではないと思います。

（aList.get（previousIndex + 1）> temp）の代わりに（previousIndex + 1！= i）をテストすることで、より高速なテストを実現できます。これは、リストのオブジェクトのコピーが多い場合に最適化される可能性があります。複雑なオブジェクト構造をコピーするなど、より時間がかかります。ただし、場合によっては、整数オブジェクトについて話しているので、テストを追加すると、すべての場合で速度が低下するだけだと思います。

もちろん、すべての最適化の場合と同様に、実際の測定値だけが何が効果的であるかを示します。そのため、最適化は常に最後に行う必要があり、必要な場合にのみ行われます。

于 2012-08-26T19:05:56.023 に答える