为什么交换这两行运行的结果会不同？

Question

第一次：

SortTestHelper::testSort("InsertSort", insertionSort, arr1, n);

SortTestHelper::testSort("Merge Sort", mergeSort, arr2, n);

运行结果：

InsertSort : 1.768 s

Merge Sort : 0.101 s

第二次;

SortTestHelper::testSort("Merge Sort", mergeSort, arr2, n);

SortTestHelper::testSort("InsertSort", insertionSort, arr1, n);

运行结果：

Merge Sort : 2.748 s

InsertSort : 1.74 s

Answer 1

liuyubobobo 2016-11-08 15:45:01

我测试了一下我为这个课程官方写的代码，没有这个问题。你的第一组实验数据的结果是合理的。第二组数据MergeSort比InsertionSort慢这么多是不合理的。

我在我的计算机上运行了一遍你的代码，速度上没有这个差异。你再运行一下看看。是不是单一一次运行的时候计算机上其他并行的任务产生了什么影响？

另外，释放一个数组的内存空间应该使用delete[] 

所以你的26行应该改为 delete[] aux;

58行应该改为 delete[] arr1;

59行应该改为 delete[] arr2;

• 提问者 尘埃旅途 #1

  非常感谢！

Answer 2

liuyubobobo 2016-11-08 15:28:13

感觉在你的测试代码中，arr1和arr2互相不独立哦。能否给出你的整体main函数，尤其是arr1和arr2创建的部分。

Answer 3

提问者 尘埃旅途 2016-11-08 16:33:09

我将官方代码的：  cout<<"Test for Random Array, size = "<<n<<", random range [0, "<<n<<"]"<<endl; 这一行删除

并将

        SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);

        SortTestHelper::testSort("Merge Sort",     mergeSort,     arr2, n);

交换位置，然后加上delete[] aux;后发现运行速度也会出现问题。而以上三点只要任何一点不满足都会运行成功！！我用的是VS2013.

• liuyubobobo #1

  。。。 那啥，我都不敢相信自己完全按照你的操作对我的代码进行了一遍修改。然后依然没有问题。。。我这里没有vs 2013。。。

• 提问者 尘埃旅途 回复 liuyubobobo #2

  好吧，也许是我软件的问题。谢谢老师了

• liuyubobobo #3

  你看看按照我的这个回答的思路，把aux放在merge外面会不会好。。。 这个链接的最后附了源码地址。。。 http://coding.imooc.com/learn/questiondetail/3115.html

Answer 4

提问者 尘埃旅途 2016-11-08 16:21:00

好的，谢谢老师！

Answer 5

提问者 尘埃旅途 2016-11-08 15:57:06

我的代码只要加上了delete[] aux;就会变慢，而官方代码加上这一句也是正常速度

• liuyubobobo #1

  在你的计算机上，运行官方代码（aux数组按照你现在的方式处理）是正常的吗？ https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/02-Merge-Sort/main.cpp

• 提问者 尘埃旅途 回复 liuyubobobo #2

  对的，复制官方代码，然后将T aux[r-l+1];改为 T aux=new T[r-l+1];然后加上delete[] aux;后速度是正常的

• 提问者 尘埃旅途 #3

  T aux[r-l+1]改为T *aux=new T[r-l+1];

点开查看后面1条评论

Answer 6

提问者 尘埃旅途 2016-11-08 15:52:26

刚刚重新再改了一下。运行仍然不正常。使用官方代码却是正常的！但我的代码和官方代码没差别啊

#include"SortTestHelper.h"
#include<iostream>
#include<string>
#include<ctime>
#include<cassert>
#include"InsertionSort.h"
#include<algorithm>

using namespace std;

template<typename  T>
void __merge(T arr[], int l, int mid, int r){
	// 经测试,传递aux数组的性能效果并不好
	T *aux = new T[r - l + 1];
	for (int i = l; i <= r; i++)
		aux[i - l] = arr[i];

	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++){

		if (i > mid)   { arr[k] = aux[j - l]; j++; }
		else if (j > r){ arr[k] = aux[i - l]; i++; }
		else if (aux[i - l] < aux[j - l]){ arr[k] = aux[i - l]; i++; }
		else                          { arr[k] = aux[j - l]; j++; }
	}
	delete[] aux;


}


template<typename T>
void __mergeSort(T arr[], int l, int r){
	if (l >= r) return;
	int mid = (l + r) / 2;
	__mergeSort(arr, l, mid);
	__mergeSort(arr, mid + 1, r);
	__merge(arr, l, mid, r);
}


template<typename T>
void mergeSort(T arr[], int n){
	__mergeSort(arr, 0, n - 1);   //下划线代表私有子函数，不被用户调用。__开头的函数易被编译器占用，尽量少用该函数。
}

int main()
{
	int n = 50000;
	int* arr1 = SortTestHelper::generateRandomArray(n, 0, n);
	int* arr2 = SortTestHelper::copyIntArray(arr1, n);
	SortTestHelper::testSort("Merge Sort", mergeSort, arr2, n);
	SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
	delete[] arr1;
	delete[] arr2;

	system("pause");
	return 0;
}

运行结果：

Merge Sort : 2.695 s

Insertion Sort : 1.722 s

请按任意键继续. . .

Answer 7

提问者 尘埃旅途 2016-11-08 15:34:08

#include"SortTestHelper.h"
#include<iostream>
#include<string>
#include<ctime>
#include<cassert>
#include"InsertionSort.h"
#include<algorithm>

using namespace std;

template<typename  T>
void __merge(T arr[], int l, int mid, int r){
	// 经测试,传递aux数组的性能效果并不好
	T *aux=new T[r - l + 1];
	for (int i = l; i <= r; i++)
		aux[i - l] = arr[i];

	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++){

		if (i > mid)   { arr[k] = aux[j - l]; j++; }
		else if (j > r){ arr[k] = aux[i - l]; i++; }
		else if (aux[i - l] < aux[j - l]){ arr[k] = aux[i - l]; i++; }
		else                          { arr[k] = aux[j - l]; j++; }
	}
	delete aux;


}


template<typename T>
void __mergeSort(T arr[], int l, int r){
	if (l >= r) return;
	int mid = (l + r) / 2;
	__mergeSort(arr, l, mid);
	__mergeSort(arr, mid + 1, r);
	__merge(arr, l, mid, r);
}


template<typename T>
void mergeSort(T arr[], int n){
	__mergeSort(arr,0,n-1);   //下划线代表私有子函数，不被用户调用。__开头的函数易被编译器占用，尽量少用该函数。
}

int main()
{
	int n = 50000;
	int* arr1 = SortTestHelper::generateRandomArray(n, 0, n);
	int* arr2 = SortTestHelper::copyIntArray(arr1, n);
	SortTestHelper::testSort("Merge Sort", mergeSort, arr2, n);
	SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
	


	delete(arr1);
	delete(arr2);

	system("pause");
	return 0;
}

这是全部main代码

Answer 8

提问者 尘埃旅途 2016-11-08 15:28:52

更改delete后正常了，谢谢老师指导！