В настоящее время я беру класс Data Structures и, как вы, возможно, должны сделать некоторые из обычных видов. При написании моего алгоритма сортировки вставки я заметил, что он работает значительно быстрее, чем у моего преподавателя (для 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 линии являются виновниками. Из-за этого мой код работал значительно быстрее. Perplexed, мы побежали javap -c, чтобы получить байтовый код для простой программы, которая только что имела main, которая содержала объявление массива, объявление переменной для int j и 3 строки кода для замены, как я их написал, и когда он их написал. Вот байт-код для моего метода свопинга:
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 года, и мой код точно так же, как он появляется здесь, и его код был выведен точно на тот код, который появляется здесь, за исключением трех строк.
[EDIT] Вот мои тестовые классы:
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):
My insertion sort took 37680.0 milliseconds.
Other insertion sort took 86358.0 milliseconds.
Данные были выполнены как 2 отдельных файла в 2 разных JVM.
Интересно. Можете ли вы опубликовать один из ваших тестовых классов? –
@JonKiparsky я сделал. Кроме того, у меня было это поменялось, что эффективно. Назначение темпа A [j - 1] показалось более эффективным. Кроме того, нет замены temp делает его еще хуже. –
Нечетный, есть ли что-то очевидное в соответствующем нативном коде? – harold