Subject: Re: [boost] [config] std::shuffle support
From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2016-11-07 11:36:31
On 11/07/16 17:54, Edward Diener wrote:
> On 11/7/2016 7:28 AM, Peter Dimov wrote:
>> Andrey Semashev wrote:
>>> FWIW, in Boost.Log I'm using my local random_shuffle regardless of
>>> the standard library version. Maybe that would be a better solution
>>> than conditioning your code on config macros.
>>> : https://github.com/boostorg/log/blob/develop/src/core.cpp#L60
>> The standard random_shuffle doesn't use rng() % n though, it uses
>> rng(n). rng() % n is non-uniform in general.
> So substituting:
> Iterator where = begin + rng(it - begin + 1u);
> in Andrey's code would be fine according to the current random_shuffle
> implementations ?
In that particular code, rng does not implement operator() with an
argument (it's an instance of random::taus88).
Yes, the code could be changed to use the canon operator() and use
random::uniform_int_distribution internally to guarantee uniform
distribution. I just chose not to waste CPU cycles because that level of
correctness is not needed in that particular code.
I'll add that at least libstdc++ uses modulus division, like in
Boost.Log, in std::random_shuffle that doesn't take random number
generator as an argument. Any place that uses that overload of
std::random_shuffle is already susceptible to the uniformity error.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk