Minmax_element 的性能

關於性能

當然,影響算法性能的因素有很多。比較的次數只是其中之一,還有分支預測、流水線、局部引用(影響緩存的效率),等等。在實踐中,我們觀察到,當迭代器類 型為指針時,boost::minmax_element 只比 std::min_element 慢一點點,而比 boost::first_min_last_max_element 快很多!對於更慢的迭代器更是這樣(list<>::iteratormap<>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)