Bug 9106 – Rename std.random.randomShuffle as std.random.shuffle and small usage change

I suggest to rename the function "std.random.randomShuffle()" to just "std.random.shuffle()". There is no other "shuffle" name in Phobos. And one of the points of the module system is to avoid prefixes like that. Othrwise why the other funtions aren't named randomUniform, randomRandom, etc? See also what the Python Pep8 says about this topic: > There's also the style of using a short unique prefix to group related names > together. This is not used much in Python, but it is mentioned for > completeness. For example, the os.stat() function returns a tuple whose items > traditionally have names like st_mode, st_size, st_mtime and so on. (This is > done to emphasize the correspondence with the fields of the POSIX system call > struct, which helps programmers familiar with that.) > > The X11 library uses a leading X for all its public functions. In Python, > this style is generally deemed unnecessary because attribute and method names > are prefixed with an object, and function names are prefixed with a module > name. The old name should be left as deprecated alias for some time.

Due to the issues regarding random number generator ranges being value types instead of reference types, there's a decent chance that we're going to end up with a std.random2 in the semi-near future. It would make sense to make this sort of change when we do that.

(In reply to comment #1) > Due to the issues regarding random number generator ranges being value types > instead of reference types, there's a decent chance that we're going to end up > with a std.random2 in the semi-near future. It would make sense to make this > sort of change when we do that.

Let me add that I too was surprised when shuffle() didn't work, and by looking at the docs discovered that the correct name was randomShuffle().

Along with the name change it could be a good idea to also change the API a little. I'd like std.random.shuffle to be usable UFCS chains. Currently you can't: void main() { import std.stdio, std.random, std.algorithm, std.array; auto data = [10, 20, 30]; auto pairs = cartesianProduct(data, data).array; pairs.randomShuffle; pairs.writeln; } A possible usage in a UFCS chain: void main() { import std.stdio, std.random, std.algorithm, std.array; auto data = [10, 20, 30]; cartesianProduct(data, data) .array .shuffle .writeln; } An alternative way, more similar to std.algorithm.sort, this helps remember that shuffe works in-place: void main() { import std.stdio, std.random, std.algorithm, std.array; auto data = [10, 20, 30]; cartesianProduct(data, data) .array .shuffle .release .writeln; }

Is there any favour for renaming the other randomSomething functions and types in this way? Note that one rationale for the existing names is by analogy to their C++ equivalents.

(In reply to comment #5) > Is there any favour for renaming the other randomSomething functions and types > in this way? Note that one rationale for the existing names is by analogy to > their C++ equivalents. C++ libs don't always have the best API. D std.string functions API are partially modeled on Python string module and this is good. In Phobos there is now a permutations function that is modelled on C++ equivalent that has a bad API, and I prefer the range-based permutations/combinations lazy generators that are more fit and more useful for D that also have the same API as the equivalent Python generators from the itertools module. So while C++ can sometimes be a good source for inspiration, other times it is not a good source, and other sources like Python or Haskell are much better. I presume the structs/functions you refer to are: RandomCover/randomCover, RandomSample/randomSample I think you can drop the Random/random prefix for the second ones: Sample/sample because sample from a std.random module is clearly related to sampling. Regarding randomCover, it's less clear what "cover" means, so you can leave the "random" prefix if you want.

(In reply to comment #5) > Is there any favour for renaming the other randomSomething functions and types > in this way? Note that one rationale for the existing names is by analogy to > their C++ equivalents. Keep also in mind this law: http://en.wikipedia.org/wiki/Zipf_law Shuffling is a common operation to do, so it's good to have it with a shorter name. Other less common operations can have longer names.

Initially, I would have been against the renaming. The main argument would be that what we have now is consistent as a set of randomization functions operating on ranges, and consistent with use in other languages. For example, wouldn't it be inconsistent to rename some of the functions (shuffle and sample) but not others (randomCover)? But then, a quick search on modern languages revealed they favor the shorter shuffle/sample names. For example, C++ has a legacy random_shuffle but a modern C++11 shuffle for use with C++11 RNGs. Python has shuffle and sample. Java has shuffle. So, the second part of my argument is no longer valid. So, for me, the problem reduced to whether randomCover could use a wholly different, better name. So, how is this function called in other languages? By the way, randomCover is terribly inefficient as of DMD 2.065.0 (quadratic in total), is that addressed somehow in random2? I have a linear-time approach with an associative array in mind, but that would mean reallocating when the AA grows, which is something to avoid for Phobos code, right? Ivan Kazmenko.

(In reply to comment #8) > Initially, I would have been against the renaming. The main argument would be > that what we have now is consistent as a set of randomization functions > operating on ranges, and consistent with use in other languages. For example, > wouldn't it be inconsistent to rename some of the functions (shuffle and > sample) but not others (randomCover)? > > But then, a quick search on modern languages revealed they favor the shorter > shuffle/sample names. For example, C++ has a legacy random_shuffle but a > modern C++11 shuffle for use with C++11 RNGs. Python has shuffle and sample. > Java has shuffle. So, the second part of my argument is no longer valid. Yup, I'm in the same boat as you: initially resistant but now realizing that actually it reflects more typical naming practice. So, I'm inclined at least to switch randomSample => sample (again maintaining an alias for the older name). > So, for me, the problem reduced to whether randomCover could use a wholly > different, better name. So, how is this function called in other languages? Without any knowledge of how it's addressed in other languages, I would have been inclined to call it "permute". But I'll look around (you didn't find anything appropriate in your existing search of Python and C++?) > By the way, randomCover is terribly inefficient as of DMD 2.065.0 (quadratic in > total), is that addressed somehow in random2? I have a linear-time approach > with an associative array in mind, but that would mean reallocating when the AA > grows, which is something to avoid for Phobos code, right? Not addressed yet, but something I intend to look into. For this first iteration the biggest goal was to try and get the API/general design right, with improved internals the next goal. I imagine there will be well-defined algorithms in the literature, it's just a matter of finding said literature, as it's probably in research papers rather than textbooks.

(In reply to comment #9) > to switch randomSample => sample (again maintaining an alias for the older > name). Is randomSample a documented alias? > For this first > iteration the biggest goal was to try and get the API/general design right, > with improved internals the next goal. Then I suggest to fix the API of dice(), it should be a range. It means you give your distribution to a function/struct, and then you have a range that yields values efficiently with that distribution.

(In reply to comment #10) > Is randomSample a documented alias? "Is"? I haven't even made the patch yet :-P But yes, it will be. > Then I suggest to fix the API of dice(), it should be a range. It means you > give your distribution to a function/struct, and then you have a range that > yields values efficiently with that distribution. Already there. ;-) https://github.com/WebDrake/std.random2/blob/master/std/random2/distribution.d#L124 But please, let's try and keep this issue focused -- we can make other issues for the other areas of concern, right now we're talking about renames.

(In reply to comment #9) > (In reply to comment #8) > > So, for me, the problem reduced to whether randomCover could use a wholly > > different, better name. So, how is this function called in other languages? > > Without any knowledge of how it's addressed in other languages, I would have > been inclined to call it "permute". But I'll look around (you didn't find > anything appropriate in your existing search of Python and C++?) No, I didn't see a similar function in other languages. The function itself seems a bit odd to me, even after I got an explanation of a possible use case (in this old thread: http://forum.dlang.org/thread/[email protected]#post-kuvhrfnrrbhzpyoirqgt:40forum.dlang.org).

(In reply to comment #12) > No, I didn't see a similar function in other languages. The function itself > seems a bit odd to me, even after I got an explanation of a possible use case > (in this old thread: > http://forum.dlang.org/thread/[email protected]#post-kuvhrfnrrbhzpyoirqgt:40forum.dlang.org). That thread also refers to this issue: http://d.puremagic.com/issues/show_bug.cgi?id=2898

(In reply to comment #12) > No, I didn't see a similar function in other languages. The function itself > seems a bit odd to me, even after I got an explanation of a possible use case > (in this old thread: > http://forum.dlang.org/thread/[email protected]#post-kuvhrfnrrbhzpyoirqgt:40forum.dlang.org). The rationale that I can see for randomCover would be that it ought to provide a non-destructive (i.e. no in-place shuffling), non-allocating (i.e. no .dup-ing or .save-ing of the original range) way of getting a random permutation of the elements of the range provided as input. However, currently randomCover fails on the second of these in any case, because it contains and allocates an internal array of bools, _chosen. I think that to be honest we simply need to do research and identify a better algorithm than the one currently implemented. One such must exist.

(In reply to comment #14) > The rationale that I can see for randomCover would be that it ought to provide > a non-destructive (i.e. no in-place shuffling), non-allocating (i.e. no > .dup-ing or .save-ing of the original range) way of getting a random > permutation of the elements of the range provided as input. > > However, currently randomCover fails on the second of these in any case, > because it contains and allocates an internal array of bools, _chosen. > > I think that to be honest we simply need to do research and identify a better > algorithm than the one currently implemented. One such must exist. I don't think a no-allocation version would be possible at all. Consider having already covered N/2 elements out of N elements. There are Choose (N, N/2) possible ways to do so. To provide the next element, and then again and again, N/2 more times, we have to remember that exact state somehow. Hence we have to store at least log (Choose (N, N/2)) bits at that moment to distinguish between the states, which is of the order N/2.

(In reply to comment #15) > I don't think a no-allocation version would be possible at all. Consider > having already covered N/2 elements out of N elements. There are Choose (N, > N/2) possible ways to do so. To provide the next element, and then again and > again, N/2 more times, we have to remember that exact state somehow. Hence we > have to store at least log (Choose (N, N/2)) bits at that moment to distinguish > between the states, which is of the order N/2. I think I may have struck gold in the search for appropriate algorithms: http://gan.anu.edu.au/~brent/pd/Arndt-thesis.pdf It'll take some time to read and digest this and see if it's really a good source of potential algorithms, but I thought I'd share the reference in any case. See also: http://forum.dlang.org/post/[email protected]

(In reply to comment #16) > (In reply to comment #15) > > I don't think a no-allocation version would be possible at all. Consider > > having already covered N/2 elements out of N elements. There are Choose (N, > > N/2) possible ways to do so. To provide the next element, and then again and > > again, N/2 more times, we have to remember that exact state somehow. Hence we > > have to store at least log (Choose (N, N/2)) bits at that moment to distinguish > > between the states, which is of the order N/2. > > I think I may have struck gold in the search for appropriate algorithms: > http://gan.anu.edu.au/~brent/pd/Arndt-thesis.pdf > > It'll take some time to read and digest this and see if it's really a good > source of potential algorithms, but I thought I'd share the reference in any > case. > > See also: > http://forum.dlang.org/post/[email protected] The paper looks interesting (albeit likely for other purposes), thank you for the link. Regarding randomCover, Andrei's example with an LCG is able to generate only few permutations of order n at all. There are just a few dozen bits of information if the initial state and the transition function of any LCG modulo n. Thus there will be O(Poly(n)) (say, n^3 if we choose seed, multiplier and summand arbitrarily) different permutations possibly appearing in the LCG generation process. Still, there are n! different permutations of order n. A good randomCover would be able to generate a uniformly distributed permutation of any order n, provided that the underlying random bits are uniform and independent (that is, from an ideal randomness source). I believe no algorithm would suffice to counter the proof above which states that we need to store at least n bits during the course of randomCover. And there does not seem to be much justification in providing a skewed (that is, non-uniform) randomCover in Phobos. So, I believe the solution with least allocations would be to allocate once when the randomCover struct/class is initialized (possibly with an option to reuse space given in an extra argument), and then proceed allocation-free. The downside is that it will be always Theta(n) bits, while if we knew ahead the maximum number of calls k to randomCover, Theta(k) memory would suffice. ----- Well, that's offtopic here. Is there a proper place to put it? A wiki discussion page, perhaps? Forum threads tend to get lost...

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/phobos/issues/9943 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB