提高 search_n 的性能

Can search_n be more efficient? （By Jim Xochellis）

翻译 masterlee

本文讨论常用的search_n的性能，另外介绍一个新的专门处理随机访问迭代器的search_n，它的性能上要超过常规使用方法。

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;

}

* 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.

* 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

}

* 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