8回答

liuyubobobo

2016-11-08

已采纳

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

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

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

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

58行应该改为 delete[] arr1;

59行应该改为 delete[] arr2;

3

1

尘埃旅途

非常感谢！

2016-11-17

共1条回复

liuyubobobo

2016-11-08

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

0

0

尘埃旅途

提问者

2016-11-08

我将官方代码的：  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.

0

3

liuyubobobo

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

2016-11-08

共3条回复

尘埃旅途

提问者

2016-11-08

好的，谢谢老师！

0

0

尘埃旅途

提问者

2016-11-08

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

0

4

liuyubobobo

回复

尘埃旅途

因为你这个问题在我的计算机上复制不出来，所以我暂时也没找到原因。目测你贴的第二版代码没有问题。试试重新启动一下整个IDE或者计算机... 如果问题依旧就需要一点一点和没问题的代码做一下比对，确认一下问题源了。。。

2016-11-08

共4条回复

尘埃旅途

提问者

2016-11-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;
}

运行结果：

Merge Sort : 2.695 s

Insertion Sort : 1.722 s

请按任意键继续. . .

0

0

尘埃旅途

提问者

2016-11-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代码

0

0

尘埃旅途

提问者

2016-11-08

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

0

0