提高 search_n 的性能
Can search_n be more efficient? （By Jim Xochellis）
翻译 masterlee
本文讨论常用的search_n的性能，另外介绍一个新的专门处理随机访问迭代器的search_n，它的性能上要超过常规使用方法。
Performance Tests - 12.1 Kb
1. 介绍
在这篇文章中我们将讨论STL算法中search_n的性能。后面将介绍一个新的专门处理随机访问迭代器的search_n，它的性能上要超过常规使用方法。这个事实上就是一个充分改良后的 search_n算法，它将降低时间复杂度。
本文没有深入介绍C++模板和STL，而是直接分析主体相关的内容。为了能够理解本文，你需要掌握C++模板，标准模板库和基本的C++语言等等。这里我们承认 在STL里面并不是主要的算法，对于C++程序员优化它也并不能够提高多少。但是对于一个算法提高2-8倍是很有用的。
2. 算法的用法和行为
search_n算法已经有非常详尽的文档了，这里为了介绍算法的使用方法和行为，从非常好的SGI STL 文档中借来三节来介绍它。
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)范围内的迭代指针i，对于每一个在[i, i+count)范围内的迭代j多有 *j == value 。第二个search_n 返回的是在[first, last)范围内的迭代指针i，对于每一个在[i, i+count)范围内的迭代j多有 binary_pred(*j, value) 是正确的。
2.3、复杂度
search_n 几乎都是执行的 last – first 的比较。（C++标准中提供的复杂度是 O(n(last-first))），但是这个并不严格。对于search_n比较每一个数据超过一次。）
3. 常用操作
search_n所有的操作都是非常相似的，同一算法也使用在随机访问迭代上。下面流程图一详细的描述了一个典型的search_n操作，在search_n所有的版本中，我们能够非常容易地区分VC++和SGI的操作。我们将在下面的章节中分别讨论这两个版本。为了简单话，我们仅仅讨论第一个search_n，使用operator== 来判断是否等于，不去研究使用用户自定义函数binary_pred对象来判断是否符合条件。除了使用binary_pred，设计和第一个变量的行为是和它的副本相同的。因此我们就可以讨论第一个变量然后应用到第二个上面。
流程图一
3.1、使用VC执行
STL中的search_n 操作一直伴随着流行的VC++ 6.x-7.x的编译器，此外在Metrowerks CodeWarrior 8.x-9.x中的STL也提供了相似的操作（Metrowerks在下面的要讨论它的一些优点）。换句话说，search_n被频繁地使用着。
源代码
为了避免版权问题，这里并不介绍在VC++中search_n的源代码，但是，我们可以从VC++ 6.x-7.x编译器中包含的头文件algorithm片断中看出有价值的东西。
几个要点
1、 根据MSDN站点上VC++中 search_n文档中介绍，它的时间复杂度是：是与搜索大小线形相关的（参考第五章节中的B1，B2和C的测试）。
2、 VC++中的 search_n首先计算 [_First1, _Last1) 搜索范围的宽度，以后就用这个宽度值为逻辑表达式控制循环次数。这个宽度计算明显是一个固定的时间复杂度，当 _FwdIt1是一个随机访问迭代器的时候这个时间复杂度就是一个线形的值。换句话说，我们将在列表和其他序列上进行的 search_n操作获取的经验并不能证明随机访问迭代器（参照第五章E的测试）。
3、 VC++中的 search_n在搜索的数据范围内常常需要多次比较，而不是一次。就像上面提到的，search_n是从一个[_First1, _Last1)范围的数据中查找有_Count个连续的数据，每个数据都和_Val 相同。在VC++这个版本中一个子串仅仅有M(M < _Count)个数据等于_Val，它将根据这个子串的长度了决定继续搜索，从第二个当前子串的数据（而不是下一次搜索的数据）搜索。下面将从M-1开始和_Val比较是否相等，M-1事实上是上一次匹配的那个M数据的下一个数据。然后继续访问M-2后面的子串，再到M-3的子串，等等。
也就是说，当M(M < _Count)个连续的数据等于_Val，VC++中的 search_n将进行M(M+1)/2次多余的比较！所以VC++中的 search_n当它可能有许多数据在搜索的[_First1, _Last1)范围内等于_Val的话，它的效率就比较低（参考第五章D的测试）。
4、 Metrowerks版本的 search_n和VC++中的匹配非常相似，但它的优点就在于不用在搜索范围内检查多次。因此对于上面的第二条应用Metrowerks版本的操作是非常好的，但第三点并不是这样的。
3.2、使用SGI执行
下面是SGI STL（version 3.3）中 search_n实现的部分。这个实现主要用在现在流行的GCC编译器上的（包括Darwin 和 MinGW 的 GCC）。然而，这仅仅是流行的 search_n实现方法之一。
源代码
// search_n. Search for __count consecutive copies of __val.
// (Part of the SGI STL v3.3)
template <class class _ForwardIter _Integer _Tp class="",,>
_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.
*/
几个要点
1、 根据SGI的 search_n文档中介绍，它的时间复杂度是线形的。search_n至多要进行 last – first次比较（参见第五章测试程序B1，B2和C）。
2、 SGI的 search_n在实现的内部使用了find算法，不管是否适当，它利用了优化的find算法，这样将提高性能。（例如，如果_ForwardIter是(char *)类型，那么find在实现的内部可能使用的是memchr函数）一个非常好的设计师必须的。
3、 和VC++中的实现向比较，值得我们注意的是在SGI的 search_n使用的迭代是有限制的。这些操作不需要计算搜索[__first, __last)范围的宽度，适应使用在列表和其他序列中，但不提供随即访问迭代器（参照第五章测试程序E）。
4、 SGI的文档中明确规定没有任何理由 search_n的比较数据的次数超过一次，但遗憾的是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的时候多进行一次比较。实际上在实际情形中并不是一个大问题，但是对于SGI的 search_n实现的确是一个缺点（参照第五章测试程序D）。
4. 增强随机访问迭代器的实现
在本章节中，我要介绍一个增强的 search_n实现，它仅仅能够用于处理随即访问迭代器。增强这个实现的机制主要依靠主循环中的工作(流程图二：loop 1)。当使用标准的 search_n搜索N个连续的数据的时候，这个主循环对于每一个N个连续的数据在这个范围内仅仅搜索一次。然而VC++ 和SGI版本的 search_n在搜索范围内每次需要一个接一个地比较(流程图一：loop 1)。当然，当主循环匹配到一个的时候，这个search_n 版本将退回到上一步，因为对于标准的search_n匹配到的数据在一个子串的中间。因此，他首先要退回(流程图二：loop 3)，然后前往(流程图二：loop 2)为了估算出在开始那个特定子串的长度。然而，这种倒退经常会发生，很少有比较的数据的次数是一次的。因此这个版本的search_n期望能够比VC++ 和SGI版本的 search_n更快。为了这些目的（简短地说），后面我将命名“DPX search_n”来优化这个算法。
下面是DPX search_n 实现的流程图和源代码。然后我们将讨论关于这个实现的几个主要的思想。
流程图二
源代码
template <CLASS class="" Tp, _, _Integer _RandomAccessIter> inline
_RandomAccessIter search_n(_RandomAccessIter __first,
_RandomAccessIter __last, _Integer __count, const _Tp& __val)
{
if (__count <= 0)
return __first;
else if (__count == 1)
return find(__first, __last, __val);
else if (__last > __first)
{
_RandomAccessIter __lookAhead;
_RandomAccessIter __backTrack;
_Integer __skipOffset = __count - 1;
_Integer __tailSize = (_Integer)(__last - __first);
_Integer __remainder;
_Integer __prevRemainder;
for ( __lookAhead = __first + __skipOffset;
__tailSize >= __count; __lookAhead += __count )
{
__tailSize -= __count;
if (*__lookAhead == __val)
{
__remainder = __skipOffset;
for (__backTrack = __lookAhead - 1;
*__backTrack == __val; --__backTrack )
{
if (--__remainder == 0)
return (__lookAhead - __skipOffset); //Success
}
if (__remainder <= __tailSize)
{
__prevRemainder = __remainder;
while ( *(++__lookAhead) == __val )
{
if ( --__remainder == 0)
return __backTrack + 1; //Success
}
__tailSize -= __prevRemainder - __remainder;
}
else
return __last; //failure
}
//__lookAhead here is always pointing
//to the element of the last mismatch.
}
}
return __last; //failure
}
/*
* Copyright (c) 2004
* 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.
*
*/
几个要点
1、 DPX search_n 至多完成 last – first 次比较，因此最坏的时间复杂度是线形的，类似于VC++和SGI的平均复杂度。但是最坏的情况是一种非常极端的，在这个算法中很少出现。另一方面，它的平均时间复杂度是O((last – first)/count)（参照第五章的测试程序A，B1，B2和C）。
2、 除了从事实上看 DPX search_n实际上检查仅仅少量的匹配数据，我能确保党在搜索范围内没有数据的时候检查的次数永远不止一次（参照第五章的测试程序D）。因此这个search_n 版本在这个使用环境下比较这些数据是非常理想的。
3、 对于上面的原因，我相信在任何情况下这个 search_n在性能上能够超过VC++和SGI版本。它仅仅当用在随机访问迭代器的时候不适合，因而它不能使用于列表和其他序列数据，仅仅提供向前的迭代（参照第五章测试程序和第六章的总结）。
5. 性能测试
到目前为止，我们看了三种版本的search_n 算法，我们从理论上讨论了运行的预期性能。在本章节，我们将观察这些算法在一台机器上运行的具体表现。特别是我们要完成一系列的性能测试，这些代码在文章的开头有它们的地址，可以下载。在后续的子节中，分别描述每一个测试和关于每一个结果的一个简短的总结。所有执行的结果都使用图形在后面表现出来了。
下面的一些符号在后面将频繁使用到：
1、 符号N，这个符号表示 search_n需要搜索的连贯的数据个数。
2、 符号M，这个符号表示 search_n搜索到的序列数据个数。
测试A
这个测试的目的是观察当随着M的增长DPX search_n算法的行为。这个测试执行三次，每次测试使用不同的N值。被搜索数据存放在一个vector中，匹配到的机率是1%。
测试程序A的结果如图A所示。图中，纵轴表示消耗的时间，横轴表示执行的次数M。这个图很明显地表示消耗的时间是随着M线形增长的，但它也表示出DPX search_n 当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的值增长的时候的性能（1百万个数据）。被搜索的数据都存储在vector 中，匹配到的机率是1%。
测试程序C的结果如图C所示。图中，纵轴表示消耗的时间，横轴表示执行的次数N。这个图中表示SGI和VC++版本的性能不受影响，DPX版本的随着N的增长性能提高。从另一方面验证了search_n执行时间复杂度为O(M/N)。
测试D
本测试程序是观察比较我们讨论的三个search_n当M和N保存常量（分别为1百万个数和32）单匹配的密度增长的时候的性能。也就是说在这个测试中我们增加匹配的可能性。被搜索的数据都存储在vector 中。
测试程序D的结果如图D所示。图中，纵轴表示消耗的时间，横轴表示匹配的密度。这个图形表示当密度增大的时候SGI和VC++版本的性能变低了，但是DPX版本几乎不受影响。这也表示出SGI和VC++版本当匹配密度增加德时候进行了多余的比较（在测试D中变差了100%），同样，DPX版本性能降低的很少（最差降低9%）。
测试E
本测试的目的是比较SGI和VC++版本的search_n对存储在列表中的数据进行搜索，当随着M的增加性能的变化。注意在这个测试中DPX search_n不能使用，因为它需要随机访问迭代器，但列表仅仅有向前迭代。N等于16是一个不变的常量，匹配到的机率是1%。
测试程序E的结果如图E所示。图中，纵轴表示消耗的时间，横轴表示执行的次数M。当在图B1和B2种比较的时候，这个图形表示其能耐优势，当使用随机迭代器的时候SGI search_n超过VC++版本的，在向前迭代器中更加体现出来了。
详细的分析
这也纵坐标都是代表了消耗的时间，但你会注意到关于这些消耗时间并不能提供任何信息。这是故意的，因为我们并不关心具体消耗的时间多少，而我们关心的是随着某一个因数的变化消耗时间的增长增长率。此外，这些消耗的时间仅仅是发生在特定机器上运行这些程序的结果，在不同的硬件和软件环境下有着不同的时间消耗。
用来测试的代码在文章的开头有下载的地址。它是非常小的代码片断，在代码中有相应的说明，我相信能够很容易地通过这些测试程序验证 search_n算法运行时的结果。
Performance graph A
Performance graph B1
Performance graph B2
Performance graph C
Performance graph D
Performance graph E
6. 结论
在本文中我们讨论了STL search_n算法的效率。特别是，我们讨论了流行的VC++和SGI版本的和介绍了新的DPX search_n算法，特别是search_n算法在使用随机访问迭代器时的性能。此外，我们在第五章我们执行了一系列的测试来验证我们预期的设想。这些讨论的结论总结如下：
· 当使用的时随机访问迭代器的时候，DPX search_n算法是最好的选择，它的平均时间复杂度最好（看第四章的第一点）并通过了测试证明（看第五章的测试A，B1，B2和C）。
· 当在更大的数据中搜索连贯的数据的时候DPX search_n算法性能是最好的（看第五章的测试A和C）当匹配机率增加的时候也是这样的（看第五章的测试D）。
· 对于向前迭代器，SGI search_n算法的性能比VC++版本的要好（看第五章的测试E）。
7. 参考
The SGI Standard Template Library.
The search_n algorithm of the SGI STL.
The VC++ Standard Template Library.
The search_n algorithm of the VC++ STL.
The Rogue Wave Standard Template Library.
The search and search_n algorithms of the Rogue Wave STL.
郑重声明：
允许复制、修改、传递或其它行为
但不准用于任何商业用途.
写于 2004/11/9 masterlee
本文地址：http://com.8s8s.com/it/it25578.htm