Pourquoi les distributions aléatoires de c++11 sont-elles mutables ?

Question

Je pensais que la valeur générée par la distribution aléatoire de c++11 ( uniform_int_distribution par exemple), ne dépend que de l'état du générateur qui est transmis à la fonction operator() . Cependant, pour une raison quelconque, il n'y a pas de const dans la signature de operator() . Qu'est-ce que cela signifie et comment dois-je passer la distribution comme paramètre de la fonction ? Je pensais que je devais la passer comme tout paramètre non modifiable : par référence constante, mais maintenant je n'en suis plus sûr.

Answer 1

J'ai d'abord mal compris la question, mais maintenant que j'ai compris, c'est une bonne question. En creusant un peu dans la source de l'implémentation de <random> pour g++ donne ce qui suit (avec quelques parties laissées de côté pour plus de clarté) :

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;
};

Si l'on fait abstraction de tous les _ nous pouvons voir qu'il n'a qu'un seul paramètre membre, param_type _M_param qui elle-même est simplement une structure imbriquée contenant 2 valeurs intégrales - en fait, une plage. operator() n'est que déclarée ici, elle n'est pas définie. En creusant un peu plus, nous arrivons à la définition. Au lieu d'afficher tout le code ici, qui est plutôt laid (et plutôt long), il suffit de dire que rien n'est muté à l'intérieur de cette fonction. En fait, en ajoutant const à la définition et à la déclaration se compilera sans problème.

La question qui se pose alors est de savoir si c'est le cas pour toutes les autres distributions. La réponse est non. Si nous regardons l'implémentation de std::normal_distribution , nous trouvons :

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!

Ce n'est qu'une théorie, mais j'imagine que la raison pour laquelle il n'est pas limité à l'Europe est qu'il n'y a pas d'autre solution que de l'argent. const est de permettre aux personnes chargées de la mise en œuvre de modifier cette dernière si nécessaire. De plus, cela permet de conserver une interface plus uniforme - si un operator() son const et d'autres ne le sont pas const Le résultat est un peu désordonné.

Cependant, pourquoi ne pas les avoir simplement rendus const et avoir laissé les personnes chargées de leur mise en œuvre les utiliser ? mutable Je n'en suis pas certain. Il est probable qu'à moins que quelqu'un ici n'ait été impliqué dans cette partie de l'effort de normalisation, vous n'obtiendrez pas une bonne réponse à cette question.

Edit : Comme l'a souligné MattieuM, mutable et les fils multiples ne font pas bon ménage.

Juste une petite parenthèse intéressante, std::normal_distribution génère deux valeurs à la fois et en met une en cache (d'où l'expression _M_saved ). Les operator<< qu'il définit vous permet en fait de voir cette valeur avant le prochain appel à 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";
}

Ici, le format de sortie est mu sigma nextval .

Answer 2

L'autre réponse est la suivante :

Ce n'est qu'une théorie, mais j'imagine que la raison pour laquelle il n'est pas limité à const est de permettre aux implémenteurs de muter leur implémentation si nécessaire. De plus, cela permet de conserver une interface plus uniforme - si certains operator() sont const et d'autres non-const, cela devient un peu fouillis.

C'est en grande partie correct, mais c'est encore plus profond que cela dans le contexte de la programmation générique. (Comme l'a dit @Calimo, cela laisse l'idée que const a été omise "au cas où").

Après avoir réfléchi, je suis arrivé à la conclusion que le problème se traduit par la question de savoir si la fonction membre suivante peut être en principe const dépend en fait du type de _UniformRandomNumberGenerator .

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

À ce niveau de spécification (générique), cela n'est pas connu, et c'est donc seulement à ce moment-là que "[la spécification] permet aux implémenteurs de muter [l'état interne]" et elle le fait pour des raisons de généricité.

Le problème de la constance est donc que au moment de la compilation il faut savoir si _UniformRandomNumberGenerator est capable de générer suffisamment d'aléas (bits) pour que la distribution produise un échantillon.

Dans la spécification actuelle, cette possibilité est laissée de côté, mais elle peut en principe être mise en œuvre (ou spécifiée) en ayant deux versions exclusives de la fonction membre :

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...}

Dónde has_enough_randomness_for est une métafonction booléenne imaginée qui permet de savoir si l'implémentation particulière peut être sans état.

Cependant, il existe encore un autre obstacle : en général, la question de savoir si la mise en œuvre est sans état ou non dépend de l'état de l'application. paramètres d'exécution de la distribution. Mais comme il s'agit d'une information d'exécution, elle ne peut pas être transmise en tant que partie du système de types !

Comme vous le voyez, cela ouvre une autre boîte de Pandore. constexpr Les paramètres des distributions pourraient en principe détecter cela, mais je comprendrais tout à fait que la commission s'arrête là.

Si vous avez besoin d'une distribution immuable (par exemple pour être "conceptuellement" correcte), vous pouvez facilement l'obtenir en payant un prix :

1. Copier une distribution vierge à chaque fois avant de l'utiliser.
2. Mettre en œuvre soi-même la logique de distribution d'une manière sans état.

(1) peut être très inefficace et (2) il est probable qu'il soit quelque peu inefficace et (3) il est probable qu'il soit quelque peu inefficace. extrêmement difficile à mettre en œuvre correctement.

Étant donné que (2) est presque impossible à réaliser en général et que même si l'on y parvient, ce sera quelque peu inefficace, je vais seulement montrer comment mettre en œuvre une distribution sans état qui fonctionne :

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;
};

De manière à ce que immutable<D> remplace D . (Autre nom pour immutable<D> pourrait être conceptual<D> .)

J'ai testé ceci avec uniform_real_distribution par exemple, et le immutable le remplacement est presque deux fois plus lent (parce qu'il copie/modifie/abandonne un état nominal), mais comme vous le soulignez, il peut être utilisé dans un contexte plus "conceptuel" si c'est important pour votre conception (ce que je peux comprendre).

(Il y a un autre avantage mineur non lié qui est que vous pouvez utiliser une distribution immuable partagée entre les threads).

---

LE CODE SUIVANT EST INCORRECT MAIS ILLUSTRATIF :

Pour illustrer la difficulté de l'exercice (2), je vais faire un naïf spécialisation de immutable<std::uniform_int_distribution> qui est presque correcte pour certaines utilisations (ou très incorrecte selon la personne à qui l'on s'adresse).

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;
};

Cette implémentation sans état est très "efficace" mais n'est pas 100% correcte pour des valeurs arbitraires de a et b (limites de la distribution). Comme vous pouvez le constater, pour d'autres distributions (y compris les distributions continues), cette voie est très difficile, délicate et sujette à erreur, et je ne la recommande donc pas.

---

Il s'agit principalement d'une opinion personnelle : Les situations peuvent-elles être améliorées ?

Oui, mais seulement un peu.

Les distributions pourraient avoir deux versions de operator() , un no- const (c'est-à-dire & ), qui est optimale (actuelle) et une qui est const qu'il fait ce qu'il peut pour ne pas modifier l'état. Toutefois, il n'est pas certain qu'ils soient cohérents d'un point de vue déterministe (c'est-à-dire qu'ils donnent les mêmes réponses). (Même le recours à la copie ne donnera pas les mêmes résultats qu'une distribution mutable à part entière). Cependant, je ne pense pas que ce soit une voie viable (je suis d'accord avec l'autre réponse) ; soit vous utilisez une version immuable, soit une version immuable, mais pas les deux en même temps.

Ce que je pense pouvoir faire, c'est d'avoir une version mutable mais une surcharge spécifique pour les références aux valeurs r ( operator() && ). De cette manière, le mécanisme de la version mutable peut être utilisé, mais l'étape désormais "inutile" de la mise à jour (par exemple, la réinitialisation) de l'état peut être omise parce que l'instance particulière ne sera plus jamais utilisée. On peut ainsi économiser certaines opérations dans certains cas.

De cette manière, le immutable décrit ci-dessus peut être écrit de cette manière et exploiter la sémantique :

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);
   }
};