I'd like to test the execution time of different sorting algorithms and I found an interesting problem. When I run the program multiple times, say the insert sorting, the first one or two times cost much more time than later ones. This scenario happens when the size of array is big, also different sizes have different effect on the execution time.
public static void insertSort(int[] array){
for(int i = 1; i<array.length; i++){
int current = array[i];
int j = i-1;
while((j>=0)&&(array[j]>current)){
array[j+1] = array[j];
array[j] = current;
j--;
}
}
}
public static void multiTimes(int size){
Random r = new Random();
int a[] = new int[size];
int b[] = new int[size];
for(int j = 0; j<size; j++)
a[j] = r.nextInt(size);
long startTime, endTime = 0;
b = Arrays.copyOf(a, a.length);
startTime=System.nanoTime();
insertSort(b);
endTime=System.nanoTime();
System.out.println("Insert "+(endTime-startTime)+" ns");
b = Arrays.copyOf(a, a.length);
startTime=System.nanoTime();
insertSort(b);
endTime=System.nanoTime();
System.out.println("Insert "+(endTime-startTime)+" ns");
b = Arrays.copyOf(a, a.length);
startTime=System.nanoTime();
insertSort(b);
endTime=System.nanoTime();
System.out.println("Insert "+(endTime-startTime)+" ns");
b = Arrays.copyOf(a, a.length);
startTime=System.nanoTime();
insertSort(b);
endTime=System.nanoTime();
System.out.println("Insert "+(endTime-startTime)+" ns");
b = Arrays.copyOf(a, a.length);
startTime=System.nanoTime();
insertSort(b);
endTime=System.nanoTime();
System.out.println("Insert "+(endTime-startTime)+" ns");
b = Arrays.copyOf(a, a.length);
startTime=System.nanoTime();
insertSort(b);
endTime=System.nanoTime();
System.out.println("Insert "+(endTime-startTime)+" ns");
}
Size: 100
Insert 77908 ns
Insert 82573 ns
Insert 75109 ns
Insert 76508 ns
Insert 91902 ns
Insert 78840 ns
Each time the execution time is similar.
size: 1000:
Insert 6256400 ns
Insert 5674659 ns
Insert 188938 ns
Insert 188004 ns
Insert 187071 ns
Insert 186605 ns
size: 2000:
Insert 7961037 ns
Insert 6590889 ns
Insert 793538 ns
Insert 793072 ns
Insert 793072 ns
Insert 792138 ns
We can see that for the size of 1000, 2000 or more, the results are quite interesting. The execution time of first two times are about 30 times more than later executions (size = 1000).
Note:
- Language: Java JDK7; IDE: Eclipse; Platform: Win8.1;
- For each size, many experiments are tested and the results are quite similar. Although the execution time has some randomness, but it cannot explain why first two times are similar and more than 30x longer than later ones.
- A possible reason may be the array is already in data cache so later executions cost less time. I'm not sure if there are other reasons.
PS: After I tested insert sort, I found it even confusing in quick sort.
public static void quickSort(int a[], int left, int right){
if(right<=left)
return;
int temp[] = new int[right-left+1];
for(int i = left; i<=right; i++)
temp[i-left] = a[i];
int pivot = a[left];
int subr = right, subl = left;
for(int i = left+1; i<=right;i++){
if(temp[i-left]>pivot)
a[subr--] = temp[i-left];
else
a[subl++] = temp[i-left];
}
a[subl] = pivot;
quickSort(a, left, subl-1);
quickSort(a, subr+1, right);
}
Size = 1000:
Qs 888240 ns
Qs 2218734 ns
Qs 2179547 ns
Qs 2132896 ns
Qs 2146890 ns
Qs 2212670 ns
Size = 500:
Qs 432924 ns
Qs 406799 ns
Qs 941889 ns
Qs 1103302 ns
Qs 1101436 ns
Qs 1086042 ns
When the size is around [200, 2000], the first several times cost less time than later ones, which is opposite than insert sort. When size increases to more than 2000, it is similar to scenarios in insert sort in which later executions cost less time.
