diff options
| author | Lorry Tar Creator <lorry-tar-importer@baserock.org> | 2013-06-25 22:59:01 +0000 |
|---|---|---|
| committer | <> | 2013-09-27 11:49:28 +0000 |
| commit | 8c4528713d907ee2cfd3bfcbbad272c749867f84 (patch) | |
| tree | c09e2ce80f47b90c85cc720f5139089ad9c8cfff /libs/algorithm/minmax/doc | |
| download | boost-tarball-baserock/morph.tar.gz | |
Imported from /home/lorry/working-area/delta_boost-tarball/boost_1_54_0.tar.bz2.boost_1_54_0baserock/morph
Diffstat (limited to 'libs/algorithm/minmax/doc')
| -rw-r--r-- | libs/algorithm/minmax/doc/minmax_benchs.html | 524 | ||||
| -rw-r--r-- | libs/algorithm/minmax/doc/minmax_synopsis.html | 127 |
2 files changed, 651 insertions, 0 deletions
diff --git a/libs/algorithm/minmax/doc/minmax_benchs.html b/libs/algorithm/minmax/doc/minmax_benchs.html new file mode 100644 index 000000000..1db516d7d --- /dev/null +++ b/libs/algorithm/minmax/doc/minmax_benchs.html @@ -0,0 +1,524 @@ +<!doctype html public "-//w3c//dtd html 4.0 transitional//en"> +<html> +<head> + <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> + <meta name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]"> + <meta name="Author" content="Herve Bronnimann"> + <meta name="Description" content="Small library to propose minmax_element algorithm."> + <title>Boost minmax library</title> +</head> +<body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000"> + +<center> +<h1> +Minmax_element Performance</h1></center> + +<h3> +<a NAME="Performance"></a><b>About performance</b></h3> +Of course, there are many factors that affect the performance of an algorithm. +The number of comparison is only one, but also branch prediction, pipelining, +locality of reference (affects cache efficiency), etc. In practice, +we observe that when the iterator type is a pointer, +<tt>boost::minmax_element</tt> +is only a tad slower than +<tt>std::min_element</tt>, and is even faster +than +<tt>boost::first_min_last_max_element</tt>! This is even more true +for slower iterators (<tt>list<>::iterator</tt> or +<tt>map<>iterator</tt> +for instance). The following experiments were conducted on a Pentium III +500 Mhz running Linux and compiled with g++, version 2.95.2, flags -O3. +In the tables, we use different distributions: <i>Identical</i> means that +all the elements are identical, <i>2-valued</i> means that we replace the +second half of the identical elements by a distinct element, <i>increasing</i> +means that all the elements are distinct and in increasing order, <i>decrea</i>sing +is the reverse, and <i>random</i> is produced by random_shuffle. +<br> +The program that created these tables is included in the distribution, +under <a href="../example/minmax_timer.cpp">minmax_timer.cpp</a> +<br> +<center><table BORDER NOSAVE > +<tr NOSAVE> +<td NOSAVE><b>vector<int>::iterator</b></td> + +<td>Identical</td> + +<td>2-valued</td> + +<td>Increasing</td> + +<td>Decreasing</td> + +<td>Random</td> +</tr> + +<tr> +<td>std::min_element</td> + +<td>23.26M/s</td> + +<td>23.26M/s</td> + +<td>23.15M/s</td> + +<td>22.94M/s</td> + +<td>22.94M/s</td> +</tr> + +<tr> +<td>std::max_element</td> + +<td>23.26M/s</td> + +<td>23.26M/s</td> + +<td>23.15M/s</td> + +<td>22.94M/s</td> + +<td>22.62M/s</td> +</tr> + +<tr> +<td>boost::first_min_element</td> + +<td>23.15M/s</td> + +<td>23.04M/s</td> + +<td>23.04M/s</td> + +<td>22.94M/s</td> + +<td>22.83M/s</td> +</tr> + +<tr> +<td>boost::last_min_element</td> + +<td>23.26M/s</td> + +<td>23.26M/s</td> + +<td>23.26M/s</td> + +<td>22.83M/s</td> + +<td>16.23M/s</td> +</tr> + +<tr> +<td>boost::first_max_element</td> + +<td>23.15M/s</td> + +<td>23.26M/s</td> + +<td>23.15M/s</td> + +<td>23.04M/s</td> + +<td>22.93M/s</td> +</tr> + +<tr> +<td>boost::last_max_element</td> + +<td>23.26M/s</td> + +<td>23.15M/s</td> + +<td>23.15M/s</td> + +<td>22.94M/s</td> + +<td>16.18M/s</td> +</tr> + +<tr> +<td>boost::minmax_element</td> + +<td>21.83M/s</td> + +<td>21.83M/s</td> + +<td>21.83M/s</td> + +<td>21.55M/s</td> + +<td>17.79M/s</td> +</tr> + +<tr> +<td>boost::first_min_last_max_element</td> + +<td>18.52M/s</td> + +<td>18.38M/s</td> + +<td>18.38M/s</td> + +<td>18.94M/s</td> + +<td>16.29M/s</td> +</tr> + +<tr> +<td>boost::last_min_first_max_element</td> + +<td>20.08M/s</td> + +<td>20.83M/s</td> + +<td>20.75M/s</td> + +<td>19.76M/s</td> + +<td>15.87M/s</td> +</tr> + +<tr> +<td>boost::last_min_last_max_element</td> + +<td>18.66M/s</td> + +<td>19.69M/s</td> + +<td>19.69M/s</td> + +<td>19.23M/s</td> + +<td>15.77M/s</td> +</tr> + +<caption ALIGN=BOTTOM>Number of elements per second for standard vector +container iterators</caption> +</table></center> + +<center><table BORDER NOSAVE > +<tr NOSAVE> +<td NOSAVE><b>list<int>::iterator</b></td> + +<td>Identical</td> + +<td>2-valued</td> + +<td>Increasing</td> + +<td>Decreasing</td> + +<td>Random</td> +</tr> + +<tr> +<td>std::min_element</td> + +<td>5.8M/s</td> + +<td>5.8M/s</td> + +<td>5.80M/s</td> + +<td>5.73M/s</td> + +<td>5.73M/s</td> +</tr> + +<tr> +<td>std::max_element</td> + +<td>5.81M/s</td> + +<td>5.81M/s</td> + +<td>5.78M/s</td> + +<td>5.73M/s</td> + +<td>5.75M/s</td> +</tr> + +<tr> +<td>boost::first_min_element</td> + +<td>5.81M/s</td> + +<td>5.81M/s</td> + +<td>5.79M/s</td> + +<td>5.75M/s</td> + +<td>5.73M/s</td> +</tr> + +<tr> +<td>boost::last_min_element</td> + +<td>5.81M/s</td> + +<td>5.80M/s</td> + +<td>5.79M/s</td> + +<td>5.73M/s</td> + +<td>5.03M/s</td> +</tr> + +<tr> +<td>boost::first_max_element</td> + +<td>5.81M/s</td> + +<td>5.80M/s</td> + +<td>5.78M/s</td> + +<td>5.74M/s</td> + +<td>5.73M/s</td> +</tr> + +<tr> +<td>boost::last_max_element</td> + +<td>5.81M/s</td> + +<td>5.80M/s</td> + +<td>5.79M/s</td> + +<td>5.73M/s</td> + +<td>5.07M/s</td> +</tr> + +<tr> +<td>boost::minmax_element</td> + +<td>5.68M/s</td> + +<td>5.80M/s</td> + +<td>5.66M/s</td> + +<td>5.74M/s</td> + +<td>5.30M/s</td> +</tr> + +<tr> +<td>boost::first_min_last_max_element</td> + +<td>5.79M/s</td> + +<td>5.81M/s</td> + +<td>5.78M/s</td> + +<td>5.73M/s</td> + +<td>5.04M/s</td> +</tr> + +<tr> +<td>boost::last_min_first_max_element</td> + +<td>5.69M/s</td> + +<td>5.79M/s</td> + +<td>5.69M/s</td> + +<td>5.73M/s</td> + +<td>4.84M/s</td> +</tr> + +<tr> +<td>boost::last_min_last_max_element</td> + +<td>5.61M/s</td> + +<td>5.79M/s</td> + +<td>5.64M/s</td> + +<td>5.74M/s</td> + +<td>4.75M/s</td> +</tr> + +<caption ALIGN=BOTTOM>Runtimes for standard list container iterators</caption> +</table></center> + +<center><table BORDER NOSAVE > +<tr NOSAVE> +<td NOSAVE><b>multiset<int>::iterator</b></td> + +<td>Identical</td> + +<td>2-valued</td> + +<td>Increasing</td> + +<td>Decreasing</td> + +<td>Random</td> +</tr> + +<tr> +<td>std::min_element</td> + +<td>4.03M/s</td> + +<td>4.04M/s</td> + +<td>4.02M/s</td> + +<td>4.04M/s</td> + +<td>2.97M/s</td> +</tr> + +<tr> +<td>std::max_element3.007M</td> + +<td>4.02M/s</td> + +<td>4.02M/s</td> + +<td>4.01M/s</td> + +<td>4.02M/s</td> + +<td>2.96M/s</td> +</tr> + +<tr> +<td>boost::first_min_element</td> + +<td>4.01M/s</td> + +<td>4.04M/s</td> + +<td>4.03M/s</td> + +<td>4.04M/s</td> + +<td>3.01M/s</td> +</tr> + +<tr> +<td>boost::last_min_element</td> + +<td>4.03M/s</td> + +<td>4.04M/s</td> + +<td>4.04M/s</td> + +<td>4.04M/s</td> + +<td>3.00M/s</td> +</tr> + +<tr> +<td>boost::first_max_element</td> + +<td>4.04M/s</td> + +<td>4.04M/s</td> + +<td>4.04M/s</td> + +<td>4.06M/s</td> + +<td>3.01M/s</td> +</tr> + +<tr> +<td>boost::last_max_element</td> + +<td>4.04M/s</td> + +<td>4.04M/s</td> + +<td>4.03M/s</td> + +<td>4.04M/s</td> + +<td>3.00M/s</td> +</tr> + +<tr> +<td>boost::minmax_element</td> + +<td>3.98M/s</td> + +<td>3.99M/s</td> + +<td>3.98M/s</td> + +<td>3.99M/s</td> + +<td>3.00M/s</td> +</tr> + +<tr> +<td>boost::first_min_last_max_element</td> + +<td>3.99M/s</td> + +<td>3.98M/s</td> + +<td>3.97M/s</td> + +<td>3.99M/s</td> + +<td>2.99M/s</td> +</tr> + +<tr> +<td>boost::last_min_first_max_element</td> + +<td>3.97M/s</td> + +<td>3.98M/s</td> + +<td>3.96M/s</td> + +<td>3.98M/s</td> + +<td>3.00M/s</td> +</tr> + +<tr> +<td>boost::last_min_last_max_element</td> + +<td>4.00M/s</td> + +<td>4.00M/s</td> + +<td>4.00M/s</td> + +<td>4.02M/s</td> + +<td>2.97M/s</td> +</tr> + +<caption ALIGN=BOTTOM>Runtimes for standard set/multiset container iterators</caption> +</table></center> + +<hr SIZE="6"> +<br>Last modified 2004-06-28 +<p><font face="Arial,Helvetica"><font size=-1>© Copyright Hervé +Brönnimann, Polytechnic University, 2002--2004. +Use, modification, and distribution is subject to the Boost Software +License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at +<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>) +</font></font> +</body> +</html> diff --git a/libs/algorithm/minmax/doc/minmax_synopsis.html b/libs/algorithm/minmax/doc/minmax_synopsis.html new file mode 100644 index 000000000..1651a13f1 --- /dev/null +++ b/libs/algorithm/minmax/doc/minmax_synopsis.html @@ -0,0 +1,127 @@ +<!doctype html public "-//w3c//dtd html 4.0 transitional//en"> +<html> +<head> + <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> + <meta name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]"> + <meta name="Author" content="Herve Bronnimann"> + <meta name="Description" content="Small library to propose minmax_element algorithm."> + <title>Boost minmax library synopsis</title> +</head> +<body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000"> + +<center> +<h1> +Minmax_element complete synopsis</h1></center> + +<h3> +Synopsis of <tt><boost/algorithm/minmax.hpp></tt></h3> + +<pre>#include <boost/tuple/tuple.hpp> + +namespace boost { + + template <class T> + tuple<T const&, T const&> > + minmax(const T& a, const T& b); + + template <class T, class <a href="http://www.sgi.com/tech/stl/ BinaryPredicate.html">BinaryPredicate</a>> + tuple<T const&, T const&> > + minmax(const T& a, const T& b, BinaryPredicate comp); + +} +</pre> + +<h3> +Synopsis of <tt><boost/algorithm/minmax_element.hpp></tt></h3> + +<pre>#include <utility> //for std::pair + +namespace boost { + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + std::pair<ForwardIterator,ForwardIterator> + minmax_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + std::pair<ForwardIterator,ForwardIterator> + minmax_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + // Variants + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + ForwardIterator first_min_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + ForwardIterator first_min_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + ForwardIterator last_min_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + ForwardIterator last_min_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + ForwardIterator first_max_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + ForwardIterator first_max_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + ForwardIterator last_max_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + ForwardIterator last_max_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + std::pair<ForwardIterator,ForwardIterator> + first_min_first_max_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + std::pair<ForwardIterator,ForwardIterator> + first_min_first_max_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + std::pair<ForwardIterator,ForwardIterator> + first_min_last_max_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + std::pair<ForwardIterator,ForwardIterator> + first_min_last_max_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + std::pair<ForwardIterator,ForwardIterator> + last_min_first_max_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + std::pair<ForwardIterator,ForwardIterator> + last_min_first_max_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>> + std::pair<ForwardIterator,ForwardIterator> + last_min_last_max_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>> + std::pair<ForwardIterator,ForwardIterator> + last_min_last_max_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + +}</pre> + +<hr SIZE="6"> +<br>Last modified 2002-07-01 +<p><font face="Arial,Helvetica"><font size=-1>© Copyright Hervé +Brönnimann, Polytechnic University, 2002--2004. +Use, modification, and distribution is subject to the Boost Software +License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at +<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>) +</font></font> +</body> +</html> |