This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[v3] More work on <random>


Hi,

tested x86_64-linux, committed to mainline.

Paolo.

/////////////
2009-06-14  Paolo Carlini  <paolo.carlini@oracle.com>

	* include/bits/random.tcc (discrete_distribution<>::param_type::
      	param_type(size_t, double, double, _Func),
	discrete_distribution<>::operator()(_UniformRandomNumberGenerator&,
	const param_type&)): Tidy.
	(piecewise_constant_distribution<>::param_type::_M_initialize):
	Use reserve, fix.
	(piecewise_constant_distribution<>::param_type::
	param_type(initializer_list<>, _Func),
	piecewise_constant_distribution<>::param_type::
	param_type(size_t, _RealType, _RealType, _Func),
       	piecewise_linear_distribution<>::param_type::
	param_type(initializer_list<>, _Func),
       	piecewise_linear_distribution<>::param_type::
	param_type(size_t, _RealType, _RealType, _Func)): Use reserve, tidy.
	(piecewise_constant_distribution<>::param_type::
	param_type(_InputIteratorB, _InputIteratorB, _InputIteratorW),
	piecewise_constant_distribution<>::
	operator()(_UniformRandomNumberGenerator&, const param_type&),
      	piecewise_linear_distribution<>::
	operator()(_UniformRandomNumberGenerator&, const param_type&)): Fix.
	(operator>>(std::basic_istream<>&,
	piecewise_constant_distribution<>&),
	operator>>(std::basic_istream<>&, piecewise_linear_distribution<>&)):
	Use reserve.
	* include/bits/random.h: Minor cosmetic changes.
Index: include/bits/random.tcc
===================================================================
--- include/bits/random.tcc	(revision 148467)
+++ include/bits/random.tcc	(working copy)
@@ -1985,31 +1985,32 @@
 	  return;
 	}
 
-      double __sum = std::accumulate(_M_prob.begin(), _M_prob.end(), 0.0);
-      //  Now normalize the densities.
+      const double __sum = std::accumulate(_M_prob.begin(),
+					   _M_prob.end(), 0.0);
+      // Now normalize the probabilites.
       std::transform(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
 		     std::bind2nd(std::divides<double>(), __sum));
-      //  Accumulate partial sums.
+      // Accumulate partial sums.
+      _M_cp.reserve(_M_prob.size());
       std::partial_sum(_M_prob.begin(), _M_prob.end(),
 		       std::back_inserter(_M_cp));
-      //  Make sure the last cumulative probablility is one.
+      // Make sure the last cumulative probability is one.
       _M_cp[_M_cp.size() - 1] = 1.0;
     }
 
   template<typename _IntType>
     template<typename _Func>
       discrete_distribution<_IntType>::param_type::
-      param_type(size_t __nw, double __xmin, double __xmax,
-		 _Func __fw)
+      param_type(size_t __nw, double __xmin, double __xmax, _Func __fw)
       : _M_prob(), _M_cp()
       {
-	for (size_t __i = 0; __i < __nw; ++__i)
-	  {
-	    const double __x = ((__nw - __i - 0.5) * __xmin
-				     + (__i + 0.5) * __xmax) / __nw;
-	    _M_prob.push_back(__fw(__x));
-	  }
+	const size_t __n = __nw == 0 ? 1 : __nw;
+	const double __delta = (__xmax - __xmin) / __n;
 
+	_M_prob.reserve(__n);
+	for (size_t __k = 0; __k < __nw; ++__k)
+	  _M_prob.push_back(__fw(__xmin + __k * __delta + 0.5 * __delta));
+
 	_M_initialize();
       }
 
@@ -2026,11 +2027,8 @@
 	const double __p = __aurng();
 	auto __pos = std::lower_bound(__param._M_cp.begin(),
 				      __param._M_cp.end(), __p);
-	if (__pos == __param._M_cp.end())
-	  return 0;
-	const size_t __i = __pos - __param._M_cp.begin();
 
-	return __i;
+	return __pos - __param._M_cp.begin();
       }
 
   template<typename _IntType, typename _CharT, typename _Traits>
@@ -2075,6 +2073,7 @@
       __is >> __n;
 
       std::vector<double> __prob_vec;
+      __prob_vec.reserve(__n);
       for (; __n != 0; --__n)
 	{
 	  double __prob;
@@ -2098,6 +2097,7 @@
       if (_M_int.size() < 2)
 	{
 	  _M_int.clear();
+	  _M_int.reserve(2);
 	  _M_int.push_back(_RealType(0));
 	  _M_int.push_back(_RealType(1));
 
@@ -2107,21 +2107,21 @@
 	  return;
 	}
 
-      double __sum = 0.0;
-      for (size_t __i = 0; __i < _M_den.size(); ++__i)
-	{
-	  __sum += _M_den[__i] * (_M_int[__i + 1] - _M_int[__i]);
-	  _M_cp.push_back(__sum);
-	}
+      const double __sum = std::accumulate(_M_den.begin(),
+					   _M_den.end(), 0.0);
 
-      //  Now normalize the densities...
       std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
 		     std::bind2nd(std::divides<double>(), __sum));
-      //  ... and partial sums.
-      std::transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(),
-		     std::bind2nd(std::divides<double>(), __sum));
-      //  Make sure the last cumulative probablility is one.
+
+      _M_cp.reserve(_M_den.size());
+      std::partial_sum(_M_den.begin(), _M_den.end(),
+		       std::back_inserter(_M_cp));
+
+      // Make sure the last cumulative probability is one.
       _M_cp[_M_cp.size() - 1] = 1.0;
+
+      for (size_t __k = 0; __k < _M_den.size(); ++__k)
+	_M_den[__k] /= _M_int[__k + 1] - _M_int[__k];
     }
 
   template<typename _RealType>
@@ -2132,17 +2132,19 @@
 		 _InputIteratorW __wbegin)
       : _M_int(), _M_den(), _M_cp()
       {
-	do
+	if (__bbegin != __bend)
 	  {
-	    _M_int.push_back(*__bbegin);
-	    ++__bbegin;
-	    if (__bbegin != __bend)
+	    for (;;)
 	      {
+		_M_int.push_back(*__bbegin);
+		++__bbegin;
+		if (__bbegin == __bend)
+		  break;
+
 		_M_den.push_back(*__wbegin);
 		++__wbegin;
 	      }
 	  }
-	while (__bbegin != __bend);
 
 	_M_initialize();
       }
@@ -2150,17 +2152,16 @@
   template<typename _RealType>
     template<typename _Func>
       piecewise_constant_distribution<_RealType>::param_type::
-      param_type(initializer_list<_RealType> __bil, _Func __fw)
+      param_type(initializer_list<_RealType> __bl, _Func __fw)
       : _M_int(), _M_den(), _M_cp()
       {
-	for (auto __biter = __bil.begin(); __biter != __bil.end(); ++__biter)
+	_M_int.reserve(__bl.size());
+	for (auto __biter = __bl.begin(); __biter != __bl.end(); ++__biter)
 	  _M_int.push_back(*__biter);
 
-	for (size_t __i = 0; __i < _M_int.size() - 1; ++__i)
-	  {
-	    _RealType __x = 0.5 * (_M_int[__i] + _M_int[__i + 1]);
-	    _M_den.push_back(__fw(__x));
-	  }
+	_M_den.reserve(_M_int.size() - 1);
+	for (size_t __k = 0; __k < _M_int.size() - 1; ++__k)
+	  _M_den.push_back(__fw(0.5 * (_M_int[__k + 1] + _M_int[__k])));
 
 	_M_initialize();
       }
@@ -2171,19 +2172,17 @@
       param_type(size_t __nw, _RealType __xmin, _RealType __xmax, _Func __fw)
       : _M_int(), _M_den(), _M_cp()
       {
-	for (size_t __i = 0; __i <= __nw; ++__i)
-	  {
-	    const _RealType __x = ((__nw - __i) * __xmin
-					  + __i * __xmax) / __nw;
-	    _M_int.push_back(__x);
-	  }
-	for (size_t __i = 0; __i < __nw; ++__i)
-	  {
-	    const _RealType __x = ((__nw - __i - 0.5) * __xmin
-					+ (__i + 0.5) * __xmax) / __nw;
-	    _M_den.push_back(__fw(__x));
-	  }
+	const size_t __n = __nw == 0 ? 1 : __nw;
+	const _RealType __delta = (__xmax - __xmin) / __n;
 
+	_M_int.reserve(__n + 1);
+	for (size_t __k = 0; __k <= __nw; ++__k)
+	  _M_int.push_back(__xmin + __k * __delta);
+
+	_M_den.reserve(__n);
+	for (size_t __k = 0; __k < __nw; ++__k)
+	  _M_den.push_back(__fw(_M_int[__k] + 0.5 * __delta));
+
 	_M_initialize();
       }
 
@@ -2202,8 +2201,9 @@
 				      __param._M_cp.end(), __p);
 	const size_t __i = __pos - __param._M_cp.begin();
 
-	return __param._M_int[__i]
-	     + (__p - __param._M_cp[__i]) / __param._M_den[__i];
+	const double __pref = __i > 0 ? __param._M_cp[__i - 1] : 0.0;
+
+	return __param._M_int[__i] + (__p - __pref) / __param._M_den[__i];
       }
 
   template<typename _RealType, typename _CharT, typename _Traits>
@@ -2253,6 +2253,7 @@
       __is >> __n;
 
       std::vector<_RealType> __int_vec;
+      __int_vec.reserve(__n + 1);
       for (size_t __i = 0; __i <= __n; ++__i)
 	{
 	  _RealType __int;
@@ -2261,6 +2262,7 @@
 	}
 
       std::vector<double> __den_vec;
+      __den_vec.reserve(__n);
       for (size_t __i = 0; __i < __n; ++__i)
 	{
 	  double __den;
@@ -2284,10 +2286,12 @@
       if (_M_int.size() < 2)
 	{
 	  _M_int.clear();
+	  _M_int.reserve(2);
 	  _M_int.push_back(_RealType(0));
 	  _M_int.push_back(_RealType(1));
 
 	  _M_den.clear();
+	  _M_den.reserve(2);
 	  _M_den.push_back(1.0);
 	  _M_den.push_back(1.0);
 
@@ -2295,17 +2299,19 @@
 	}
 
       double __sum = 0.0;
-      for (size_t __i = 0; __i < _M_int.size() - 1; ++__i)
+      _M_cp.reserve(_M_int.size() - 1);
+      _M_m.reserve(_M_int.size() - 1);
+      for (size_t __k = 0; __k < _M_int.size() - 1; ++__k)
 	{
-	  const _RealType __delta = _M_int[__i + 1] - _M_int[__i];
-	  __sum += 0.5 * (_M_den[__i + 1] + _M_den[__i]) * __delta;
+	  const _RealType __delta = _M_int[__k + 1] - _M_int[__k];
+	  __sum += 0.5 * (_M_den[__k + 1] + _M_den[__k]) * __delta;
 	  _M_cp.push_back(__sum);
-	  _M_m.push_back((_M_den[__i + 1] - _M_den[__i]) / __delta);
+	  _M_m.push_back((_M_den[__k + 1] - _M_den[__k]) / __delta);
 	}
 
       //  Now normalize the densities...
       std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
-		     std::bind2nd(std::divides<double>(),__sum));
+		     std::bind2nd(std::divides<double>(), __sum));
       //  ... and partial sums... 
       std::transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(),
 		     std::bind2nd(std::divides<double>(), __sum));
@@ -2314,15 +2320,9 @@
 		     std::bind2nd(std::divides<double>(), __sum));
       //  Make sure the last cumulative probablility is one.
       _M_cp[_M_cp.size() - 1] = 1.0;
-    }
+     }
 
   template<typename _RealType>
-    piecewise_linear_distribution<_RealType>::param_type::
-    param_type()
-    : _M_int(), _M_den(), _M_cp(), _M_m()
-    { _M_initialize(); }
-
-  template<typename _RealType>
     template<typename _InputIteratorB, typename _InputIteratorW>
       piecewise_linear_distribution<_RealType>::param_type::
       param_type(_InputIteratorB __bbegin,
@@ -2342,10 +2342,12 @@
   template<typename _RealType>
     template<typename _Func>
       piecewise_linear_distribution<_RealType>::param_type::
-      param_type(initializer_list<_RealType> __bil, _Func __fw)
+      param_type(initializer_list<_RealType> __bl, _Func __fw)
       : _M_int(), _M_den(), _M_cp(), _M_m()
       {
-	for (auto __biter = __bil.begin(); __biter != __bil.end(); ++__biter)
+	_M_int.reserve(__bl.size());
+	_M_den.reserve(__bl.size());
+	for (auto __biter = __bl.begin(); __biter != __bl.end(); ++__biter)
 	  {
 	    _M_int.push_back(*__biter);
 	    _M_den.push_back(__fw(*__biter));
@@ -2357,16 +2359,18 @@
   template<typename _RealType>
     template<typename _Func>
       piecewise_linear_distribution<_RealType>::param_type::
-      param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
-		 _Func __fw)
+      param_type(size_t __nw, _RealType __xmin, _RealType __xmax, _Func __fw)
       : _M_int(), _M_den(), _M_cp(), _M_m()
       {
-	for (size_t __i = 0; __i <= __nw; ++__i)
+	const size_t __n = __nw == 0 ? 1 : __nw;
+	const _RealType __delta = (__xmax - __xmin) / __n;
+
+	_M_int.reserve(__n + 1);
+	_M_den.reserve(__n + 1);
+	for (size_t __k = 0; __k <= __nw; ++__k)
 	  {
-	    const _RealType __x = ((__nw - __i) * __xmin
-					  + __i * __xmax) / __nw;
-	    _M_int.push_back(__x);
-	    _M_den.push_back(__fw(__x));
+	    _M_int.push_back(__xmin + __k * __delta);
+	    _M_den.push_back(__fw(_M_int[__k] + __delta));
 	  }
 
 	_M_initialize();
@@ -2379,7 +2383,6 @@
       operator()(_UniformRandomNumberGenerator& __urng,
 		 const param_type& __param)
       {
-	result_type __x;
 	__detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
 	  __aurng(__urng);
 
@@ -2387,23 +2390,23 @@
 	auto __pos = std::lower_bound(__param._M_cp.begin(),
 				      __param._M_cp.end(), __p);
 	const size_t __i = __pos - __param._M_cp.begin();
+
+	const double __pref = __i > 0 ? __param._M_cp[__i - 1] : 0.0;
+
 	const double __a = 0.5 * __param._M_m[__i];
 	const double __b = __param._M_den[__i];
-	const double __c = __param._M_cp[__i];
-	const double __q = -0.5 * (__b
-#if _GLIBCXX_USE_C99_MATH_TR1
-			 + std::copysign(std::sqrt(__b * __b
-						 - 4.0 * __a * __c), __b));
-#else
-			 + (__b < 0.0 ? -1.0 : 1.0)
-			 * std::sqrt(__b * __b - 4.0 * __a * __c));
-#endif
-	const double __x0 = __param._M_int[__i];
-	const double __x1 = __q / __a;
-	const double __x2 = __c / __q;
-	__x = std::max(__x0 + __x1, __x0 + __x2);
+	const double __cm = __p - __pref;
 
-	return __x;
+	_RealType __x = __param._M_int[__i];
+	if (__a == 0)
+	  __x += __cm / __b;
+	else
+	  {
+	    const double __d = __b * __b + 4.0 * __a * __cm;
+	    __x += 0.5 * (std::sqrt(__d) - __b) / __a;
+          }
+
+        return __x;
       }
 
   template<typename _RealType, typename _CharT, typename _Traits>
@@ -2453,6 +2456,7 @@
       __is >> __n;
 
       std::vector<_RealType> __int_vec;
+      __int_vec.reserve(__n + 1);
       for (size_t __i = 0; __i <= __n; ++__i)
 	{
 	  _RealType __int;
@@ -2461,6 +2465,7 @@
 	}
 
       std::vector<double> __den_vec;
+      __den_vec.reserve(__n + 1);
       for (size_t __i = 0; __i <= __n; ++__i)
 	{
 	  double __den;
Index: include/bits/random.h
===================================================================
--- include/bits/random.h	(revision 148467)
+++ include/bits/random.h	(working copy)
@@ -4108,8 +4108,8 @@
 	: _M_param(__wbegin, __wend)
 	{ }
 
-      discrete_distribution(initializer_list<double> __wil)
-      : _M_param(__wil)
+      discrete_distribution(initializer_list<double> __wl)
+      : _M_param(__wl)
       { }
 
       template<typename _Func>
@@ -4240,7 +4240,7 @@
 		     _InputIteratorW __wbegin);
 
 	template<typename _Func>
-	  param_type(initializer_list<_RealType> __bil, _Func __fw);
+	  param_type(initializer_list<_RealType> __bi, _Func __fw);
 
 	template<typename _Func>
 	  param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
@@ -4276,9 +4276,9 @@
 	{ }
 
       template<typename _Func>
-	piecewise_constant_distribution(initializer_list<_RealType> __bil,
+	piecewise_constant_distribution(initializer_list<_RealType> __bl,
 					_Func __fw)
-	: _M_param(__bil, __fw)
+	: _M_param(__bl, __fw)
 	{ }
 
       template<typename _Func>
@@ -4408,7 +4408,9 @@
 	typedef piecewise_linear_distribution<_RealType> distribution_type;
 	friend class piecewise_linear_distribution<_RealType>;
 
-	param_type();
+	param_type()
+	: _M_int(), _M_den(), _M_cp(), _M_m()
+	{ _M_initialize(); }
 
 	template<typename _InputIteratorB, typename _InputIteratorW>
 	  param_type(_InputIteratorB __bfirst,
@@ -4416,7 +4418,7 @@
 		     _InputIteratorW __wbegin);
 
 	template<typename _Func>
-	  param_type(initializer_list<_RealType> __bil, _Func __fw);
+	  param_type(initializer_list<_RealType> __bl, _Func __fw);
 
 	template<typename _Func>
 	  param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
@@ -4453,9 +4455,9 @@
 	{ }
 
       template<typename _Func>
-	piecewise_linear_distribution(initializer_list<_RealType> __bil,
+	piecewise_linear_distribution(initializer_list<_RealType> __bl,
 				      _Func __fw)
-	: _M_param(__bil, __fw)
+	: _M_param(__bl, __fw)
 	{ }
 
       template<typename _Func>

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]