Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r80645 - in branches/release: boost/numeric/ublas boost/numeric/ublas/operation libs/numeric/ublas libs/numeric/ublas/doc libs/numeric/ublas/test
From: guwi17_at_[hidden]
Date: 2012-09-22 17:57:58


Author: guwi17
Date: 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
New Revision: 80645
URL: http://svn.boost.org/trac/boost/changeset/80645

Log:
merged [80483],[80487],[80586],[80591],[80592],[80599],[80600],[80624],[80625],[80643],[80644] into release:

* fix #4024

* fix #5812

* fix #7296 (hopefully ;-)

* see #7363 (must wait for a full test cycle before closing this task)

Added:
   branches/release/libs/numeric/ublas/test/test_coordinate_matrix_inplace_merge.cpp
      - copied unchanged from r80625, /trunk/libs/numeric/ublas/test/test_coordinate_matrix_inplace_merge.cpp
   branches/release/libs/numeric/ublas/test/test_coordinate_vector_inplace_merge.cpp
      - copied unchanged from r80625, /trunk/libs/numeric/ublas/test/test_coordinate_vector_inplace_merge.cpp
Properties modified:
   branches/release/boost/numeric/ublas/ (props changed)
   branches/release/boost/numeric/ublas/functional.hpp (props changed)
   branches/release/libs/numeric/ublas/ (props changed)
   branches/release/libs/numeric/ublas/doc/ (props changed)
Text files modified:
   branches/release/boost/numeric/ublas/matrix_sparse.hpp | 56 ++++++++++++++++++++++++++++++++++++++-
   branches/release/boost/numeric/ublas/operation/size.hpp | 6 ++--
   branches/release/boost/numeric/ublas/storage.hpp | 2 -
   branches/release/boost/numeric/ublas/vector_sparse.hpp | 49 ++++++++++++++++++++++++++++++++++
   branches/release/libs/numeric/ublas/test/Jamfile.v2 | 7 +++++
   branches/release/libs/numeric/ublas/test/test_triangular.cpp | 47 ++++++++++++++-------------------
   branches/release/libs/numeric/ublas/test/utils.hpp | 29 +++++++++++++-------
   7 files changed, 151 insertions(+), 45 deletions(-)

Modified: branches/release/boost/numeric/ublas/matrix_sparse.hpp
==============================================================================
--- branches/release/boost/numeric/ublas/matrix_sparse.hpp (original)
+++ branches/release/boost/numeric/ublas/matrix_sparse.hpp 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
@@ -4391,17 +4391,69 @@
             m1.swap (m2);
         }
 
+ // replacement if STL lower bound algorithm for use of inplace_merge
+ array_size_type lower_bound (array_size_type beg, array_size_type end, array_size_type target) const {
+ while (end > beg) {
+ array_size_type mid = (beg + end) / 2;
+ if (((index1_data_[mid] < index1_data_[target]) ||
+ ((index1_data_[mid] == index1_data_[target]) &&
+ (index2_data_[mid] < index2_data_[target])))) {
+ beg = mid + 1;
+ } else {
+ end = mid;
+ }
+ }
+ return beg;
+ }
+
+ // specialized replacement of STL inplace_merge to avoid compilation
+ // problems with respect to the array_triple iterator
+ void inplace_merge (array_size_type beg, array_size_type mid, array_size_type end) const {
+ array_size_type len_lef = mid - beg;
+ array_size_type len_rig = end - mid;
+
+ if (len_lef == 1 && len_rig == 1) {
+ if ((index1_data_[mid] < index1_data_[beg]) ||
+ ((index1_data_[mid] == index1_data_[beg]) && (index2_data_[mid] < index2_data_[beg])))
+ {
+ std::swap(index1_data_[beg], index1_data_[mid]);
+ std::swap(index2_data_[beg], index2_data_[mid]);
+ std::swap(value_data_[beg], value_data_[mid]);
+ }
+ } else if (len_lef > 0 && len_rig > 0) {
+ array_size_type lef_mid, rig_mid;
+ if (len_lef >= len_rig) {
+ lef_mid = (beg + mid) / 2;
+ rig_mid = lower_bound(mid, end, lef_mid);
+ } else {
+ rig_mid = (mid + end) / 2;
+ lef_mid = lower_bound(beg, mid, rig_mid);
+ }
+ std::rotate(&index1_data_[0] + lef_mid, &index1_data_[0] + mid, &index1_data_[0] + rig_mid);
+ std::rotate(&index2_data_[0] + lef_mid, &index2_data_[0] + mid, &index2_data_[0] + rig_mid);
+ std::rotate(&value_data_[0] + lef_mid, &value_data_[0] + mid, &value_data_[0] + rig_mid);
+
+ array_size_type new_mid = lef_mid + rig_mid - mid;
+ inplace_merge(beg, lef_mid, new_mid);
+ inplace_merge(new_mid, rig_mid, end);
+ }
+ }
+
         // Sorting and summation of duplicates
         BOOST_UBLAS_INLINE
         void sort () const {
             if (! sorted_ && filled_ > 0) {
                 typedef index_triple_array<index_array_type, index_array_type, value_array_type> array_triple;
                 array_triple ita (filled_, index1_data_, index2_data_, value_data_);
+#ifndef BOOST_UBLAS_COO_ALWAYS_DO_FULL_SORT
                 const typename array_triple::iterator iunsorted = ita.begin () + sorted_filled_;
                 // sort new elements and merge
                 std::sort (iunsorted, ita.end ());
- std::inplace_merge (ita.begin (), iunsorted, ita.end ());
-
+ inplace_merge(0, sorted_filled_, filled_);
+#else
+ const typename array_triple::iterator iunsorted = ita.begin ();
+ std::sort (iunsorted, ita.end ());
+#endif
                 // sum duplicates with += and remove
                 array_size_type filled = 0;
                 for (array_size_type i = 1; i < filled_; ++ i) {

Modified: branches/release/boost/numeric/ublas/operation/size.hpp
==============================================================================
--- branches/release/boost/numeric/ublas/operation/size.hpp (original)
+++ branches/release/boost/numeric/ublas/operation/size.hpp 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
@@ -304,7 +304,7 @@
 BOOST_UBLAS_INLINE
 typename vector_traits<VectorExprT>::size_type size(vector_expression<VectorExprT> const& ve)
 {
- return detail::size_by_dim_impl<Dim, vector_tag>::template apply(ve);
+ return detail::size_by_dim_impl<Dim, vector_tag>::apply(ve);
 }
 
 
@@ -321,7 +321,7 @@
 BOOST_UBLAS_INLINE
 typename matrix_traits<MatrixExprT>::size_type size(matrix_expression<MatrixExprT> const& me)
 {
- return detail::size_by_dim_impl<Dim, matrix_tag>::template apply(me);
+ return detail::size_by_dim_impl<Dim, matrix_tag>::apply(me);
 }
 
 
@@ -341,7 +341,7 @@
     detail::matrix_size_type<MatrixExprT>
>::type size(matrix_expression<MatrixExprT> const& me)
 {
- return detail::size_by_tag_impl<TagT, matrix_tag, typename matrix_traits<MatrixExprT>::orientation_category>::template apply(me);
+ return detail::size_by_tag_impl<TagT, matrix_tag, typename matrix_traits<MatrixExprT>::orientation_category>::apply(me);
 }
 
 }}} // Namespace boost::numeric::ublas

Modified: branches/release/boost/numeric/ublas/storage.hpp
==============================================================================
--- branches/release/boost/numeric/ublas/storage.hpp (original)
+++ branches/release/boost/numeric/ublas/storage.hpp 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
@@ -1564,7 +1564,6 @@
 
     template <class V>
     class index_pair :
- private boost::noncopyable,
         public container_reference<V> {
 
         typedef index_pair<V> self_type;
@@ -1734,7 +1733,6 @@
 
     template <class M>
     class index_triple :
- private boost::noncopyable,
         public container_reference<M> {
 
         typedef index_triple<M> self_type;

Modified: branches/release/boost/numeric/ublas/vector_sparse.hpp
==============================================================================
--- branches/release/boost/numeric/ublas/vector_sparse.hpp (original)
+++ branches/release/boost/numeric/ublas/vector_sparse.hpp 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
@@ -1801,16 +1801,63 @@
             v1.swap (v2);
         }
 
+ // replacement if STL lower bound algorithm for use of inplace_merge
+ size_type lower_bound (size_type beg, size_type end, size_type target) const {
+ while (end > beg) {
+ size_type mid = (beg + end) / 2;
+ if (index_data_[mid] < index_data_[target]) {
+ beg = mid + 1;
+ } else {
+ end = mid;
+ }
+ }
+ return beg;
+ }
+
+ // specialized replacement of STL inplace_merge to avoid compilation
+ // problems with respect to the array_triple iterator
+ void inplace_merge (size_type beg, size_type mid, size_type end) const {
+ size_type len_lef = mid - beg;
+ size_type len_rig = end - mid;
+
+ if (len_lef == 1 && len_rig == 1) {
+ if (index_data_[mid] < index_data_[beg]) {
+ std::swap(index_data_[beg], index_data_[mid]);
+ std::swap(value_data_[beg], value_data_[mid]);
+ }
+ } else if (len_lef > 0 && len_rig > 0) {
+ size_type lef_mid, rig_mid;
+ if (len_lef >= len_rig) {
+ lef_mid = (beg + mid) / 2;
+ rig_mid = lower_bound(mid, end, lef_mid);
+ } else {
+ rig_mid = (mid + end) / 2;
+ lef_mid = lower_bound(beg, mid, rig_mid);
+ }
+ std::rotate(&index_data_[0] + lef_mid, &index_data_[0] + mid, &index_data_[0] + rig_mid);
+ std::rotate(&value_data_[0] + lef_mid, &value_data_[0] + mid, &value_data_[0] + rig_mid);
+
+ size_type new_mid = lef_mid + rig_mid - mid;
+ inplace_merge(beg, lef_mid, new_mid);
+ inplace_merge(new_mid, rig_mid, end);
+ }
+ }
+
         // Sorting and summation of duplicates
         BOOST_UBLAS_INLINE
         void sort () const {
             if (! sorted_ && filled_ > 0) {
                 typedef index_pair_array<index_array_type, value_array_type> array_pair;
                 array_pair ipa (filled_, index_data_, value_data_);
+#ifndef BOOST_UBLAS_COO_ALWAYS_DO_FULL_SORT
                 const typename array_pair::iterator iunsorted = ipa.begin () + sorted_filled_;
                 // sort new elements and merge
                 std::sort (iunsorted, ipa.end ());
- std::inplace_merge (ipa.begin (), iunsorted, ipa.end ());
+ inplace_merge(0, sorted_filled_, filled_);
+#else
+ const typename array_pair::iterator iunsorted = ipa.begin ();
+ std::sort (iunsorted, ipa.end ());
+#endif
 
                 // sum duplicates with += and remove
                 size_type filled = 0;

Modified: branches/release/libs/numeric/ublas/test/Jamfile.v2
==============================================================================
--- branches/release/libs/numeric/ublas/test/Jamfile.v2 (original)
+++ branches/release/libs/numeric/ublas/test/Jamfile.v2 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
@@ -157,6 +157,9 @@
           [ run test_assignment.cpp
           ]
           [ run test_triangular.cpp
+ :
+ :
+ : <library>/boost/timer//boost_timer
           ]
           [ run test_ticket7296.cpp
           ]
@@ -181,4 +184,8 @@
         : test_inplace_solve_mvov
         :
       ]
+ [ run test_coordinate_vector_inplace_merge.cpp
+ ]
+ [ run test_coordinate_matrix_inplace_merge.cpp
+ ]
     ;

Modified: branches/release/libs/numeric/ublas/test/test_triangular.cpp
==============================================================================
--- branches/release/libs/numeric/ublas/test/test_triangular.cpp (original)
+++ branches/release/libs/numeric/ublas/test/test_triangular.cpp 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
@@ -6,6 +6,7 @@
 #include <boost/numeric/ublas/triangular.hpp>
 #include <boost/numeric/ublas/io.hpp>
 
+#include <boost/timer/timer.hpp>
 
 #include <sys/times.h>
 #include <sys/time.h>
@@ -33,7 +34,7 @@
 
 
 int main() {
- const int n=10000;
+ const int n=7000;
 #if 1
   ublas::compressed_matrix<double, ublas::row_major> mat_row_upp(n, n);
   ublas::compressed_matrix<double, ublas::column_major> mat_col_upp(n, n);
@@ -76,62 +77,54 @@
 
   std::cerr << "Starting..." << std::endl;
   {
- clock_t start = clock();
+ boost::timer::auto_cpu_timer t(std::cerr, "col_low x: %t sec CPU, %w sec real\n");
     ublas::vector<double> x(b);
     ublas::inplace_solve(mat_col_low, x, ublas::lower_tag());
- std::cerr << "Col_low x: " << clock()-start << std::endl;
     std::cerr << "delta: " << diff(mat_col_low, x, b) << "\n";
   }
   {
- clock_t start = clock();
+ boost::timer::auto_cpu_timer t(std::cerr, "row_low x: %t sec CPU, %w sec real\n");
     ublas::vector<double> x(b);
     ublas::inplace_solve(mat_row_low, x, ublas::lower_tag());
- std::cerr << "Row_low x: " << clock()-start << std::endl;
     std::cerr << "delta: " << diff(mat_row_low, x, b) << "\n";
   }
 
   {
- clock_t start = clock();
+ boost::timer::auto_cpu_timer t(std::cerr, "col_upp x: %t sec CPU, %w sec real\n");
     ublas::vector<double> x(b);
     ublas::inplace_solve(mat_col_upp, x, ublas::upper_tag());
- std::cerr << "col_upp x: " << clock()-start << std::endl;
     std::cerr << "delta: " << diff(mat_col_upp, x, b) << "\n";
   }
   {
- clock_t start = clock();
+ boost::timer::auto_cpu_timer t(std::cerr, "row_upp x: %t sec CPU, %w sec real\n");
     ublas::vector<double> x(b);
     ublas::inplace_solve(mat_row_upp, x, ublas::upper_tag());
- std::cerr << "row_upp x: " << clock()-start << std::endl;
     std::cerr << "delta: " << diff(mat_row_upp, x, b) << "\n";
   }
 
-// {
-// clock_t start = clock();
-// ublas::vector<double> x(b);
-// ublas::inplace_solve(x, mat_col_low, ublas::lower_tag());
-// std::cerr << "x col_low: " << clock()-start << std::endl;
-// std::cerr << "delta: " << diff(x, mat_col_low, b) << "\n";
-// }
   {
- clock_t start = clock();
+ boost::timer::auto_cpu_timer t(std::cerr, "x col_low: %t sec CPU, %w sec real\n");
+ ublas::vector<double> x(b);
+ ublas::inplace_solve(x, mat_col_low, ublas::lower_tag());
+ std::cerr << "delta: " << diff(x, mat_col_low, b) << "\n";
+ }
+ {
+ boost::timer::auto_cpu_timer t(std::cerr, "x row_low: %t sec CPU, %w sec real\n");
     ublas::vector<double> x(b);
     ublas::inplace_solve(x, mat_row_low, ublas::lower_tag());
- std::cerr << "x row_low: " << clock()-start << std::endl;
     std::cerr << "delta: " << diff(x, mat_row_low, b) << "\n";
   }
 
-// {
-// clock_t start = clock();
-// ublas::vector<double> x(b);
-// ublas::inplace_solve(x, mat_col_upp, ublas::upper_tag());
-// std::cerr << "x col_upp: " << clock()-start << std::endl;
-// std::cerr << "delta: " << diff(x, mat_col_upp, b) << "\n";
-// }
   {
- clock_t start = clock();
+ boost::timer::auto_cpu_timer t(std::cerr, "x col_upp: %t sec CPU, %w sec real\n");
+ ublas::vector<double> x(b);
+ ublas::inplace_solve(x, mat_col_upp, ublas::upper_tag());
+ std::cerr << "delta: " << diff(x, mat_col_upp, b) << "\n";
+ }
+ {
+ boost::timer::auto_cpu_timer t(std::cerr, "x row_upp: %t sec CPU, %w sec real\n");
     ublas::vector<double> x(b);
     ublas::inplace_solve(x, mat_row_upp, ublas::upper_tag());
- std::cerr << "x row_upp: " << clock()-start << std::endl;
     std::cerr << "delta: " << diff(x, mat_row_upp, b) << "\n";
   }
 

Modified: branches/release/libs/numeric/ublas/test/utils.hpp
==============================================================================
--- branches/release/libs/numeric/ublas/test/utils.hpp (original)
+++ branches/release/libs/numeric/ublas/test/utils.hpp 2012-09-22 17:57:57 EDT (Sat, 22 Sep 2012)
@@ -54,6 +54,9 @@
 
 #include <boost/numeric/ublas/detail/config.hpp>
 #include <boost/numeric/ublas/traits.hpp>
+
+#include <boost/math/special_functions/fpclassify.hpp> // isnan, isinf
+
 #include <cmath>
 #include <complex>
 #include <cstddef>
@@ -63,13 +66,17 @@
 
 namespace boost { namespace numeric { namespace ublas { namespace test { namespace detail { namespace /*<unnamed>*/ {
 
+ using ::std::abs;
+ using ::std::max;
+
 /// Check if the given complex number is a NaN.
+// read the comments in fpclassify as well
 template <typename T>
 BOOST_UBLAS_INLINE
-bool isnan(::std::complex<T> const& z)
+bool (isnan)(::std::complex<T> const& z)
 {
         // According to IEEE, NaN is different even by itself
- return (z != z) || ::std::isnan(z.real()) || ::std::isnan(z.imag());
+ return (z != z) || (boost::math::isnan)(z.real()) || (boost::math::isnan)(z.imag());
 }
 
 /// Check if two (real) numbers are close each other (wrt a given tolerance).
@@ -80,12 +87,12 @@
         typedef typename promote_traits<typename promote_traits<T1,T2>::promote_type,
                                                                         T3>::promote_type real_type;
 
- if (::std::isnan(x) || ::std::isnan(y))
+ if ((boost::math::isnan)(x) || (boost::math::isnan)(y))
     {
         // According to IEEE, NaN is different even by itself
         return false;
     }
- return ::std::abs(x-y) <= (::std::max(static_cast<real_type>(::std::abs(x)), static_cast<real_type>(::std::abs(y)))*tol);
+ return abs(x-y) <= (max(static_cast<real_type>(abs(x)), static_cast<real_type>(abs(y)))*tol);
 }
 
 /// Check if two complex numbers are close each other (wrt a given tolerance).
@@ -96,14 +103,15 @@
         typedef typename promote_traits<typename promote_traits<T1,T2>::promote_type,
                                                                         T3>::promote_type real_type;
 
- if (isnan(x) || isnan(y))
+ if ((isnan)(x) || (isnan)(y))
     {
         // According to IEEE, NaN is different even by itself
         return false;
     }
         ::std::complex<real_type> xx(x);
         ::std::complex<real_type> yy(y);
- return ::std::abs(xx-yy) <= (::std::max(::std::abs(xx), ::std::abs(yy))*tol);
+
+ return abs(xx-yy) <= (max(abs(xx), abs(yy))*tol);
 }
 
 /// Check if two (real) numbers are close each other (wrt a given tolerance).
@@ -114,12 +122,12 @@
         typedef typename promote_traits<typename promote_traits<T1,T2>::promote_type,
                                                                         T3>::promote_type real_type;
 
- if (::std::isnan(x) || ::std::isnan(y))
+ if ((boost::math::isnan)(x) || (boost::math::isnan)(y))
     {
         // According to IEEE, NaN is different even by itself
         return false;
     }
- return ::std::abs(x-y)/::std::abs(y) <= tol;
+ return abs(x-y)/abs(y) <= tol;
 }
 
 /// Check if two complex numbers are close each other (wrt a given tolerance).
@@ -130,14 +138,15 @@
         typedef typename promote_traits<typename promote_traits<T1,T2>::promote_type,
                                                                         T3>::promote_type real_type;
 
- if (isnan(x) || isnan(y))
+ if ((isnan)(x) || (isnan)(y))
     {
         // According to IEEE, NaN is different even by itself
         return false;
     }
         ::std::complex<real_type> xx(x);
         ::std::complex<real_type> yy(y);
- return ::std::abs(xx-yy)/::std::abs(yy) <= tol;
+
+ return abs(xx-yy)/abs(yy) <= tol;
 }
 
 }}}}}} // Namespace boost::numeric::ublas::test::detail::<unnamed>


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk