我有两个类似的实现(java和c ++)用于像选择排序这样的简单算法.
public interface SortingAlgorithm { public void sort(int[] a); } public class SelectionSort implements SortingAlgorithm { @Override public void sort(int[] a) { for (int i = 0; i < a.length; i++) { int lowerElementIndex = i; for (int j = i + 1; j < a.length; j++) { if (a[j] < a[lowerElementIndex]) { lowerElementIndex = j; } } swap(a, lowerElementIndex, i); } } private void swap(int[] a, int i, int j) { if (i == j) { return; } int temp = a[i]; a[i] = a[j]; a[j] = temp; } }
和c一:
inline void swap(int* a, int i, int j); void s_sort(int* a, int size) { int i; for (i = 0; i < size; i++) { int lowerElementIndex = i, j; for (j = i + 1; j < size; j++) { if (a[j] < a[lowerElementIndex]) { lowerElementIndex = j; } } swap(a, lowerElementIndex, i); } } inline void swap(int* a, int i, int j) { if (i == j) { return; } int temp = a[i]; a[i] = a[j]; a[j] = temp; }
现在,我尝试在大型阵列上测试它们(100000随机int).结果首先是java:~17秒(用oracle jdk/jvm编译和执行)c:~22秒(用gcc v4.8编译,没有任何优化)
当然,我然后尝试通过cflags优化我的c版本.结果是(我只报告cflags): - O1:~18.4
-O2:~18.4
-O {3-9}:~20.9
现在,我的第一个问题是我应该使用哪些cflacs进行编译?
所以我阅读了关于优化的gnu手册.添加-march = native没有帮助.经过一段时间尝试其他选项后,我进入了-fprofile-arcs选项.将它添加到我的标志使我的代码在大约11秒内完成测试!但是有些文件出现在我的文件夹中:分析的结果.据我所知,我应该将它们与-fbranch-probability一起使用并重新编译代码.在~18.5秒内再次重新编译结果.这就是我真正想问的问题.
如果我的程序必须编写文件并收集分析信息,那么我的程序如何运行得如此之快呢?如果它不运行,它的运行速度会慢1.5倍?
我忘了提到我在安装了Intel Celeron @ 2.8GHz处理器和linux(带有xfce的fedora 20)的旧PC上.如果您需要有关硬件的其他信息,请询问!;)
编辑:我用于测试的代码是:
Java的:
public class Test { public static void main(String[] args) { int[] a = new int[100000]; int[] a2 = new int[100000]; for (int i = 0; i < a.length; i++) { a[i] = (int)(Math.random()*100000); a2[i] = a[i]; } SelectionSort s = new SelectionSort(); InsertionSort s1 = new InsertionSort(); double start = System.nanoTime(); s.sort(a); double end = System.nanoTime(); double time = (end-start)/1000000000.0; System.out.println("Selection: "+time); start = System.nanoTime(); s1.sort(a2); end = System.nanoTime(); time = (end-start)/1000000000.0; System.out.println("Insertion: "+time); } }
而c:
#include "insertion_sort.h" #include "selection_sort.h" #include#include #include #include int main() { int max = 100000, i; srand(time(NULL)); int array[100000], array2[100000]; for(i=0; i<100000; i+=1) { array[i] = rand()%100000; } memcpy(array2, &array[0], 100000 * sizeof(int)); clock_t inizio = clock(); s_sort(array, max); clock_t fine = clock(); float tempoEsecuzione = (float)(fine - inizio) / CLOCKS_PER_SEC; printf("Selection: %2.3f\n", tempoEsecuzione); inizio = clock(); i_sort(array2, max); fine = clock(); tempoEsecuzione = (float)(fine - inizio) / CLOCKS_PER_SEC; printf("Insertion: %2.3f\n", tempoEsecuzione); return 0; }
代码包含对插入排序函数的引用,我没有将其包含在问题的其余部分中,因为(正如预期的那样)java运行速度慢于c.