Simplifying simple uses of <random>

187 views
Skip to first unread message

T. C.

unread,
May 23, 2016, 4:42:29 PM5/23/16
to ISO C++ Standard - Future Proposals
Hi,

I've written a paper based on Melissa O'Neill's randutils.hpp (described here), proposing a simple wrapper class template for URNGs with various convenience member functions and automatic nondeterministic seeding (for random number engines):

https://github.com/timsong-cpp/stuff/blob/master/random_generator.md

Comments would be greatly appreciated.

Thanks,
Tim

Richard Smith

unread,
May 23, 2016, 5:29:03 PM5/23/16
to std-pr...@isocpp.org
The new random algorithms here (choose, pick, ...) should be made available as non-member functions that operate on URNGs, like sample and shuffle already are -- it doesn't seem reasonable for these to exist in the convenience wrapper but for the general case.

With that change made, the value of a separate class here is diminished. Instead of

  std::random_generator<std::mt19937> rng; // nondeterministically seeded
  std::cout << rng.choose(some_list);

... how would you feel about

  auto urng = std::seeded<std::mt19937>(); // returns a nondeterministically seeded std::mt19937
  std::cout << choose(some_list, urng);

or similar?

Arthur O'Dwyer

unread,
May 23, 2016, 7:45:31 PM5/23/16
to ISO C++ Standard - Future Proposals
On Monday, May 23, 2016 at 2:29:03 PM UTC-7, Richard Smith wrote:
On Mon, May 23, 2016 at 1:42 PM, T. C. <rs2...@gmail.com> wrote:

I've written a paper based on Melissa O'Neill's randutils.hpp (described here), proposing a simple wrapper class template for URNGs with various convenience member functions and automatic nondeterministic seeding (for random number engines):

https://github.com/timsong-cpp/stuff/blob/master/random_generator.md

Comments would be greatly appreciated.

The new random algorithms here (choose, pick, ...) should be made available as non-member functions that operate on URNGs, like sample and shuffle already are -- it doesn't seem reasonable for these to exist in the convenience wrapper but [not] for the general case.

With that change made, the value of a separate class here is diminished. Instead of

  std::random_generator<std::mt19937> rng; // nondeterministically seeded
  std::cout << rng.choose(some_list);

... how would you feel about

  auto urng = std::seeded<std::mt19937>(); // returns a nondeterministically seeded std::mt19937
  std::cout << choose(some_list, urng);

I was shocked to read in Tim's paper that C++1z currently requires some variation on

// assuming that unsigned int is 32 bits
std
::random_device rd;
std
::seed_seq sseq {rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd()};
std
::mt19937 rng(sseq); // seeded with 256 bits of entropy from random_device

I would have expected the following HYPOTHETICAL code to Do The Right Thing:

std::random_device rd;
std
::mt19937 rng(rd);  // seeded with however much entropy it needs from the provided random_device

(Notice that this is the "naïve" code but with one pair of parentheses removed.)
Does C++ really not allow that right now?  (Checked with Wandbox: it does not.)
If C++ were amended to allow it, would a good chunk of the problem go away?  Is there a good reason not to allow it?

I agree with Richard Smith's statement that the new algorithmic mechanisms (pick, choose, uniform, shuffle, sample) should be proposed as plain old library algorithms, not coupled tightly with the new seeding mechanism.

my $.02,
Arthur

M.E. O'Neill

unread,
May 23, 2016, 7:48:09 PM5/23/16
to ISO C++ Standard - Future Proposals
Richard Smith wrote:
> The new random algorithms here (choose, pick, ...) should be made available as non-member functions that operate on URNGs, like sample and shuffle already are -- it doesn't seem reasonable for these to exist in the convenience wrapper but for the general case.

FWIW, sample doesn't exist in the standard yet, it's a proposed addition. When I wrote randutils it didn't exist. So the only stand-alone function in C++14 is shuffle, whose origins date back to random_shuffle (which predates the C++11 <random> library and thus has a different flavor). Thus pick, choose, uniform, variate, and sample all don't exist right now.

To me there is a bit of a fork in the road here, let's look at the two forks:

Option 1: Global functions, exemplified by the proposed sample algorithm, which take (optional) extra arguments to specify the engine. To simply things, there is a global state (actually per-thread) that holds some system-defined random engine (i.e., the randint proposal). But do you want a constellation of thematically-related global helper functions (i.e., seeded, uniform, variate, pick, choose, shuffle, and sample)?

Option 2: Random-generator objects, which tie together the <random> pieces but stay in the domain of object orientation. There is far less reliance on baked-in global state and only one new name in the std namespace.

The rest of the random number generation library is happy to use objects (e.g., the distributions, the engines, etc.), the second option retains the flavor of the existing library while making it easier to use.

> ... how would you feel about
>
> auto urng = std::seeded<std::mt19937>(); // returns a nondeterministically seeded std::mt19937
> std::cout << choose(some_list, urng);

I don't like it. I teach C++ (to smart people who already have some programming experience), and I don't want to to have to explain this. If urng is a std::mt19937, it looks like a band-aid around a design flaw (why doesn't std::mt19937 know how to construct itself well in the first place? why does it need a helper function? why doesn't it look like the rest of the rng library?). And, did a std::mt19937 object get copied here?

If you presuppose that randint is a done deal and so is sample, then perhaps there isn't as much reason for this convenience class, but I don't think they are set in stone yet, and I think it's worthwhile to think through what really fits best with the random generation library we have. In that vein, it's shuffle that's the outlier.

The focus of this proposal is providing a tiny amount of glue to make all the wonderful features of <random> actually easy to use. There is pretty much no reason to provide pick as a helper function, or variate, or even sample, because they aren't really meaty *algorithms* at all, they're virtually one liners (choose is just a call to advance by an appropriate random amount, sample is just stable_partition with an appropriate random-based predicate. etc.). But there are a very good reasons to make these things something a random-generator object can do, because it creates something cohesive.

Thoughts welcome,

M.E.O.

Nicol Bolas

unread,
May 23, 2016, 8:23:40 PM5/23/16
to ISO C++ Standard - Future Proposals

Be advised: there's already a proposal for improving the seeding of RNGs.

As for the idea, if you're interested in a do-everything RNG class, why bother making the random number engine a template parameter? Why expose the underlying engine at all?

That seems like an over-complication of the idea. If the goal is to be as simple as Python, then just make it `random_generator`, and have implementations decide on what the underlying engine is.

If you're serious about your random engine and distributions, about the specific details of seeding and so forth, you're not going to use this class. And if just want some randomness, then you don't care about the details. You just want a quick, simple, braindead class that spits out randomness in various ways upon request.

That being said, I see no reason why such a class needs member functions for things we already have algorithms for (or will have, in the case of range-generate). The sooner a C++ programmer is encouraged to look to algorithms, the better. We may want to be as simple as Python, but we should not pretend that C++ is Python.

Nicol Bolas

unread,
May 23, 2016, 8:32:05 PM5/23/16
to ISO C++ Standard - Future Proposals
Oh and a couple of other things about the proposal:

How do you implement `choose` with ForwardIterators? Does it involve `std::distance` calling, so that it can determine how many items to choose from?

What's the point of `pick`? Is it *really* that important to have a function that does `*choose`?

ForwardIterators can't be subtracted. `sample`'s description seems to rely on that. You probably meant `std::distance`.

Nicol Bolas

unread,
May 23, 2016, 9:02:27 PM5/23/16
to ISO C++ Standard - Future Proposals
On Monday, May 23, 2016 at 7:48:09 PM UTC-4, M.E. O'Neill wrote:
Richard Smith wrote:
> The new random algorithms here (choose, pick, ...) should be made available as non-member functions that operate on URNGs, like sample and shuffle already are -- it doesn't seem reasonable for these to exist in the convenience wrapper but for the general case.

FWIW, sample doesn't exist in the standard yet, it's a proposed addition.  When I wrote randutils it didn't exist.  So the only stand-alone function in C++14 is shuffle, whose origins date back to random_shuffle (which predates the C++11 <random> library and thus has a different flavor).  Thus pick, choose, uniform, variate, and sample all don't exist right now.

To me there is a bit of a fork in the road here, let's look at the two forks:

Option 1: Global functions, exemplified by the proposed sample algorithm, which take (optional) extra arguments to specify the engine.  To simply things, there is a global state (actually per-thread) that holds some system-defined random engine (i.e., the randint proposal).  But do you want a constellation of thematically-related global helper functions (i.e., seeded, uniform, variate, pick, choose, shuffle, and sample)?

Have you not looked at Chapter 25 of the C++ Standard? That's how we do things in C++.

`uniform` is not a function that should be an algorithm. If you have an engine, and you want to get a uniform value in a range, we have a whole class for that. Seeding likewise is being looked into for an overhaul. `variate` is not something we need as an algorithm. And `pick` is rather silly.

But the rest... why not make them algorithms? There's absolutely nothing to be lost by providing these as global functions that any RNG engine can be used with. It would be extremely silly to see people wrap an RNG engine in one of these classes for the sole purpose of making use of these algorithms.

And yet, if you don't offer them the obvious choice of a `std` algorithm, they will do it.

And no, we don't need "global state (actually per-thread) that holds some system-defined random engine (i.e., the randint proposal)". That's a horrible idea. As far as I'm concerned, I have no problem with saying that all C++ random functions must be provided an engine by the user.
 
Option 2: Random-generator objects, which tie together the <random> pieces but stay in the domain of object orientation.  There is far less reliance on baked-in global state and only one new name in the std namespace.

Names in the `std` namespace are not at a premium. They're not going anywhere. And as previously stated, we need no "baked-in global state".

The rest of the random number generation library is happy to use objects (e.g., the distributions, the engines, etc.), the second option retains the flavor of the existing library while making it easier to use.

> ... how would you feel about
>
>   auto urng = std::seeded<std::mt19937>(); // returns a nondeterministically seeded std::mt19937
>   std::cout << choose(some_list, urng);

I don't like it.  I teach C++ (to smart people who already have some programming experience), and I don't want to to have to explain this.  If urng is a std::mt19937, it looks like a band-aid around a design flaw (why doesn't std::mt19937 know how to construct itself well in the first place?

Because "construct itself well" is a matter of opinion, so we require users to be specific about how it gets built.
 
why does it need a helper function?

Your students must hate `make_shared` and `make_unique`...

 why doesn't it look like the rest of the rng library?).  And, did a std::mt19937 object get copied here?

If you haven't told them about how move semantics and copy elision works yet, then that's not a question they ought to be concerned about yet.

If you presuppose that randint is a done deal and so is sample, then perhaps there isn't as much reason for this convenience class, but I don't think they are set in stone yet, and I think it's worthwhile to think through what really fits best with the random generation library we have.  In that vein, it's shuffle that's the outlier.

The focus of this proposal is providing a tiny amount of glue to make all the wonderful features of <random> actually easy to use.   There is pretty much no reason to provide pick as a helper function, or variate, or even sample, because they aren't really meaty *algorithms* at all, they're virtually one liners (choose is just a call to advance by an appropriate random amount, sample is just stable_partition with an appropriate random-based predicate. etc.).

`std::generate` is not exactly "meaty" either; neither are `for_each` and many more. We add these things because they're repeatedly used, convenient, and potentially bug-prone. Not because they're hard to write.

Also, it should be noted that writing an efficient `choose` for non-RandomAccessIterators very much is tricky. You don't want to call `std::distance` on the range, so it'd be best to find a different way. And that can be complicated.

But there are a very good reasons to make these things something a random-generator object can do, because it creates something cohesive.

No, they should not.

I should not have to implement `choose` for every single RNG engine I write. The purpose of an RNG engine is to produce randomness; `choose` is about how you use randomness.

Just like the purpose of a `vector` is to store and manage elements. `sort` is about the order of those elements, without affecting the storage or management of them. One is a class, the other an algorithm.

M.E. O'Neill

unread,
May 23, 2016, 9:24:02 PM5/23/16
to ISO C++ Standard - Future Proposals
Nicol Bolas wrote (across three messages):
> Be advised: there's already a proposal for improving the seeding of RNGs.

That's good to know. (One issue with encouraging std::random_device though is that std::random_device is not currently required to be in any way nondeterministic. It is allowed to produce the same output on every run of the program.)

> As for the idea, if you're interested in a do-everything RNG class, why bother making the random number engine a template parameter? Why expose the underlying engine at all?

Although it's not part of this proposal draft, in my original version I did provide some typedefs for common generators precisely so that people didn't need to specify an engine as a parameter.

> That seems like an over-complication of the idea. If the goal is to be as simple as Python, then just make it `random_generator`, and have implementations decide on what the underlying engine is.
>
> If you're serious about your random engine and distributions, about the specific details of seeding and so forth, you're not going to use this class. And if just want some randomness, then you don't care about the details. You just want a quick, simple, braindead class that spits out randomness in various ways upon request.

The whole point of this proposal is that it enhances rather than subverts the library we have. Consider this code:

mt19937_gen rng;
double x = rng.variate<std::normal_distribution<double>>(17,3);

it's using the beauty of the library we have while being much easer to use.

The key idea is that it's easy enough for a beginner, but still handy for an expert, and provides a good stepping stone to the facilities that still exist. It's not a dumbing down, it's handy glue to avoid annoying and error-prone boilerplate, boilerplate that's confusing to beginners and a hassle for experts.

> That being said, I see no reason why such a class needs member functions for things we already have algorithms for (or will have, in the case of range-generate). The sooner a C++ programmer is encouraged to look to algorithms, the better. We may want to be as simple as Python, but we should not pretend that C++ is Python.

As I said above and in another post, it's best to see this class as very helpful glue to provide something cohesive.

> `uniform` is not a function that should be an algorithm. If you have an engine, and you want to get a uniform value in a range, we have a whole class for that. Seeding likewise is being looked into for an overhaul. `variate` is not something we need as an algorithm.

EXACTLY! You hit the nail on the head. These are *NOT* algorithms. They are far too simple. They are in fact, basically trivial, they just call out to the classes that we already have, that's the point. It's about ease of use.

My claim is that people don't use the distribution classes because producing a number in the range [0,9] by saying:

std::uniform_int_distribution mydist(0,9)
std::cout << mydist(myengine);

feels cumbersome to a lot of people to the point that people would rather write myengine() % 10 instead. That's also one reason why randint got proposed.

> What's the point of `pick`? Is it *really* that important to have a function that does `*choose`?

Pick is passed a container and gives you an element, because it always gives you an element it makes no sense to return an iterator. Choose is passed two iterators and gives you an iterator.

But yes, pick is trivially implemented as *choose, much as a[i] is trivially *(a+i) and front() and back() on containers are trivial (e.g., foo.front() is *(foo.begin())).

> How do you implement `choose` with ForwardIterators? Does it involve `std::distance` calling, so that it can determine how many items to choose from?

Yes. With a ForwardIterator it'll be O(n) but it would be O(n) expected anyway.

> ForwardIterators can't be subtracted. `sample`'s description seems to rely on that. You probably meant `std::distance`.

Yes, my implementation actually uses std::distance; when Tim turned it into a proposal, I think he tried to simplify the description but this wasn't a valid simplification. Good catch, thanks.


If there is one takeaway here, the point of this class was not to do anything fundamentally new (although it did have to work around the current brokenness in seeding), but to make the facilities we already have easy to use right for beginners and experts alike. The fact that the randint proposal exists is proof enough that as things stand right now is *NOT* good enough in that regard.

Best regards,

M.E.O.


T. C.

unread,
May 23, 2016, 9:45:40 PM5/23/16
to ISO C++ Standard - Future Proposals


On Monday, May 23, 2016 at 9:24:02 PM UTC-4, M.E. O'Neill wrote:

> ForwardIterators can't be subtracted. `sample`'s description seems to rely on that. You probably meant `std::distance`.

Yes, my implementation actually uses std::distance; when Tim turned it into a proposal, I think he tried to simplify the description but this wasn't a valid simplification.  Good catch, thanks.

Actually, there's blanket wording in [algorithms.general]/12 that defines + and - for non-random-access iterators for specification purposes. I should have added a cross reference.

That said, we have the RNG-taking version of sample in the working draft now; it may make more sense to accept an output iterator and/or return a container instead of rearranging the range in place. Then I can just define the behavior with the "equivalent to" magic word used elsewhere.

Zhihao Yuan

unread,
May 24, 2016, 2:38:21 AM5/24/16
to std-pr...@isocpp.org
On Mon, May 23, 2016 at 8:24 PM, M.E. O'Neill <one...@cs.hmc.edu> wrote:
>
>
> The whole point of this proposal is that it enhances rather than subverts the library we have. Consider this code:
>
> mt19937_gen rng;
> double x = rng.variate<std::normal_distribution<double>>(17,3);
>
> it's using the beauty of the library we have while being much easer to use.
>

I'm seeing a problem with this code. std::normal_distribution
caches results, so does other distributions internally using it.
But here it looks like that a normal_distribution object will be
created for each run of `variate`, wasting both CPU cycles and
bits from the engine.

I would suggest to remove `variate`.

`uniform` is fine because those two distributions do not cache,
albeit theoretically they could.

And I don't like the interface to forward params for
construction. It doesn't save typing, and breaks the
information about the distribution into two sides of the
expression:

g.generate<std::normal_distribution>(first, last, 0.5);

An optional argument for distribution will do the work:

g.generate(std::normal_distribution(0.5), first, last);

>> That being said, I see no reason why such a class needs member functions for things we already have algorithms for (or will have, in the case of range-generate). The sooner a C++ programmer is encouraged to look to algorithms, the better. We may want to be as simple as Python, but we should not pretend that C++ is Python.

OT: I would be happy to see a utility which is really as simple
as Python, meaning type-erased the engines and allow
assigning from any engines. Actually I tried modifying Melissa's
code to experiment this idea and it just works :)

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://blog.miator.net/

Viacheslav Usov

unread,
May 24, 2016, 7:07:20 AM5/24/16
to ISO C++ Standard - Future Proposals
On Mon, May 23, 2016 at 10:42 PM, T. C. <rs2...@gmail.com> wrote:
Hi,

I've written a paper based on Melissa O'Neill's randutils.hpp (described here), proposing a simple wrapper class template for URNGs with various convenience member functions and automatic nondeterministic seeding (for random number engines):

https://github.com/timsong-cpp/stuff/blob/master/random_generator.md

Adding to what the others have said.

This proposal tries to address two related but different issues.

1. Correct use of random facilities (to obtain good quality random numbers).

2. Easy use of random facilities.

Part one is mostly about seeding PRNGs. It has already been said that there is a proposal addressing just that, and, I think, it is something that we definitely need regardless of #2.

But, in the context of #2, I take issue with the very motivation in your proposal. It assumes that the user is both naive and technical enough to bother specifying the Mersenne Twister PRNG. This seems somewhat schizophrenic to me. Why would the naive user even want to have all the complexity of using a PRNG seeded by a (hopefully) non-deterministic RNG? Why would the naive user not write something like:

std::random_device rng; for (int i = 2; i <= 27; ++i) std::cout << "\t" << std::uniform_int_distribution<>(1, i)(rng) << std::endl; 


And if the user is technical enough to have valid reasons not to use std::random_device in that way, then, as said earlier, the technical user needs a better way to use the random_device as a good seed generator, but that need not be coupled with #2 at this point.

Cheers,
V.

Nicol Bolas

unread,
May 24, 2016, 1:32:17 PM5/24/16
to ISO C++ Standard - Future Proposals


On Monday, May 23, 2016 at 9:24:02 PM UTC-4, M.E. O'Neill wrote:
Nicol Bolas wrote (across three messages):
> Be advised: there's already a proposal for improving the seeding of RNGs.

That's good to know.  (One issue with encouraging std::random_device though is that std::random_device is not currently required to be in any way nondeterministic.  It is allowed to produce the same output on every run of the program.)

The reason for that is so that implementation of C++ are not required to have access to the ability to produce non-deterministic random numbers. Because some of them simply can't do that.

If an implementation doesn't implement `random_device` non-deterministically, there's no reason to expect it to be able to do so for your class either.
 

> As for the idea, if you're interested in a do-everything RNG class, why bother making the random number engine a template parameter? Why expose the underlying engine at all?

Although it's not part of this proposal draft, in my original version I did provide some typedefs for common generators precisely so that people didn't need to specify an engine as a parameter.

> That seems like an over-complication of the idea. If the goal is to be as simple as Python, then just make it `random_generator`, and have implementations decide on what the underlying engine is.
>
> If you're serious about your random engine and distributions, about the specific details of seeding and so forth, you're not going to use this class. And if just want some randomness, then you don't care about the details. You just want a quick, simple, braindead class that spits out randomness in various ways upon request.

The whole point of this proposal is that it enhances rather than subverts the library we have.  Consider this code:

        mt19937_gen rng;
        double x = rng.variate<std::normal_distribution<double>>(17,3);

it's using the beauty of the library we have while being much easer to use.
 
The key idea is that it's easy enough for a beginner, but still handy for an expert, and provides a good stepping stone to the facilities that still exist.  It's not a dumbing down, it's handy glue to avoid annoying and error-prone boilerplate, boilerplate that's confusing to beginners and a hassle for experts. 

And how is that any easier than:

mt19937 rng(/*seed*/);
double x = std::normal_distribution<double>(17, 3)(rng);

I see no reason why a beginner would be unable to write that, but able to write your `variate` version. The only difference between them is that it's a member function, rather than directly creating an external class. You still have to type `normal_distribution<typename>`, so the user still must know that this class exists. You still have to provide the RNG, so you still must know that your rng object exists. And so forth.

Your version reads "random generator, select from, normal distribution, with distribution params". The current version reads "normal distribution, with distribution params, select from, random generator". I don't see that yours reads any better than the other.

Jeffrey Yasskin

unread,
May 24, 2016, 1:48:42 PM5/24/16
to std-pr...@isocpp.org
On Mon, May 23, 2016 at 11:38 PM, Zhihao Yuan <z...@miator.net> wrote:
On Mon, May 23, 2016 at 8:24 PM, M.E. O'Neill <one...@cs.hmc.edu> wrote:
>
>
> The whole point of this proposal is that it enhances rather than subverts the library we have.  Consider this code:
>
>         mt19937_gen rng;
>         double x = rng.variate<std::normal_distribution<double>>(17,3);
>
> it's using the beauty of the library we have while being much easer to use.
>

I'm seeing a problem with this code.  std::normal_distribution
caches results, so does other distributions internally using it.
But here it looks like that a normal_distribution object will be
created for each run of `variate`, wasting both CPU cycles and
bits from the engine.

I think that's fine. It's true that folks wanting to get the last ounce of performance will need to store a distribution object and re-use it, but we can provide the convenient spelling for folks who don't need that. I believe it doesn't even cost that much in the grand scheme of things: it's on the order of a couple extra generated numbers, which is generally less than the cost of a memory allocation, right?

We do similar things when we write functions to return vectors instead of taking pre-allocated storage as an argument.

Jeffrey

Nicol Bolas

unread,
May 24, 2016, 1:57:52 PM5/24/16
to ISO C++ Standard - Future Proposals

Whatever happened to "pay only for what you use"? I thought that was supposed to be a design goal of C++.

I can understand if you don't want that to be your design goal in your library. But what goes into the standard really ought to conform to that.

Jeffrey Yasskin

unread,
May 24, 2016, 2:00:15 PM5/24/16
to std-pr...@isocpp.org
If you're using these convenience functions, "pay only for what you use" means the library can let you pay for them. We shouldn't _remove_ the ability to use the cheaper things, but that design goal doesn't prevent us from including more expensive things too.

Jeffrey

Nicol Bolas

unread,
May 24, 2016, 3:13:59 PM5/24/16
to ISO C++ Standard - Future Proposals

But we shouldn't make the expensive things be more convenient than cheap things. That's what's nice about move support and elision: it encourages doing the convenient thing (returning/passing types by value) and makes it cheap (relatively).

Jeffrey Yasskin

unread,
May 24, 2016, 4:10:14 PM5/24/16
to std-pr...@isocpp.org
First, thanks for proposing an improvement to <random>. We need more people to do things like that.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4582.pdf is the most recent draft of C++17, and what you find in there is very likely to be in the final standard, unless folks find significant problems. So you should assume sample(PopulationIterator first, PopulationIterator last, SampleIterator out, Distance n, UniformRandomNumberGenerator&& g) will stick around.

The per-thread engine is only in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4584.html, the Library Fundamentals TS, and I understand there's some objection to having it at all. I think it'll probably make it into C++20, but there's definitely time to replace it with something better.

I think it's totally defensible to have a library that wraps up a bunch of useful algorithms into a class type. However, in C++ we got burned with the std::string interface, and so tend toward writing the non-essential algorithms as non-member functions, so that it's just as easy to call extensions as it is to call the functions the library author anticipated.

So, pick(), choose(), uniform(), and variate() should probably all be added as non-member algorithms. (I'm a little skeptical of variate(), and maybe choose(range) should return the element, but those are minor details.)

And I do think they're algorithms, even if they're one line each. It takes some ingenuity to write or, more importantly, read that line, and you don't need it as much if it's a function with a good name.

I don't really mind making the design flaws in the standard library stand out. We do make mistakes, and we shouldn't contort later interfaces to disguise those mistakes. We do often change the shape of things to be consistent with older styles, but I'm trying to push folks away from doing that when the older style was actually wrong, and not just out of fashion.

Jeffrey


--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/E197AA74-7F44-434C-B5E9-6DCC2FB12AF4%40cs.hmc.edu.

Jeffrey Yasskin

unread,
May 24, 2016, 4:10:47 PM5/24/16
to std-pr...@isocpp.org
On Mon, May 23, 2016 at 6:02 PM, Nicol Bolas <jmck...@gmail.com> wrote:
Have you not looked at Chapter 25 of the C++ Standard? That's how we do things in C++.
 
Please be more respectful on this list.

Jeffrey

Zhihao Yuan

unread,
May 25, 2016, 12:26:23 AM5/25/16
to std-pr...@isocpp.org
On Tue, May 24, 2016 at 3:09 PM, 'Jeffrey Yasskin' via ISO C++
Standard - Future Proposals <std-pr...@isocpp.org> wrote:
>
> I think it's totally defensible to have a library that wraps up a bunch of
> useful algorithms into a class type. However, in C++ we got burned with the
> std::string interface, and so tend toward writing the non-essential
> algorithms as non-member functions, so that it's just as easy to call
> extensions as it is to call the functions the library author anticipated.
>

This is not as same as the std::string case IMO. For std::string,

1. There are just too many overloads, because only std::string
uses indices. <random> doesn't.

2. Many code bases have their own String types. random_-
generator is just a wrapper; if with my type-erasing suggestion,
there will be only one type.

3. The concepts of find/replace apply to non-characters well. But
uniform(), choose(), etc. are not so outside the context of random
numbers. At least, this generate() is not that generate().

==x cut ==x cut ==

I implemented my idea of a type-erased random_generator
and added some benchmarks, and it turns out to be working
fine. Detailed changes are:

- // using unpredictably seeded default_random_generator
random_generator g;
- g = mt19937(); // using default seeded mt19937
- g.use<mt19937>(); // using unpredictably seeded mt19937
- // distribution object as argument to variate is required
g.variate(std::normal_distribution<double>(0.0, 1.0));
- // distribution object as argument to generate is optional
g.generate(begin(v), end(v));
g.generate(std::normal_distribution<double>(), begin(v),
end(v));

And I added a new method, gauss, modeled after uniform(),
so that the result_type is deduced,

g.gauss(0.0, 1.0);

Also gives me a chance to make uniform variate perform better
using the Kinderman and Monahan method copied from Python.
It kind of works under clang 3.6 + libstdc++:

type-erased generate
: 0.0107519s

type-erased variate
: 0.0203656s <==

type-erased Gaussian
: 0.0137261s <==

direct generate
: 0.014665s <== but what is this?!

Cannot neglect the cost of calling the underlying engine
twice at all under gcc 4.9:

type-erased generate
: 0.00691891s

type-erased variate
: 0.0136719s <==

type-erased Gaussian
: 0.0120535s <==

direct generate
: 0.00603833s

The code is here https://github.com/lichray/randutils .

Zhihao Yuan

unread,
May 25, 2016, 12:40:30 AM5/25/16
to Zhihao Yuan, std-pr...@isocpp.org
On Tue, May 24, 2016 at 11:26 PM, Zhihao Yuan <z...@miator.net> wrote:
> Cannot neglect the cost of calling the underlying engine
> twice at all under gcc 4.9

Err, forgot generate_canonical. Now saner:

type-erased generate
: 0.00681946s
0.996832
type-erased variate
: 0.013105s <==
0.999598
type-erased Gaussian
: 0.00926815s <==
0.998747
direct generate
: 0.00600034s
1.00041

And it's as fast as the type-erased generate case in clang now.
Reply all
Reply to author
Forward
0 new messages