排序功能比std :: sort慢 [英] Sort function is slower than 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?

推荐答案

可能是实现还为某些众所周知的类型(例如int，long等)指定了该函数的一些显式特性. .)已由分发者使用不同的优化标志进行了编译，并且您从vcxxx.dll(或lib(如果是静态链接，则为lib))进行隐式链接.

因此，源代码是相同的，但是翻译后的二进制文件是不同的.

May be the implementation also specify some explicit specialization of that function for certain well known types (like int, long etc.) that have been compiled by the distributor with a different optimization flag and that you implicitly link from the vcxxx.dll (or lib, in case of static linking).

so, the source code is the same, but the translated binary is different.

复制代码时，您只是将std :: sort的代码逐字粘贴到了sort2上吗?即sort2不是std名称空间的一部分.由于它不是std命名空间的一部分，因此不会使用所有可爱的交换专业化方法，而 可能是缺乏速度的原因.
搜索Koenig查找(或依赖于参数的查找-ADL)，该解释说明了编译器如何在名称空间中搜索名称.我可能完全错了，但是过去当我在命名空间之间移动内容时，这种事情使我感到痛苦.

干杯，

灰

When you copied the code did you just stick the code from std::sort into sort2 verbatim? i.e. sort2 isn''t part of the std namespace. As it''s not part of the std namespace it won''t be using all the lovely specialisations for swap that are kicking around which may be the cause of the lack of speed.

Do a search for Koenig lookup (or argument dependent lookup - ADL) which explains how the compiler searches namespaces for names. I may be completely wrong but this sort of thing has bitten me in the past when I''ve moved stuff between namespaces.

Cheers,

Ash

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慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！