简介：
使用两种相同的mergesort算法，我测试了C++（使用Visual Studios C++2010 express）与Java（使用NetBeans 7.0）的执行速度。我推测C++的执行速度至少会稍快，但测试显示C++的执行比Java的执行慢4-10倍。我相信我已经为C++设置了所有的速度优化，我发布的是一个版本，而不是一个调试。为什么会出现这种速度差异？
代码：
Java：
public class PerformanceTest1
{
/**
* Sorts the array using a merge sort algorithm
* @param array The array to be sorted
* @return The sorted array
*/
public static void sort(double[] array)
{
if(array.length > 1)
{
int centre;
double[] left;
double[] right;
int arrayPointer = 0;
int leftPointer = 0;
int rightPointer = 0;
centre = (int)Math.floor((array.length) / 2.0);
left = new double[centre];
right = new double[array.length - centre];
System.arraycopy(array,0,left,0,left.length);
System.arraycopy(array,centre,right,0,right.length);
sort(left);
sort(right);
while((leftPointer < left.length) && (rightPointer < right.length))
{
if(left[leftPointer] <= right[rightPointer])
{
array[arrayPointer] = left[leftPointer];
leftPointer += 1;
}
else
{
array[arrayPointer] = right[rightPointer];
rightPointer += 1;
}
arrayPointer += 1;
}
if(leftPointer < left.length)
{
System.arraycopy(left,leftPointer,array,arrayPointer,array.length - arrayPointer);
}
else if(rightPointer < right.length)
{
System.arraycopy(right,rightPointer,array,arrayPointer,array.length - arrayPointer);
}
}
}
public static void main(String args[])
{
//Number of elements to sort
int arraySize = 1000000;
//Create the variables for timing
double start;
double end;
double duration;
//Build array
double[] data = new double[arraySize];
for(int i = 0;i < data.length;i += 1)
{
data[i] = Math.round(Math.random() * 10000);
}
//Run performance test
start = System.nanoTime();
sort(data);
end = System.nanoTime();
//Output performance results
duration = (end - start) / 1E9;
System.out.println("Duration: " + duration);
}
}
C++：
#include <iostream>
#include <windows.h>
using namespace std;
//Mergesort
void sort1(double *data,int size)
{
if(size > 1)
{
int centre;
double *left;
int leftSize;
double *right;
int rightSize;
int dataPointer = 0;
int leftPointer = 0;
int rightPointer = 0;
centre = (int)floor((size) / 2.0);
leftSize = centre;
left = new double[leftSize];
for(int i = 0;i < leftSize;i += 1)
{
left[i] = data[i];
}
rightSize = size - leftSize;
right = new double[rightSize];
for(int i = leftSize;i < size;i += 1)
{
right[i - leftSize] = data[i];
}
sort1(left,leftSize);
sort1(right,rightSize);
while((leftPointer < leftSize) && (rightPointer < rightSize))
{
if(left[leftPointer] <= right[rightPointer])
{
data[dataPointer] = left[leftPointer];
leftPointer += 1;
}
else
{
data[dataPointer] = right[rightPointer];
rightPointer += 1;
}
dataPointer += 1;
}
if(leftPointer < leftSize)
{
for(int i = dataPointer;i < size;i += 1)
{
data[i] = left[leftPointer++];
}
}
else if(rightPointer < rightSize)
{
for(int i = dataPointer;i < size;i += 1)
{
data[i] = right[rightPointer++];
}
}
delete left;
delete right;
}
}
void main()
{
//Number of elements to sort
int arraySize = 1000000;
//Create the variables for timing
LARGE_INTEGER start; //Starting time
LARGE_INTEGER end; //Ending time
LARGE_INTEGER freq; //Rate of time update
double duration; //end - start
QueryPerformanceFrequency(&freq); //Determinine the frequency of the performance counter (high precision system timer)
//Build array
double *temp2 = new double[arraySize];
QueryPerformanceCounter(&start);
srand((int)start.QuadPart);
for(int i = 0;i < arraySize;i += 1)
{
double randVal = rand() % 10000;
temp2[i] = randVal;
}
//Run performance test
QueryPerformanceCounter(&start);
sort1(temp2,arraySize);
QueryPerformanceCounter(&end);
delete temp2;
//Output performance test results
duration = (double)(end.QuadPart - start.QuadPart) / (double)(freq.QuadPart);
cout << "Duration: " << duration << endl;
//Dramatic pause
system("pause");
}
观察结果：
对于10000个元素，C++执行所花费的时间大约是Java执行所花费时间的4倍。对于100000个元素，该比例约为7:1。对于10000000个元素，比例约为10:1。对于超过10000000，Java执行完成，但C++执行暂停，我不得不手动终止进程。
我认为运行程序的方式可能有错误。当您在Visual C++Express中点击F5时，程序正在调试器下运行，速度会慢很多。在Visual C++2010的其他版本（例如，我使用的Ultimate）中，尝试按CTRL+F5（即"启动而不调试"）或尝试运行可执行文件本身（在Express中），您就会看到差异。
我在我的机器上只做了一次修改就运行了你的程序（添加了delete[] left; delete[] right;以消除内存泄漏；否则它将在32位模式下耗尽内存！）。我有一台i7950。公平地说，我还将相同的数组传递给了Java中的Arrays.sort（）和C++中的std:：sort。我使用了10000000的数组大小。
以下是结果（时间以秒为单位）：
Java代码：7.13Java Arrays.sort：0.9332位C++代码：3.57C++标准：：排序0.8164位C++代码：2.77C++标准：：排序0.76
因此，C++代码要快得多，即使是在Java和C++中都经过高度调优的标准库，也往往显示出C++的微小优势。
编辑：我刚刚意识到，在您最初的测试中，您在调试模式下运行C++代码。您应该切换到Release模式并在调试器之外运行它（正如我在文章中所解释的），以获得公平的结果。
我不专业地编程C++（甚至不专业地：），但我注意到您正在堆上分配一个double（double*temp2=new double[arraySize]；）。与Java初始化相比，这是昂贵的，但更重要的是，它构成了内存泄漏，因为你从未删除过它，这可以解释为什么你的C++实现会停滞，它基本上已经耗尽了内存。
首先，您是否尝试使用std::sort（或std::stable_sort，通常是mergesort）在C++中获得基线性能？
我不能评论Java代码，但对于C++代码：
- 与Java不同，C++中的
new需要手动干预来释放内存。每次递归都会泄漏内存。我建议使用std::vector，因为它为您管理所有内存，而且iterator, iterator构造函数甚至会进行复制（并且可能比for循环优化得更好）。这几乎可以肯定是你表现不同的原因 - 您在Java中使用
arraycopy，但在C++中不使用库功能（std::copy），尽管如果您使用vector，这也无关紧要 - Nit：在同一行声明并初始化您的变量，在您第一次需要它们的时候，而不是全部在函数的顶部
- 如果允许您使用标准库的一部分，
std::merge可以取代您的合并算法
编辑：如果你真的在使用delete left;来清理内存，那可能是你的问题。正确的语法应该是delete [] left;来解除分配数组。
您的版本泄漏了太多内存，因此时间安排毫无意义
我确信这段时间花在了内存分配器上
重写它，使用标准C++对象进行内存管理std:：vector，看看会发生什么。
就我个人而言，我仍然希望Java版本能够获胜。因为JIT允许特定于机器的优化，而C++通常可以进行特定于计算机的优化，它只会进行一般的体系结构优化（除非您提供确切的体系结构标志）。
- 注意：不要忘记在启用优化的情况下进行编译
只是清理您的C++：
我没有尝试在C++风格的中进行好的合并排序（只是重写）
void sort1(std::vector<double>& data)
{
if(data.size() > 1)
{
std::size_t centre = data.size() / 2;
std::size_t lftSize = centre;
std::size_t rhtSize = data.size() - lftSize;
// Why are we allocating new arrays here??
// Is the whole point of the merge sort to do it in place?
// I forget bbut I think you need to go look at a knuth book.
//
std::vector<double> lft(data.begin(), data.begin() + lftSize);
std::vector<double> rht(data.begin() + lftSize, data.end());
sort1(lft);
sort1(rht);
std::size_t dataPointer = 0;
std::size_t lftPointer = 0;
std::size_t rhtPointer = 0;
while((lftPointer < lftSize) && (rhtPointer < rhtSize))
{
data[dataPointer++] = (lft[lftPointer] <= rht[rhtPointer])
? lft[lftPointer++]
: rht[rhtPointer++];
}
std::copy(lft.begin() + lftPointer, lft.end(), &data[dataPointer]);
std::copy(rht.begin() + rhtPointer, rht.end(), &data[dataPointer]);
}
}
正在考虑合并排序。我会尝试以下操作：
我还没有测试过，所以它可能无法正常工作。但是，这是一种尝试，不继续分配大量内存来进行排序。相反，它使用一个临时区域，并在排序完成时将结果复制回来。
void mergeSort(double* begin, double* end, double* tmp)
{
if (end - begin <= 1)
{ return;
}
std::size_t size = end - begin;
double* middle = begin + (size / 2);
mergeSort(begin, middle, tmp);
mergeSort(middle, end, tmp);
double* lft = begin;
double* rht = middle;
double* dst = tmp;
while((lft < middle) && (rht < end))
{
*dst++ = (*lft < *rht)
? *lft++
: *rht++;
}
std::size_t count = dst - tmp;
memcpy(begin, tmp, sizeof(double) * count);
memcpy(begin + count, lft, sizeof(double) * (middle - lft));
memcpy(begin + count, rht, sizeof(double) * (end - rht));
}
void sort2(std::vector<double>& data)
{
double* left = &data[0];
double* right = &data[data.size()];
std::vector<double> tmp(data.size());
mergeSort(left,right, &tmp[0]);
}
几件事。
Java经过高度优化，在代码执行一次之后，JIT编译器将以本机代码的形式执行代码。
Java中的System.arraypy将比一次只复制一个元素执行得更快。试着用memcpy替换这个副本，你会发现它要快得多。
编辑：看看这篇文章：C++性能与Java/C#
仅仅看代码很难判断，但我大胆猜测原因是处理递归而不是实际计算。尝试使用一些依赖于迭代而不是递归的排序算法，并共享性能比较的结果。
我不知道为什么Java在这里要快得多。
我将它与内置的Arrays.sort（）进行了比较，结果它又快了4倍。（它不会创建任何对象）。
通常，如果有一个测试Java要快得多，那是因为Java更善于删除什么都不做的代码。
也许您可以使用memcpy，而不是在末尾使用循环。
尽量制作一个全局向量作为缓冲区，尽量不分配大量内存。这将比你的代码运行得更快，因为如果使用一些技巧（只使用一个缓冲区，并且在程序启动时分配内存，所以内存不会被分割）：
#include <cstdio>
#define N 500001
int a[N];
int x[N];
int n;
void merge (int a[], int l, int r)
{
int m = (l + r) / 2;
int i, j, k = l - 1;
for (i = l, j = m + 1; i <= m && j <= r;)
if (a[i] < a[j])
x[++k] = a[i++];
else
x[++k] = a[j++];
for (; i <= m; ++i)
x[++k] = a[i];
for (; j <= r; ++j)
x[++k] = a[j];
for (i = l; i <= r; ++i)
a[i] = x[i];
}
void mergeSort (int a[], int l, int r)
{
if (l >= r)
return;
int m = (l + r) / 2;
mergeSort (a, l, m);
mergeSort (a, m + 1, r);
merge (a, l, r);
}
int main ()
{
int i;
freopen ("algsort.in", "r", stdin);
freopen ("algsort.out", "w", stdout);
scanf ("%dn", &n);
for (i = 1; i <= n; ++i)
scanf ("%d ", &a[i]);
mergeSort (a, 1, n);
for (i = 1; i <= n; ++i)
printf ("%d ", a[i]);
return 0;
}