作为后台开发团队,服务性能优化是我们持续在做的事情,涵盖面比较广,包括锁优化、缓存优化、查找优化等等。这里举一个查找优化方面的例子进行说明。
业务场景是查找网络拓扑中的边并进行权重的更新。概况而言就是在容器(比如vector)中查找对应元素,有则执行更新操作。原有的实现采用find_if。用法参考这里,比较直观,只需定义一个==比较函数即可,类似:
auto it = std::find_if(std::begin(v), std::end(v), [&i](uint32_t e) -> bool {
return e == i;
});
find_if的问题在于它是线性复杂度的,这是它在gcc-9.1.0中的实现:
/// This is an overload used by find algos for the Input Iterator case.
template<typename _InputIterator, typename _Predicate>
inline _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
{
while (__first != __last && !__pred(__first)) ++__first;
return __first;
}
出于其他考虑,我们保留了vector容器,再引入二分查找算法,正好C++标准库提供了lower_bound,看起来符合我们的需求:
auto first = std::lower_bound(v.begin(), v.end(), i);
if(!(first == v.end()) && !(i < *first)){
std::cout << "item found!" << std::endl;
}
由于lower_bound返回的是[v.begin(), v.end()]中第一个大于或等于查找值的迭代器,所以我们需要额外判断元素是否找到且真的相等。
简单比对find_if和lower_bound在不同大小(100~1000000)vector(元素已排序)下查找相同元素(最大元素)的耗时如下:
说明标准库还是值得信赖的,我们看下lower_bound在gcc-9.1.0的具体实现:
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (__comp(__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
可以看到lower_bound就是个二分查找,其中涉及到两个函数,distance用于计算迭代器__first和__last的距离,进而在每次迭代的步长__half;advance用于向前推进步长:
template<typename _InputIterator>
inline _GLIBCXX14_CONSTEXPR typename iterator_traits<_InputIterator>::difference_type __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last)
{
++__first;
++__n;
}
return __n;
}
template<typename _RandomAccessIterator>
inline _GLIBCXX14_CONSTEXPR typename iterator_traits<_RandomAccessIterator>::difference_type __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
return __last - __first;
}
template<typename _InputIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_assert(__n >= 0);
while (__n--) ++__i;
}
template<typename _BidirectionalIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void __advance(_BidirectionalIterator& __i, _Distance __n, bidirectional_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
if (__n > 0)
while (__n--)
++__i;
else
while (__n++)
--__i;
}
template<typename _RandomAccessIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void __advance(_RandomAccessIterator& __i, _Distance __n, random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
if (__builtin_constant_p(__n) && __n == 1)
++__i;
else if (__builtin_constant_p(__n) && __n == -1)
--__i;
else
__i += __n;
}
可以看到,对于RandomAccessIterator类型的__first和__last,distance可以在常数时间计算出距离(__last - __first),advance可以在常数时间推进指定步长(__i += __n),可是对于更一般的InputIterator,会退化到线性迭代,复杂度为O(n)。
下面以list和vector为例,给出lower_bound的这种行为的直观展示:
所以,标准库虽好,可不要违反科学哦,相信也不会有人在链表上使用二分查找吧O(∩_∩)O
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。