Module: ppl/ppl Branch: sparse_matrices Commit: f3957a85aeb8243fe82d015780a17d7601126865 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f3957a85aeb82...
Author: Marco Poletti poletti.marco@gmail.com Date: Wed Mar 24 16:24:38 2010 +0100
Unlimited_Sparse_Row_Std_Vector_Backend: add and use sequential_search_treshold.
---
...Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh | 5 +++++ ...imited_Sparse_Row_Std_Vector_Backend.inlines.hh | 18 ++++++++++++++++++ 2 files changed, 23 insertions(+), 0 deletions(-)
diff --git a/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh b/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh index a479672..370feba 100644 --- a/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh +++ b/src/Unlimited_Sparse_Row_Std_Vector_Backend.defs.hh @@ -57,6 +57,11 @@ private: Unlimited_Sparse_Row_Std_Vector_Backend::key_value_comparison<Compare> key_value_compare(const Compare& comp);
+ //! This is the number of sequential comparisons after which binary search + //! is performed. This affects performance, but not correctness. + //! Some methods do one more comparison. + static const dimension_type sequential_search_treshold = 3; + public: //! Needed to satisfy the backend requirements. //! This is not a typedef to allow overloading of methods with both types. diff --git a/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh b/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh index c7c8776..02f3696 100644 --- a/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh +++ b/src/Unlimited_Sparse_Row_Std_Vector_Backend.inlines.hh @@ -143,6 +143,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::dangerous_iterator Unlimited_Sparse_Row_Std_Vector_Backend ::lower_bound_dangerous(const dimension_type k, dangerous_iterator itr) { PPL_ASSERT(itr == end_dangerous() || (*itr).first <= k); + for (dimension_type i = sequential_search_treshold; i-- > 0; ) { + if (itr == end_dangerous() || (*itr).first >= k) + return itr; + ++itr; + } + // Now perform binary search. return std::lower_bound(itr, end_dangerous(), k, value_key_compare(std::less<dimension_type>())); } @@ -162,6 +168,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::iterator Unlimited_Sparse_Row_Std_Vector_Backend ::lower_bound(const dimension_type k, iterator itr) { PPL_ASSERT(itr == end() || (*itr).first <= k); + for (dimension_type i = sequential_search_treshold; i-- > 0; ) { + if (itr == end() || (*itr).first >= k) + return itr; + ++itr; + } + // Now perform binary search. return std::lower_bound(itr, end(), k, value_key_compare(std::less<dimension_type>())); } @@ -181,6 +193,12 @@ inline Unlimited_Sparse_Row_Std_Vector_Backend::const_iterator Unlimited_Sparse_Row_Std_Vector_Backend ::lower_bound(const dimension_type k, const_iterator itr1) const { PPL_ASSERT(itr1 == end() || (*itr1).first <= k); + for (dimension_type i = sequential_search_treshold; i-- > 0; ) { + if (itr1 == end() || (*itr1).first >= k) + return itr1; + ++itr1; + } + // Now perform binary search. return std::lower_bound(itr1, end(), k, value_key_compare(std::less<dimension_type>())); }