std::count 和 std::find 之间的性能差异
Performance differences between std::count and std::find
这可能是一个愚蠢的问题,但我想检查一个容器(在本例中是 bool
的 std::vector
,但更广泛的方法会更好)以检查值是否存在。据我了解,运行 时间 std::count
和 std::find
都是线性的,如果项目在范围内,计数可能会变慢,但我认为如果对象存在,两者应该相同,但是我可以看到编译器可以矢量化 std::count
和 因此 使 std::count
运行 更快的可能性。我的第一个假设是 运行 相同还是第二个假设是编译器可以 向量化 std::count
是正确的?
如果您要查找的项目在不在范围内,count
和find
都将遍历整个序列,因此两者的速度大致相同。
如果您要查找的项目 在 范围内,find
将在找到后 return。所以find
会更快,找到的元素越靠近序列的前面。
一般不会执行"vectorize"这个算法。但是,在 std::vector<bool>
的情况下,一个实现 (libc++) 确实进行了优化。它优化了 count
和 find
以一次查看 64 位(在 64 位平台上),因此这两个操作都将大大加快up 与 std::vector<char>
上的相同操作。这些优化描述如下:
http://howardhinnant.github.io/onvectorbool.html
我不是很肯定(如果我错了,请随时纠正我,我很乐意是错的),但我认为 libc++ 目前是进行这些优化的唯一实现。
为了找到这个问题的答案,我查看了这两个函数的行为。根据我在 C++ Reference 上可以找到的内容,std::count 函数的行为如下:
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val)
{
typename iterator_traits<InputIterator>::difference_type ret = 0;
while (first!=last) {
if (*first == val) ++ret;
++first;
}
return ret;
}
std::find 函数如下所示:
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}
这意味着 std::count 函数将始终遍历整个向量,即使只能找到一个值。但是,std::find 函数实际上在找到该值时停止。这意味着如果您只想知道向量是否包含值,则 std::find 函数平均比 std::count 函数更快。如果您还想知道找到了多少,std::count 函数是最好的解决方案,尽管我认为这不是您的意图。
总的来说,这意味着 std::find 函数将与 std::count 函数一样快,甚至更快。
来源:
http://www.cplusplus.com/reference/algorithm/find/
http://www.cplusplus.com/reference/algorithm/count/
这可能是一个愚蠢的问题,但我想检查一个容器(在本例中是 bool
的 std::vector
,但更广泛的方法会更好)以检查值是否存在。据我了解,运行 时间 std::count
和 std::find
都是线性的,如果项目在范围内,计数可能会变慢,但我认为如果对象存在,两者应该相同,但是我可以看到编译器可以矢量化 std::count
和 因此 使 std::count
运行 更快的可能性。我的第一个假设是 运行 相同还是第二个假设是编译器可以 向量化 std::count
是正确的?
如果您要查找的项目在不在范围内,count
和find
都将遍历整个序列,因此两者的速度大致相同。
如果您要查找的项目 在 范围内,find
将在找到后 return。所以find
会更快,找到的元素越靠近序列的前面。
一般不会执行"vectorize"这个算法。但是,在 std::vector<bool>
的情况下,一个实现 (libc++) 确实进行了优化。它优化了 count
和 find
以一次查看 64 位(在 64 位平台上),因此这两个操作都将大大加快up 与 std::vector<char>
上的相同操作。这些优化描述如下:
http://howardhinnant.github.io/onvectorbool.html
我不是很肯定(如果我错了,请随时纠正我,我很乐意是错的),但我认为 libc++ 目前是进行这些优化的唯一实现。
为了找到这个问题的答案,我查看了这两个函数的行为。根据我在 C++ Reference 上可以找到的内容,std::count 函数的行为如下:
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val)
{
typename iterator_traits<InputIterator>::difference_type ret = 0;
while (first!=last) {
if (*first == val) ++ret;
++first;
}
return ret;
}
std::find 函数如下所示:
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}
这意味着 std::count 函数将始终遍历整个向量,即使只能找到一个值。但是,std::find 函数实际上在找到该值时停止。这意味着如果您只想知道向量是否包含值,则 std::find 函数平均比 std::count 函数更快。如果您还想知道找到了多少,std::count 函数是最好的解决方案,尽管我认为这不是您的意图。
总的来说,这意味着 std::find 函数将与 std::count 函数一样快,甚至更快。
来源: http://www.cplusplus.com/reference/algorithm/find/ http://www.cplusplus.com/reference/algorithm/count/