search_n 能否更高效？
本文讨论了最流行的 search_n 实现的效率。此外，它还介绍了一种新的针对随机访问迭代器的 search_n 特化，其性能远远优于最常用的实现。
目录
1. 简介
在本文中，我们将首先讨论最流行的 search_n STL 算法实现的效率。之后，我将演示一种新的针对随机访问迭代器的 search_n 特化，其性能远远优于最常用的实现。这实际上是一个大大改进的 search_n 算法，其时间复杂度显著降低。
我的意图是直奔主题，不赘述 C++ 模板或 STL 本身。为了理解本文，您需要对 C++ 模板、标准模板库 (STL) 以及 C++ 语言有充分的理解。最后，我必须承认 search_n 并不是 STL 中最著名的算法，改进它对大多数 C++ 开发人员来说不会产生太大影响。另一方面，将算法提速 2-8 倍有时会很有用...
2. 算法的使用和行为
search_n 算法已经有足够充分的文档。 [2,4,6] 因此，为了描述该算法的使用和行为，我借用了以下三段（2.1、2.2 和 2.3）来自优秀的 SGI STL 文档。 [1,2]。
2.1 原型
Search_n 是一个重载名称；实际上有两个 search_n 函数。
template <class ForwardIterator, class Integer, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
Integer count, const T& value);
template <class ForwardIterator, class Integer,
class T, class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
Integer count, const T& value,
BinaryPredicate binary_pred);
2.2 描述
search_n 在范围 [first, last) 中搜索 count 个连续元素组成的子序列，这些元素都等于 value。它返回指向该子序列开头的迭代器，如果不存在这样的子序列，则返回 last。两个版本的 search_n 在如何确定两个元素是否相同方面有所不同：第一个使用 operator==，第二个使用用户提供的函数对象 binary_pred。
第一个版本的 search_n 返回范围 [first, last-count) 中第一个迭代器 i，使得对于范围 [i, i+count) 中的每个迭代器 j，*j == value。第二个版本返回范围 [first, last-count) 中第一个迭代器 i，使得对于范围 [i, i+count) 中的每个迭代器 j，binary_pred(*j, value) 为 true。
2.3 复杂度
线性。 search_n 最多执行 last-first 次比较。（C++ 标准允许复杂度为 O(n(last-first))，但这不必要的宽松。 search_n 没有理由检查任何元素多次。）
3. 常见实现
我所知道的所有 search_n 实现彼此之间都非常相似，并且在所有已知情况下，都使用相同的算法来处理向前迭代器和随机访问迭代器。下面的流程图 1 详细说明了这样一个典型的 search_n 实现。在所有这些 search_n 版本中，我们可以很容易地将 VC++ 和 SGI 实现区分为主导版本。我们将在以下小节 [s3.1.] 和 [s3.2.] 中分别讨论这两个版本。为简单起见，我们只讨论 search_n 的第一个变体，它使用 operator== 而不是用户提供的函数对象 binary_pred 来测试相等性。 [s2] 除了使用 binary_pred，第二个变体的设计和行为与其对应版本的设计和行为相同。因此，我们讨论的关于第一个变体的一切也适用于第二个变体。
流程图 1
3.1. VC++ 实现
这个 search_n 实现是随流行的 Microsoft Visual C++ 6.x-7.0 编译器附带的 STL 的一部分。此外，它与 Metrowerks CodeWarrior 8.x-9.x 的 STL 提供的实现也非常相似（尽管 Metrowerks 版本在下面的兴趣点 4 中讨论了一些优势）。换句话说，这是最常用的 search_n 实现之一。
源代码
此处不提供 VC++ search_n 实现的源代码，以避免潜在的版权侵犯。然而，任何拥有 Visual C++ 6.x-7.0 编译器的用户都可以很容易地在 algorithm 头文件中找到这段代码。
关注点
- 根据 MSDN 网站上的 VC++
search_n文档 [4]，其时间复杂度为：相对于搜索范围大小呈线性关系（另见第 5 节 [s5] 中的性能测试 B1、B2 和 C）。 - VC++
search_n首先计算搜索范围[_First1, _Last1)的宽度，然后使用该宽度值来形成控制循环的逻辑表达式。当_FwdIt1是随机访问迭代器时，宽度计算显然具有常数时间复杂度，否则为线性时间复杂度。换句话说，当使用此search_n实现处理列表和其他不提供随机访问迭代器的序列时，我们将遇到显著的开销（另请参见第 5 节 [s5] 中的性能测试 E）。 - VC++
search_n经常多次检查搜索范围中的许多元素。如上所述，search_n在范围[_First1, _Last1)中搜索_Count个连续元素组成的子序列，这些元素都等于_Val。如果 VC++ 版本遇到一个只有M (M < _Count)个连续元素等于_Val的子序列，它将判断该特定子序列不够长，并将从当前子序列的第二个元素开始继续搜索（而不是紧邻最后一个不匹配元素的元素）。然后它将立即遇到M-1个连续元素等于_Val，这实际上是初始M个元素子序列的最后M-1个元素。之后，它还将重新访问初始子序列的最后M-2个元素，然后再次是最后M-3个元素，依此类推。也就是说，当遇到
M (M < _Count)个连续等于_Val的元素时，VC++search_n最终会进行M(M+1)/2次冗余比较！因此，当搜索范围[_First1, _Last1)中有许多元素可能等于_Val时，VC++search_n实现效率较低（另见第 5 节 [s5] 中的性能测试 D）。 - Metrowerks 版本的
search_n与其 VC++ 对应版本非常相似，但它具有显著优势，即从不多次检查其搜索范围中的任何元素。因此，上述兴趣点 2 适用于 Metrowerks 实现，而兴趣点 3 不适用。
3.2. SGI 实现
以下 search_n 实现是优秀的 SGI STL（版本 3.3）的一部分。 [1,2] 此实现主要用于 GCC 编译器的所有现代版本（包括用于 Darwin 和 MinGW 的 GCC）。因此，这也是最流行的 search_n 实现之一。
源代码
// search_n. Search for __count consecutive copies of __val.
// (Part of the SGI STL v3.3)
template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp, _EqualityComparable);
if (__count <= 0)
return __first;
else {
__first = find(__first, __last, __val);
while (__first != __last) {
_Integer __n = __count - 1;
_ForwardIter __i = __first;
++__i;
while (__i != __last && __n != 0 && *__i == __val) {
++__i;
--__n;
}
if (__n == 0)
return __first;
else
__first = find(__i, __last, __val);
}
return __last;
}
}
/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
关注点
- 根据 SGI
search_n文档 [2]，其时间复杂度为：线性。search_n最多执行last-first次比较（另见第 5 节 [s5] 中的性能测试 B1、B2 和 C）。 - SGI
search_n在适当的时候内部使用find算法。因此，它可以利用find算法的潜在特化，从而显著提高其性能。（例如，如果_ForwardIter的类型是(char *)，那么find可能会在内部使用memchr函数。）这确实是一个非常好的设计选择！ - 与 VC++ 实现相比，SGI
search_n内部的迭代器推进受到显著限制。此实现不需要计算搜索范围[__first, __last)的宽度，并且更适合与列表和其他不提供随机访问迭代器的序列一起使用（另见第 5 节 [s5] 中的性能测试 E）。 - SGI 文档正确地指出，
search_n没有理由多次检查任何元素 [2]，但不幸的是，SGI 的search_n实现并未完全遵守这一理念。再次强调，search_n在范围[__first, __last)中搜索__count个连续元素组成的子序列，这些元素都等于__val。如果 SGI 版本遇到一个只有M (M < __count)个连续元素等于__val的子序列，它将判断该特定子序列不够长，并将从最后一个不匹配的元素开始继续搜索（而不是紧邻最后一个不匹配元素的元素）。也就是说，上述代码中的__first = find(__i, __last, __val)表达式总是检查*__i元素，而*__i可能是导致不匹配的元素（因此已经检查过）在之前的while循环的*__i == __val逻辑表达式中。换句话说，SGI
search_n每次遇到一个等于__val的元素子序列时，都会进行一次冗余比较。实际上，这在大多数实际情况下应该不是一个大问题，但它确实是 SGIsearch_n实现中的一个缺陷（另见第 5 节 [s5] 中的性能测试 D）。
4. 随机访问迭代器的增强实现
在本节中，我将介绍一种增强的 search_n 实现，它只能与随机访问迭代器一起使用。此实现的优势在于其主循环的工作方式 [流程图 2：循环 1]。当搜索满足 search_n 条件的 N 个连续元素时，此主循环只检查搜索范围中每 N 个元素中的一个，而 VC++ 和 SGI 版本 [s3] 则逐个检查搜索范围元素 [流程图 1：循环 1]。当然，当主循环找到匹配项时，此 search_n 版本必须回溯，因为匹配的元素可能位于满足 search_n 条件的子序列中间。因此，它将首先向后移动 [流程图 2：循环 3]，然后再次向前移动 [流程图 2：循环 2]，以准确估算特定子序列的起始位置和长度。然而，回溯发生得相当不频繁，而且没有任何元素被多次检查。因此，预计此 search_n 实现将始终比 VC++ 和 SGI 版本更快。为方便起见（并为简洁起见），我以后将使用“DPX search_n”来指代此特定算法。
下面将以流程图和源代码两种形式演示 DPX search_n 实现。之后，我们还将讨论与此实现相关的一些兴趣点。
流程图 2
源代码
template <class _RandomAccessIter, class _Integer, class _Tp> inline
_RandomAccessIter search_n(_RandomAccessIter __first,
_RandomAccessIter __last, _Integer __count, const _Tp& __val)
{
if (__count <= 0)
return __first;
if (__count == 1)
return std::find(__first, __last, __val);
typedef std::iterator_traits<_RandomAccessIter>::difference_type iter_diff;
iter_diff __tailSize = __last - __first;
const iter_diff __pattSize = __count;
if (__tailSize >= __pattSize)
{
_RandomAccessIter __backTrack;
iter_diff __remainder, __prevRemainder;
const iter_diff __skipOffset = __pattSize - 1;
_RandomAccessIter __lookAhead = __first + __skipOffset;
for ( ; ; __lookAhead += __pattSize ) // the main loop...
{
//__lookAhead here is always pointing to the last element of next
// possible match.
assert( __tailSize >= __pattSize );
__tailSize -= __pattSize;
for ( ; ; ) // the skip loop...
{
if (*__lookAhead == __val)
break;
if (__tailSize < __pattSize)
return __last;
__lookAhead += __pattSize;
__tailSize -= __pattSize;
}
assert( __tailSize == (__last - __lookAhead) - 1 );
__remainder = __skipOffset;
for ( __backTrack = __lookAhead - 1; *__backTrack ==
__val; --__backTrack )
{
if (--__remainder == 0)
return (__lookAhead - __skipOffset); //Success
}
for ( ; ; )
{
if (__remainder > __tailSize)
return __last; //failure
__lookAhead += __remainder;
__tailSize -= __remainder;
if (*__lookAhead == __val)
{
__prevRemainder = __remainder;
__backTrack = __lookAhead;
do
{
if (--__remainder == 0)
return (__lookAhead - __skipOffset); //Success
} while ( *--__backTrack == __val);
//adjust remainder for next comparison
__remainder += __pattSize - __prevRemainder;
}
else
break;
}
//__lookAhead here is always pointing to the element of the last
//mismatch.
if (__tailSize < __pattSize)
return __last;
}
}
return __last; //failure
}
/*
* Copyright (c) 2004-2007
* Jim Xochellis
*
* Permission to use, copy, modify, distribute and sell this software for
* any purpose is hereby granted without fee, provided that the above
* copyright notice appears in all copies and that both that copyright
* notice and this permission notice appear in supporting documentation.
* Jim Xochellis makes no representations about the suitability of this
* software for any purpose. It is provided "as is" without express or
* implied warranty.
*
*/
关注点
- DPX
search_n最多执行last-first次比较，因此其最坏情况复杂度是线性的，类似于 VC++ 和 SGI 实现的平均复杂度。但这种最坏情况实际上在该算法中极少发生。另一方面，其平均时间复杂度将为O((last-first)/count)（另见第 5 节 [s5] 中的性能测试 A、B1、B2 和 C）。 - 除了 DPX
search_n实际上只检查少数满足条件的元素外，我还尽力确保搜索范围中的任何元素都不会被多次检查（另见第 5 节 [s5] 中的性能测试 D）。因此，此search_n版本非常适合在元素比较过程较慢的情况下使用。 - 基于上述原因，我相信这个
search_n实现将在所有可能的情况下都优于 VC++ 和 SGI 实现。它唯一的缺点是它需要随机访问迭代器，因此不能与只提供前向迭代器的列表和其他序列一起使用（另请参阅第 5 节 [s5] 中的性能测试和第 6 节 [s6] 中的结论）。
5. 性能测试
到目前为止，我们已经遇到了 search_n 算法的三种不同实现，并且我们还在理论上讨论了它们的预期运行时性能。在本节中，我们将观察当我们在计算机上运行这些算法时实际会发生什么。特别是，我使用本文开头提供的代码进行了一系列性能测试。在接下来的小节中，将对每个测试进行描述，并简要讨论其结果。所有性能测试的结果都已在本节末尾以图表形式可视化。
在接下来的段落中，我将频繁使用一些新符号，它们是：
- 符号
N，表示search_n正在搜索的连续元素数量。 - 符号
M，表示search_n在搜索过程中超越的序列元素数量。
性能测试 A
此测试的目的是观察 DPX search_n 算法 [s4] 在被超越元素数量 M 增加时的行为。该测试重复了三次，针对 N 的三个不同值。此测试中搜索的元素存储在 vector 中，遇到匹配元素的概率为 1%。
测试 A 的结果已在相应的 图 A 中可视化。图的垂直轴表示经过时间，水平轴表示被超越的元素 M。此图清楚地表明，经过时间随 M 线性增长，但也很明显，随着 N 的增加，DPX search_n 的性能要好得多。这强烈表明特定 search_n 实现的时间复杂度为 O(M/N)，而最流行的实现通常具有时间复杂度 O(M)。
性能测试 B1 和 B2
这些测试的目的是观察和比较迄今讨论的所有三种 search_n 实现在被超越元素数量 M 增加时的行为。测试 B1 和 测试 B2 之间唯一的区别是 N 的值，它们分别等于 4 和 32。这两个测试中搜索的元素都存储在 vector 中，遇到匹配元素的概率为 1%。
测试 B1 和 B2 的结果已在相应的图 B1 和 B2 中可视化。这两个图的垂直轴都表示经过时间，水平轴都表示被超越的元素 M。两个图都显示，在所有三种 search_n 实现中，经过时间随 M 线性增长。SGI 版本似乎总是比其 VC++ 对应版本表现更好，而 DPX 版本则超越了所有竞争对手。在 测试 B2 中，N 的值为 32 而不是 4，SGI 和 VC++ 版本的性能与其在 测试 B1 中的相应性能相同，而 DPX 版本的性能显著提高。这正是我们所期望的，因为我们知道这三种算法的时间复杂度。（DPX search_n 的时间复杂度为 O(M/N)，而另外两个版本的时间复杂度为 O(M)）。
性能测试 C
此测试的目的是观察和比较迄今讨论的所有三种 search_n 实现的行为，当被超越元素数量 M 保持不变（一百万个元素），而 N 的值不断增加时。搜索的元素存储在 vector 中，遇到匹配元素的概率为 1%。
测试 C 的结果已在相应的 图 C 中可视化。图的垂直轴表示经过时间，水平轴表示 N。图显示，SGI 和 VC++ 版本的 search_n 在 N 变化时不受影响，而 DPX 版本在 N 增加时表现得更好。这是 DPX search_n 时间复杂度为 O(M/N) 的又一证明。
性能测试 D
此测试的目的是观察和比较迄今讨论的所有三种 search_n 实现的行为，当 M 和 N 保持不变（分别为一百万个元素和 32 个），但匹配元素的密度正在增加时。也就是说，在此测试中，我们增加了遇到匹配元素的概率。搜索的元素存储在 vector 中。
测试 D 的结果已在相应的 图 D 中可视化。图的垂直轴表示经过时间，水平轴表示匹配元素的密度。图显示，当匹配元素的密度变高时，SGI 和 VC++ search_n 版本的性能显著降低，而 DPX 版本几乎不受影响。这是因为当匹配元素的密度很高时，SGI 和 VC++ 版本进行了许多冗余比较（测试 D 中最坏情况：+100%）。在相同情况下，DPX 版本只检查少数（测试 D 中最坏情况：9%）满足条件的元素。
性能测试 E
此测试的目的是观察和比较 SGI 和 VC++ search_n 实现的行为，当被超越元素数量 M 增加且搜索的元素存储在 list 中时。请注意，DPX search_n 不能用于此测试，因为它需要随机访问迭代器，而 list 只提供向前迭代器。N 始终等于 16，遇到匹配元素的概率为 1%。
测试 E 的结果已在相应的 图 E 中可视化。图的垂直轴表示经过时间，水平轴表示被超越的元素 M。与之前的图 B1 和 B2 相比，此图显示 SGI search_n 在使用随机访问迭代器时相对于 VC++ 版本的性能优势，在使用前向迭代器时变得更大。
更多细节
所有图表的垂直轴表示经过时间，您可能会注意到这些轴没有提供关于经过时间精确值的任何信息。这是故意的，因为我们不关心单个经过时间，而是需要关注当问题因素发生变化时时间的增长。此外，实际的经过时间仅在我运行这些测试的计算机上，以及该计算机当时特定的硬件和软件配置下才有意义。
用于进行这些测试的代码包含在本文的顶部。这是一段简短而简单的代码，在源文件中带有注释，我相信它可以轻松用于验证我的测试结果，以及进一步实验 search_n 算法的运行时行为。
性能图 A |
性能图 B1 |
 |
 |
性能图 B2 |
性能图 C |
 |
 |
性能图 D |
性能图 E |
 |
 |
6. 结论
在本文中，我们讨论了 search_n STL 算法的效率。特别是，我们讨论了非常流行的 VC++ 和 SGI 版本 [s3]，并且我还介绍了新的 DPX search_n [s4]，它是 search_n 算法针对随机访问迭代器的高效特化。此外，我还进行了一系列性能测试 [s5]，以展示我们在计算机上运行这些算法时实际会发生什么。所有这些讨论和测试的结论可以总结如下：
- 当涉及到随机访问迭代器时，DPX
search_n是迄今为止最佳选择。其平均时间复杂度要好得多（请参阅第 4 节 [s4] 中的兴趣点 1），性能测试也证实了这一事实（请参阅第 5 节 [s5] 中的测试 A、B1、B2、C）。 - 当搜索的连续元素数量变大（参见第 5 节 [s5] 中的测试 A 和 C）或遇到匹配元素的概率增加（参见第 5 节 [s5] 中的测试 D）时，DPX
search_n的性能甚至更好。 - 对于向前访问迭代器，SGI
search_n的性能远优于 VC++ 版本（请参阅第 5 节 [s5] 中的测试 E）。
7. 关于本文的更多信息
7.1. 致谢
文章的部分文本和代码来源于 SGI/HP 的 STL 实现和文档。
版权所有 © 1996-1999
Silicon Graphics Computer Systems, Inc.
特此授予免费使用、复制、修改、分发和销售本软件及其文档的许可，但前提是所有副本中均应出现上述版权声明，并且支持文档中也应出现该版权声明和本许可声明。Silicon Graphics 不对本软件的适用性作任何声明。本软件按“原样”提供，不附带任何明示或暗示的保证。
版权所有 © 1994
Hewlett-Packard Company
特此授予免费使用、复制、修改、分发和销售本软件及其文档的许可，但前提是所有副本中均应出现上述版权声明，并且支持文档中也应出现该版权声明和本许可声明。Hewlett-Packard Company 不对本软件的适用性作任何声明。本软件按“原样”提供，不附带任何明示或暗示的保证。
7.2. 相关新闻
- 2005-09-12
- 2005-02-27
7.3. 修订历史
- 2007-03-23
- 针对随机访问迭代器的
search_n特化中的错误修复和性能改进。
- 针对随机访问迭代器的
- 2004-04-19
- 对象潜在的构造和销毁移至循环外部（由 Simon Hughes 提出）。
- 2004-04-12
- 初始发布。