をソートしながら、私は現在、私たちがしなければならないものの一つは、一般的な種類のいくつかを記述している、あなたが期待することとして、データ構造のクラスを取っています。私の挿入ソートアルゴリズムを書いているうちに、インストラクターのものよりも大幅に速く走っていたことがわかりました（400000データポイントの場合、アルゴリズムは約30秒、約90秒でした）。私は彼に私のコードを電子メールで送り、両方が同じマシン上で走っていたときに同じ結果が起こった。私たちは、ソート方法をゆっくりと私のものに変えるのに40分以上を費やすことに成功しました。まず、ここに私の挿入ソートのコードは次のとおりです。非常に奇妙な効率性に関する注意点
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
は今、この時点で彼のコードは、私たちがA[j]とA[j - 1]をスワップラインを除いて地雷と全く同じでした。彼のコードは次のようになりました：
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
これらの3行が犯人であることがわかりました。私のコードはこれによりかなり速く実行されていました。困惑し、私たちは、配列の宣言、int jための変数宣言と私はそれらを書いたように、彼がそれを書いたようにスワップのためのコードの3行が含まれていmainを持っていた簡単なプログラムのバイトコードを取得するにはjavap -cを走りました。ここに私のスワップ方式のバイトコードは次のとおりです。
Compiled from "me.java"
public class me {
public me();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iaload
12: istore_3
13: aload_1
14: iload_2
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: iaload
20: iastore
21: aload_1
22: iload_2
23: iconst_1
24: isub
25: iload_3
26: iastore
27: return
}
そして、私の講師のメソッドのバイトコード：
Compiled from "instructor.java"
public class instructor {
public instructor();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iconst_1
12: isub
13: iaload
14: istore_3
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: aload_1
20: iload_2
21: iaload
22: iastore
23: aload_1
24: iload_2
25: iload_3
26: iastore
27: return
}
私はこれらのバイトコードとの間の実質的な違いは表示されません。 この奇妙な振る舞いを引き起こす原因は何か（私のコードはまだ彼より3倍も速く走っていて、アルゴリズムのより大きな配列にこのような違いがあると予想されます）これは単にJavaの変わった変わったものですか？さらに、これはお使いのコンピュータで発生しますか？参考のため、をこれはMacBook Proの半ば2014上で実行され、それがここに表示され、それは、これらの3行を除いて、ここで表示される彼のコードは正確にコードに推定されたとおりに私のコードです。
public class Tester1 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
insertionSort(A);
System.out.println("My insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
}
そして、第二のファイル：
public class Tester2 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
otherInsertion(A);
System.out.println("Other insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] otherInsertion(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
j--;
}
}
return A;
}
}
して出力する（引数なしで、ちょうどjava Tester1とjava Tester2）：ここで
[EDIT]は私のテストクラスです
My insertion sort took 37680.0 milliseconds.
Other insertion sort took 86358.0 milliseconds.
これらは実行されました2つの異なるJVMで2つの別々のファイルとして扱います。
興味深い。あなたはあなたのテストクラスの1つを投稿できますか？ –
@JonKiparskyしました。また、私はそれが効率的である周りに交換しました。 A [j - 1]にtempを割り当てる方が効率的だったようです。また、一時的なスワップはそれをさらに悪化させます。 –
奇数、対応するネイティブコードには何か明白ですか？ – harold