<分区>
我有一个函数，它使用二进制搜索来查找已排序的 double 组中的索引，使得“搜索值”大于或等于数组中该索引处的值，但严格小于数组中的值如果按升序排序，则为后续索引处的数组。输入数组可以按升序或降序排序。
我在 Microsoft Visual Studio 2012 上分析了我的代码，它显示 12% 的时间花在了这个函数上，而 8% 的时间花在了比较“搜索值”和数组中的值上。我想探索加速此功能的可能性。
/**
Binary Search algorithm for a sorted array of doubles
_sortedArr could be sorted ascending or descending
Find the index in the array _sortedArr such that:
_sortedArr[lowerIndex] <= _valToFind < _sortedArr[lowerIndex+1]
*/
size_t findInArray(const double _sortedArr[], size_t _len, double _valToFind)
{
size_t startIndex = 0;
if( _len <= 1 ) return startIndex;
// Determine if the array is sorted ascending or descending
unsigned int isAscending = (_sortedArr[_len-1] > _sortedArr[startIndex]);
// To avoid looping through the array, detect edge cases first
if( isAscending ) {
if( _valToFind < _sortedArr[startIndex+1] ) return startIndex;
if( _valToFind >= _sortedArr[_len-1] ) return _len-1;
} else {
if( _valToFind > _sortedArr[startIndex+1] ) return startIndex;
if( _valToFind <= _sortedArr[_len-1] ) return _len-1;
}
size_t lowerIndex = startIndex + 1;
size_t upperIndex = _len - 1;
size_t midIndex = 0;
// Binary search loop
while (upperIndex - lowerIndex > 1)
{
midIndex = (upperIndex + lowerIndex) >> 1; // (upperIndex+lowerIndex)/2
// 8% of time spent executing the if-clause
if (_valToFind >= _sortedArr[midIndex] == isAscending)
lowerIndex = midIndex;
else
upperIndex = midIndex;
}
return lowerIndex;
}
下面是测试该功能的方法:
int main (int argc, char *argv[])
{
const double arr[] = {-3.0000000000000000, -2.5714285714285716, -2.1428571428571432,
-1.7142857142857146, -1.2857142857142860, -0.85714285714285743,
-0.42857142857142888, -3.3306690738754696e-016, 0.42857142857142821,
0.85714285714285676, 1.2857142857142854, 1.7142857142857140,
2.1428571428571423, 2.5714285714285707, 2.9999999999999991};
size_t index = findInArray(arr, 15, 0.0);
std::cout << "Index is: " << index << std::endl;
return 0;
}
当我更改 if 子句(此处花费 8% 的时间)以使用小于比较时，没有明显的性能改进:
if (!(_valToFind < _sortedArr[midIndex]) == isAscending)
此更改在反汇编中的唯一区别是使用“ja”而不是 jb。
如有任何想法，我们将不胜感激。