为什么C++11的随机分布是可变的？

Question

我本以为由c++11随机分布(uniform_int_distribution等)生成的数值只取决于传递给operator()的生成器的状态。然而，由于某种原因，在operator()的签名中没有const说明符。这是什么意思，我该如何将分布作为函数参数传递？我原本认为必须将它作为任何不可变参数通过const引用传递，但现在我不确定了。

- karlicoss

---

我理解这个在C++标准中已经定义了，但我不理解其中的原因。例如，均匀整型分布可以通过其左右边界完全参数化，正态分布可以通过平均值和标准差来参数化，离散分布可以通过各个概率来参数化等。所以这些都可以在构造时完成，似乎没有理由允许更改分布实例（特别是operator()）。 - karlicoss

（概念上）分布是有状态的函数（实际上某些分布可能以无状态方式实现）。 - R. Martinho Fernandes

我认为，分布是一个数学概念，下一个生成的值不依赖于前一个时刻生成的值。如果有人必须保留一些隐藏状态以避免某些计算或出于其他原因，他应该对字段使用可变修饰符，但从逻辑上讲，分布必须是不可变的。 - karlicoss

@Yuushi 不，状态已经改变了，它是我们传递给operator()的生成器的隐藏状态。 - karlicoss

@karlicoss 我原以为你在使用 C++，而不是在做数学。在 C++ 中，分布式函数具有状态。 - R. Martinho Fernandes

Answer 1

一开始我误解了问题，但是现在我理解了，这是一个好问题。对于g++的<random>实现源码进行了一些研究，以下是部分内容（为了清晰起见略去了一些细节）：

template<typename _IntType = int>
  class uniform_int_distribution
  {

  struct param_type
  {
    typedef uniform_int_distribution<_IntType> distribution_type;

    explicit
    param_type(_IntType __a = 0,
       _IntType __b = std::numeric_limits<_IntType>::max())
    : _M_a(__a), _M_b(__b)
    {
      _GLIBCXX_DEBUG_ASSERT(_M_a <= _M_b);
    }

     private:
    _IntType _M_a;
    _IntType _M_b;
};

public:
  /**
   * @brief Constructs a uniform distribution object.
   */
  explicit
  uniform_int_distribution(_IntType __a = 0,
           _IntType __b = std::numeric_limits<_IntType>::max())
  : _M_param(__a, __b)
  { }

  explicit
  uniform_int_distribution(const param_type& __p)
  : _M_param(__p)
  { }

  template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
    { return this->operator()(__urng, this->param()); }

  template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng,
       const param_type& __p);

  param_type _M_param;
};

如果我们忽略掉所有的_，我们可以看到它只有一个成员参数，param_type _M_param，它本身只是一个包含2个整数值的嵌套结构体——实际上是一个范围。这里仅声明了operator()，并未定义。进一步挖掘可找到其定义。为避免在此发布所有相当丑陋（而且相当冗长）的代码，简单地说，在此函数内没有任何变异。事实上，添加const到定义和声明中将会编译通过。

那么问题变成了，这对于其他分布也是真的吗？答案是否定的。如果我们查看std::normal_distribution的实现，我们会发现：

template<typename _RealType>
template<typename _UniformRandomNumberGenerator>
  typename normal_distribution<_RealType>::result_type
  normal_distribution<_RealType>::
  operator()(_UniformRandomNumberGenerator& __urng,
     const param_type& __param)
  {
result_type __ret;
__detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
  __aurng(__urng);

    //Mutation!
if (_M_saved_available)
  {
    _M_saved_available = false;
    __ret = _M_saved;
  }
    //Mutation!

这只是一种理论推测，但我想之所以没有限制于const，是为了让实现者在需要时可以更改自己的实现。此外，它保持了更统一的接口 - 如果有些operator()是const而有些不是，那就会变得有点混乱。

然而，他们为什么不简单地将它们设为const，让实现者使用mutable我不确定。很可能，除非这里有人参与了标准化工作的这部分内容，否则你可能无法得到一个好的答案。

编辑: 正如MattieuM指出的，mutable和多线程不兼容。

只是一个小有趣的细节，std::normal_distribution 一次生成两个值，缓存其中一个（因此有_M_saved）。它定义的 operator<< 实际上允许您在下一次调用operator()之前查看该值：

#include <random>
#include <iostream>
#include <chrono>

std::default_random_engine eng(std::chrono::system_clock::now().time_since_epoch().count());
std::normal_distribution<> d(0, 1);

int main()
{
   auto k = d(eng);
   std::cout << k << "\n";
   std::cout << d << "\n";
   std::cout << d(eng) << "\n";
}

这里的输出格式为mu sigma nextval。

- Yuushi

---

对于 std::uniform_int_distribution 这样的东西，你 可以 每次创建一个新分布，实现也没有问题。从分布中抽取数字在理论上不应以任何方式修改分布本身。如果我从均值为0，标准差为1的正态分布中抽出一个数字，那么该分布仍将保持均值为0，标准差为1的正态分布。 - Yuushi

尽管在名称上相同，但 C++ 中的分布与数学中的分布并不是同一实体。这是您必须接受的事实。事实上，一些 C++ 分布具有可变状态，且该状态是可观察的（尽管由于涉及随机性和概率，观察它可能并不容易）：编写假定不存在可观察状态的代码会导致分布不良的输出结果。而 mutable 不应用于隐藏可观察状态。 - R. Martinho Fernandes

@Yuushi：C++11标准不允许使用Copy-on-Write技术，是因为它保证了在多个线程中安全地调用对象的const操作。这也是为什么C++11标准拒绝隐藏可变性的原因。 - Matthieu M.

@karlicoss：我不确定整个库中的每一个访问都是如此，但我知道这是一个设计目标，并且已经在所有STL容器和basic_string类中得到了执行。 - Matthieu M.

尽管在名称上相同，但C++中的分布与数学中的分布并不是相同的实体。这是你必须接受的事实。原帖提问为什么会这样，所以这个回答并没有真正回答问题（而且这个回答似乎认为这是一种实现细节，这有点脆弱）。 - Calimo

Answer 2

另一个答案说：

这只是理论上的推测，但我想它不限于const的原因是为了允许实现者在需要时改变其实现。此外，它保持了更统一的接口——如果某些operator()是const，而其他的不是，那么这会变得有点混乱。

这基本上是正确的，但在泛型编程的背景下，它甚至更深层次。 （正如@Calimo所说，这表明省略了const只是“以防万一”。）

经过思考，我得出结论，以下成员函数是否可以在原则上是const或者实际上并不取决于_UniformRandomNumberGenerator的实际类型。

template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)

在这个（通用）规范级别上，这是不可知的，因此只有在这时，“[规范]允许实现者改变[内部状态]”，并且出于通用性的考虑才这样做。

所以，constness的问题在于在编译时，应该知道_UniformRandomNumberGenerator是否能够生成足够的随机性（位数），以便分布产生样本抽取。

在当前规范中，这种可能性被排除了，但原则上可以通过拥有两个互斥版本的成员函数来实现（或指定）：

template<typename _URG, typename = std::enable_if<not has_enough_randomness_for<_URG, result_type>::value > >
result_type
operator()(_UniformRandomNumberGenerator& __urng){..statefull impl..}

template<typename _URG, typename = std::enable_if<has_enough_randomness_for<_URG, result_type>::value > >
result_type
operator()(_UniformRandomNumberGenerator& __urng) const{..stateless impl...}

在这里，has_enough_randomness_for是一个想象中的布尔元函数，可以判断特定实现是否可以无状态。

然而，还有另一个障碍，一般来说，实现是否有状态取决于分布的运行时参数。 但由于这是运行时信息，因此无法作为类型系统的一部分传递！

正如您所看到的，这又引发了另一个问题。虽然理论上分布的constexpr参数可以检测到这一点，但我完全理解委员会停在这里。

如果您需要一个不可变的分布（例如为了“概念上”的正确），则可以通过付出代价轻松实现：

1. 每次使用之前复制原始分布。
2. 以无状态方式自己实现分布逻辑。

(1) 可能非常低效，而 (2) 很可能效率稍低且极其难以正确实现。

由于 (2) 在一般情况下几乎不可能做到正确，即使做到了，它也会有些低效，因此我只会展示如何实现一个能够正常工作的无状态分布：

template<class Distribution>
struct immutable : Distribution{
   using Distribution::Distribution;
   using Distribution::result_type;
   template<typename _URG> result_type operator()(_URG& __urng) const{
      auto dist_copy = static_cast<Distribution>(*this);
      return dist_copy(__urng);
   }
// template<typename _URG> result_type operator()(_URG& __urng) = delete;
};

以这种方式，immutable<D>是D的替代品。（immutable<D>的另一个名称可以是conceptual<D>。）

例如，我已经使用uniform_real_distribution进行了测试，发现immutable替代品几乎慢了一倍（因为它复制/修改/丢弃名义状态），但正如您所指出的那样，如果在设计中重视更“概念性”的上下文，则可以使用它（我可以理解）。

（还有另一个不相关的小优点，即您可以跨线程使用共享的不可变分布）。

---

以下是错误但具有说明性的代码：

为了说明（2）有多么困难，我将创建一个天真的特化版本immutable<std::uniform_int_distribution>，对于某些用途几乎正确（或者根据不同的人会非常不正确）。

template<class Int>
struct immutable<std::uniform_int_distribution<Int>> : std::uniform_int_distribution<Int>{
   using std::uniform_int_distribution<Int>::uniform_int_distribution;
   using std::uniform_int_distribution<Int>::result_type;
   template<typename _URG> result_type operator()(_URG& __urng) const{
      return __urng()%(this->b() - this->a()) + this->a(); // never do this ;) for serious stuff, it is wrong in general for very subtle reasons
   }
// template<typename _URG> result_type operator()(_URG& __urng) = delete;
};

这种无状态的实现非常“高效”，但对于任意值的a和b（分布的限制）并不完全正确。 正如你所看到的，对于其他分布（包括连续分布），这条路线非常困难、棘手且容易出错，因此我不建议使用它。

---

这主要是个人观点：情况能得到改善吗？ 可以，但只是稍微改进一下。

分布可以有两个版本的operator()，一个是非const（即&），它是最优的（当前版本），另一个则是const的，尽可能不修改状态。然而，它们是否需要确定性一致（即给出相同的答案）还不清楚。（即使回退到复制，也无法像完整的可变分布那样给出相同的结果。）然而，我认为这不是一条可行的道路（与其他答案一致）；你要么使用一个不可变版本，要么使用一个不可变版本，但不能同时使用两个。

我认为可以做的是，有一个可变版本，但对于右值引用有一个特定的重载（operator() &&）。这样就可以使用可变版本的机制，但现在“无用”的更新步骤（例如重置）可以省略，因为该特定实例将永远不会再次使用。这样，在某些情况下可以节省一些操作。

这样，上述描述的immutable适配器就可以这样编写并利用语义：

template<class Distribution>
struct immutable : Distribution{
   using Distribution::Distribution;
   using Distribution::result_type;
   template<typename _URG> result_type operator()(_URG& __urng) const{
      auto dist_copy = static_cast<Distribution>(*this);
      return std::move(dist_copy)(__urng);
// or return (Distribution(*this))(__urng);
   }
};

- alfC