Minmax_element 的性能
關於性能
當然，影響算法性能的因素有很多。比較的次數只是其中之一，還有分支預測、流水線、局部引用(影響緩存的效率)，等等。在實踐中，我們觀察到，當迭代器類
型為指針時，boost::minmax_element
只比
std::min_element 慢一點點，而比
boost::first_min_last_max_element 快很多！對於更慢的迭代器更是這樣(list<>::iterator
或
map<>iterator
for instance)。以下試驗是在一個運行 Linux 的 Pentium III
500 Mhz 平台上進行的，用 g++ 編譯，版本 2.95.2，標誌 -O3.
在下列表中，我們用了不同的元素分佈：Identical 表示所有元素都是一樣的，2-valued
表示後一半元素是另一個值，increasing
表示所有元素都不同且為升序，decreasing
則相反為降序，random 則是用 random_shuffle 生成數據。
生成以下表格的程序包含在發佈包中，文件為 minmax_timer.cpp
| vector<int>::iterator |
Identical |
2-valued |
Increasing |
Decreasing |
Random |
| std::min_element |
23.26M/s |
23.26M/s |
23.15M/s |
22.94M/s |
22.94M/s |
| std::max_element |
23.26M/s |
23.26M/s |
23.15M/s |
22.94M/s |
22.62M/s |
| boost::first_min_element |
23.15M/s |
23.04M/s |
23.04M/s |
22.94M/s |
22.83M/s |
| boost::last_min_element |
23.26M/s |
23.26M/s |
23.26M/s |
22.83M/s |
16.23M/s |
| boost::first_max_element |
23.15M/s |
23.26M/s |
23.15M/s |
23.04M/s |
22.93M/s |
| boost::last_max_element |
23.26M/s |
23.15M/s |
23.15M/s |
22.94M/s |
16.18M/s |
| boost::minmax_element |
21.83M/s |
21.83M/s |
21.83M/s |
21.55M/s |
17.79M/s |
| boost::first_min_last_max_element |
18.52M/s |
18.38M/s |
18.38M/s |
18.94M/s |
16.29M/s |
| boost::last_min_first_max_element |
20.08M/s |
20.83M/s |
20.75M/s |
19.76M/s |
15.87M/s |
| boost::last_min_last_max_element |
18.66M/s |
19.69M/s |
19.69M/s |
19.23M/s |
15.77M/s |
對於標準 vector
容器的迭代器，每秒處理的元素數量
| list<int>::iterator |
Identical |
2-valued |
Increasing |
Decreasing |
Random |
| std::min_element |
5.8M/s |
5.8M/s |
5.80M/s |
5.73M/s |
5.73M/s |
| std::max_element |
5.81M/s |
5.81M/s |
5.78M/s |
5.73M/s |
5.75M/s |
| boost::first_min_element |
5.81M/s |
5.81M/s |
5.79M/s |
5.75M/s |
5.73M/s |
| boost::last_min_element |
5.81M/s |
5.80M/s |
5.79M/s |
5.73M/s |
5.03M/s |
| boost::first_max_element |
5.81M/s |
5.80M/s |
5.78M/s |
5.74M/s |
5.73M/s |
| boost::last_max_element |
5.81M/s |
5.80M/s |
5.79M/s |
5.73M/s |
5.07M/s |
| boost::minmax_element |
5.68M/s |
5.80M/s |
5.66M/s |
5.74M/s |
5.30M/s |
| boost::first_min_last_max_element |
5.79M/s |
5.81M/s |
5.78M/s |
5.73M/s |
5.04M/s |
| boost::last_min_first_max_element |
5.69M/s |
5.79M/s |
5.69M/s |
5.73M/s |
4.84M/s |
| boost::last_min_last_max_element |
5.61M/s |
5.79M/s |
5.64M/s |
5.74M/s |
4.75M/s |
對於標準 list 容器的迭代器的運行時間
| multiset<int>::iterator |
Identical |
2-valued |
Increasing |
Decreasing |
Random |
| std::min_element |
4.03M/s |
4.04M/s |
4.02M/s |
4.04M/s |
2.97M/s |
| std::max_element3.007M |
4.02M/s |
4.02M/s |
4.01M/s |
4.02M/s |
2.96M/s |
| boost::first_min_element |
4.01M/s |
4.04M/s |
4.03M/s |
4.04M/s |
3.01M/s |
| boost::last_min_element |
4.03M/s |
4.04M/s |
4.04M/s |
4.04M/s |
3.00M/s |
| boost::first_max_element |
4.04M/s |
4.04M/s |
4.04M/s |
4.06M/s |
3.01M/s |
| boost::last_max_element |
4.04M/s |
4.04M/s |
4.03M/s |
4.04M/s |
3.00M/s |
| boost::minmax_element |
3.98M/s |
3.99M/s |
3.98M/s |
3.99M/s |
3.00M/s |
| boost::first_min_last_max_element |
3.99M/s |
3.98M/s |
3.97M/s |
3.99M/s |
2.99M/s |
| boost::last_min_first_max_element |
3.97M/s |
3.98M/s |
3.96M/s |
3.98M/s |
3.00M/s |
| boost::last_min_last_max_element |
4.00M/s |
4.00M/s |
4.00M/s |
4.02M/s |
2.97M/s |
對於標準 set/multiset 容器的迭代器的運行時間
Last modified 2004-06-28
©
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 License_1_0.txt
or copy at
http://www.boost.org/LICENSE_1_0.txt)