对于像选择排序这样的简单算法，我有两个类似的实现（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 个随机整数）上测试它们。
一开始的结果是
java：~17秒（使用oracle jdk/jvm编译并执行）
c: ~22 秒（使用 gcc v4.8 编译，未进行任何优化）
当然，我随后尝试通过cflags优化我的c版本。
结果是（我只报告 cflags）：
-O1：~18.4
-氧气：~18.4
-O{3-9}：~20.9
现在，我的第一个问题是我应该使用哪个 cflac 来编译？
所以我阅读了有关优化的 gnu 手册。
添加 -march=native 没有帮助。经过一段时间尝试其他选项后，我进入了 -fprofile-arcs 选项。将其添加到我的标志中使我的代码在大约 11 秒内完成测试！
然而，一些文件出现在我的文件夹中：分析的结果。据我了解，我应该将它们与 -fbranch-probabilities 一起使用并重新编译代码。
大约 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 <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
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 慢。
