排序功能比std :: sort慢

问题描述

由于某种原因，我必须编写自己的排序函数.我指的是std :: sort，但有时我的函数花费的时间是std::sort的2倍.
因此，我将"void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)"复制到了函数sort2中.令我惊讶的是，sort2的时间成本仍然是直接调用std::sort的2倍.为什么相同的代码会导致不同的速度?

For some reason I have to write my own sort function. I refer to std::sort, but sometime my function costs 2 times the time of std::sort.

So I copied "void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)" to my function sort2. What surprised me is that the time cost with sort2 is still 2 times of call std::sort directly. Why is the same code resulting in different speed?

推荐答案

template<class _RanIt,
	class _Diff,
	class _Pr> inline
	void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
	{	// order [_First, _Last), using _Pred
	_Diff _Count;
	for (;<big> _ISORT_MAX < (_Count = _Last - _First) </big>&& 0 < _Ideal; )
		{	// divide and conquer by quicksort
		pair<_RanIt, _RanIt> _Mid =
			_Unguarded_partition(_First, _Last, _Pred);
		_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisions
		if (_Mid.first - _First < _Last - _Mid.second)	// loop on larger half
			_Sort(_First, _Mid.first, _Ideal, _Pred), _First = _Mid.second;
		else
			_Sort(_Mid.second, _Last, _Ideal, _Pred), _Last = _Mid.first;
		}
	if (<big>_ISORT_MAX < _Count</big>)
		{	// heap sort if too many divisions
		std::make_heap(_First, _Last, _Pred);
		std::sort_heap(_First, _Last, _Pred);
		}
	else if (1 < _Count)
		_Insertion_sort(_First, _Last, _Pred);	// small, insertion sort
	}

这是_Sort的代码，堆排序由_ISORT_MAX 关闭.
在发布堆中，可以打开.

更改了源，我的排序功能接近于1M大小矢量中std :: sort的速度.

const int _ISORT_MAX2 = 64 * 64;
for(; _ISORT_MAX2<(_Count = _Last-_First)&& 0< _Ideal;)

调整_ISORT_MAX2的值，排序功能将获得不同的速度，甚至比std :: sort还要快.

This is the code of _Sort , heap sort is closed by _ISORT_MAX.
In release heap sort may be opened .

Changed the source ,my sort function is close to the speed of std::sort in 1M size vector.

const int _ISORT_MAX2 = 64*64;
for (;_ISORT_MAX2 < (_Count = _Last - _First) && 0 < _Ideal; )

Adjust the value of _ISORT_MAX2 , sort function will get different speed ,even quicker than std::sort.

这篇关于排序功能比std :: sort慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！