You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
using random.choice to sample integers in a large range #5299
I wanted these numbers as deterministic seeds for some simulations. When I do this almost 16 GB of memory are filled.
I looked into the code for choice and in this case it essentially generates a permutation, similar to shuffling a np.arange(max_int), in order to then take a small slice from that array. This seems like a bad strategy since providing only an int to random.choice makes it clear that numbers in that range should be sampled. At least when the integer argument a is much larger than the argument size.
So for now I will just generate a set of numbers but I was wondering if there is a more general way.
Reacted by Peleg Michaeli, Jonathan de Bruin, Vitchyr Pong, Sheik Irfan Basha, Prikers and Benedikt Boecking
I guess there are probably fancy algorithms out there for efficient
sampling-without-replacement but I don't know them off the top of my head
:-). One plausible approach would be
def int_choice(max_int, count):
out = np.empty((count,))
for i in range(count):
raw = randint(0, max_int - i)
out[i] = raw + np.sum(out[:i] <= raw)
return out
which is O(count^2) but faster than simple rejection sampling. Or,
emulating the classic random-permutation-by-swapping algorithm, something
like
def int_choice(max_int, count):
sparse_arr = {}
def sparse_get(idx)
return sparse_arr.get(idx, idx)
def sparse_swap(idx1, idx2):
val1 = sparse_get(idx1)
val2 = sparse_get(idx2)
sparse_arr[idx1] = val2
sparse_arr[idx2] = val1
out = np.empty((count,))
for i in range(count):
sparse_swap(i, randint(i, max_int))
out[i] = sparse_get(i)
return out
which is O(count) on time and requires O(count) auxiliary storage (but with
some non-trivial multiplier due to hash-table overhead, so if count is on
the same order as max_int then the current strategy is still probably
better).
Note also that I haven't tested these and could easily have made an error
in conception or implementation, treat these as off-the-cuff sketches :-).
Unfortunately we can't actually change implementations willy-nilly, because
changing the implementation would reproducibility of seeded results :-/. So
a precondition to making any improvements to this method is to implement
some infrastructure for letting people choose whether they want the
latest-and-greatest sampling algorithms or the old-but-compatible versions.
This has been extensively discussed, we can definitely do it, but no-one's
stepped up to do the work, so this bug will probably remain open for a
while...
On Thu, Nov 20, 2014 at 12:33 PM, Moritz Emanuel Beber < [email protected]> wrote:
So I wanted to generate some unique integers with the following code:
I wanted these numbers as deterministic seeds for some simulations. When I
do this almost 16 GB of memory are filled.
I looked into the code for choice and in this case it essentially
generates a permutation, similar to shuffling a np.arange(max_int), in
order to then take a small slice from that array. This seems like a bad
strategy since providing only an int to random.choice makes it clear that
numbers in that range should be sampled. At least when the integer argument
a is much larger than the argument size.
So for now I will just generate a set of numbers but I was wondering if
there is a more general way.
—
Reply to this email directly or view it on GitHub #5299.
Thank you for your suggestions and thoughts Nathaniel. When you mention that discussion, was that spread over one/several issues or more on the mailing list? Do you perhaps have a link to share? Thanks.
The best discussion I can find in a quick search is in #2047. Generally
speaking the idea is simple, though: have some "RNG version" that you can
specify as part of creating a RandomState object (or calling seed), so we
can have new versions that use fancier algorithms while keeping the old
versions around. The details of how exactly to arrange the API would need
to get hashed out on the mailing list, but fortunately it's not rocket
science :-)
On Thu, Nov 20, 2014 at 5:11 PM, Moritz Emanuel Beber < [email protected]> wrote:
Thank you for your suggestions and thoughts Nathaniel. When you mention
that discussion, was that spread over one/several issues or more on the
mailing list? Do you perhaps have a link to share? Thanks.
—
Reply to this email directly or view it on GitHub #5299 (comment).
Actually, there is Floyd's algorithm (see e.g. http://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values, or just the pure-Python implementation in the stdlib's random.py (the n < setsize case)).
I'd be happy to work on it, but only once API details w.r.t. as backwards compatibility are agreed upon. (My suggestion after thinking 30s about it: Provide various implementations of RandomState named after the version of numpy in which they were first introduced (RandomState_0_0 (or whenever the API appeared), RandomState_1_10 if we introduce a backwards incompatible change at the next release, etc.) and alias RandomState to the last version. Also provide a helper random.patch_to_version("xxx") which changes the alias to some old version and also patches the np.random module to use the methods of that RandomState. Now, if you want to future-proof your code, just call patch_to_version to fix the version.)
I'm not a big fan of your quick API sketch, mostly b/c we already have a way to say "I want to future-proof my code", that's seed's job. (And monkeypatching is always bad news -- e.g. in this case it's particularly nasty, if someone has from np.random import randn at the top of their file then your patch_to_version will mysteriously not work, b/c it would only affect np.random.randn, not mymodule.randn.)
I would love to see some improvement happen here though, and I don't think it would take much work to sort out an API that would be acceptable to everyone. It seems like one of those classic cases where there's a high activation energy to get started, but once someone takes the effort to overcome that then suddenly we'll see lots of neat improvements :-). @anntzer: If you're at Berkeley, want to grab lunch sometime and work out a good API? Like... Monday, maybe?
Sorry, I disagree, future-proofing your code means sticking to the same numpy version (I mean, apparently it was totally fine to completely change the behavior of diag, which IMHO affects many more users than this). Also, if you really care about reproducibility of your random stream you should directly use a RandomState object for your module/package directly anyways, because using the global seed will fail as soon as somebody else tries to get some random number (e.g., you decide to use some randomizing unittest runner (pytest-random?) and they somehow decide to use numpy's RNG).
As a side-note, I also believe that whenever the new code is "clearly" better than the old one (e.g. faster by all benchmarks but with equal amount of memory and quality of randomness) it should be enabled by default, again because this probably affects more people than reproducibility of random streams.
I'm always up for lunch. Let's move this discussion to email?
I'll have to reiterate my view that numpy.random.seed() should not exist and should not be used. @anntzer is correct in that passing around your RandomState is the best and most idiomatic way to control your output.
That said, the current policy is that the implementations in RandomState are considered frozen, except for extensions and bug fixes. New methods can be added with alternative algorithms, and new classes can be made. I can't be fussed to care about the numpy.random.* aliases, though, since you shouldn't be using them if you care about the output. The name RandomState should not be a moving target, IMO. I could be convinced that we should have a name that is explicitly a moving target, though, i.e. CurrentBestPRNG or something like that.
I agree that np.random.seed is terrible, and wouldn't even object to
deprecating it if you want to try pushing that through, but we're stuck
with it for now regardless. That's orthogonal to the issue here though --
np.random.seed, RandomState.seed, and RandomState.init (which basically
just calls self.seed with any arguments) are the same for present purposes.
.
The general approach I think we should take -- and which I think from what
you're saying should meet with your approval -- is something like this:
RandomState(integer) becomes an alias for something like
RandomState(seed=integer, underlying_generator="MT32",
method_implementations="1.0"), whereas plain RandomState() with no seed
specified becomes an alias for RandomState(seed=,
underlying_generator="the fastest one we have",
method_implementations="latest and greatest"). And of course you can also
specify this explicitly if you want to lock in RandomState(seed=integer,
underlying_generator="PCG", method_implementations="1.11") or whatever and
numpy 1.30 will still know what that means and be able to replicate numpy
1.11's best attempts.
.
And calling RandomState.seed() is the same as reinitializing the object
from scratch so it takes the same arguments.
.
Then this automatically works for np.random.seed(...) as well -- when you
first start up np.random.randn etc. give you the latest and greatest, but
people who do call np.random.seed(integer) still get the streams they were
hoping for. (At least in the lucky cases where this ever worked.)
On Thu, Apr 30, 2015 at 1:12 AM, Robert Kern [email protected]
wrote:
That said, the current policy is that the implementations in RandomState
are considered frozen, except for extensions and bug fixes. New methods can
be added with alternative algorithms, and new classes can be made. I can't
be fussed to care about the numpy.random.* aliases, though, since you
shouldn't be using them if you care about the output. The name RandomState
should not be a moving target, IMO. I could be convinced that we should
have a name that is explicitly a moving target, though, i.e.
CurrentBestPRNG or something like that.
—
Reply to this email directly or view it on GitHub #5299 (comment).
There are cases where you don't care that much about long-term reproducibility (i.e. across numpy versions), but do care about short-term reproducibility (e.g. to debug/profile/etc. some tricky randomized algorithm) (this happens to be my case right now, but I doubt I'm the only one). For that use case, I think @rkern's approach (a "CurrentBestPRNG", although that name sounds awkward) works.
At least for the core generators, I am much more inclined to handle them with different classes, like the stdlib's random module does. The core generators that I am most interested in adding are those that can be parameterized, but each one in different ways. Making the argument signature dependent on the value of one of the arguments is an antipattern I would like to avoid.
I am inclined against having the distribution implementations change by a configuration parameter, but I could be persuaded. Not least, having this mechanism be orthogonal to the selection of the core generator would be ideal. Some points on implementation: I would recommend that if we do have multiple versions, each one can be explicitly requested by name, i.e. box_mueller_normal() and ziggurat_normal() while normal() uses whichever one is configured to be used.
Also note that some distributions use other distributions underneath, often standard_exponential(), so if that is configured to change, we should decide whether the dependent distributions also change. I think arguments could go both ways. On the one hand, the whole point is to get the best (fastest, whatever) implementation wherever that implementation is used; you should get that implementation even when it is implicit. On the other hand, it becomes a lot less clear what exactly you are changing when you request a new implementation. On the gripping hand, changing anything about how you sample in your program essentially changes the whole stream anyways, so it's no big deal if your weibull() method spits out different numbers when you select the Ziggurat exponential implementation.
Sure, I agree that the way to go would be to have the core generator a
separate object, and that's compatible with the api I sketched. (Assume the
strings I wrote are the convenience sugar for the most common options.)
Can you give any example of when you would want to be able to specify that
you want only box-mueller normal deviates versus ziggurat normal deviates?
(Keeping in mind also that we may well have multiple different ziggurat
samplers over time, etc., since iiuc there are ways to tweak and optimize
these algorithms that we may fine-tune over time.)
The issue you raise the end is part of why I suggest configuring all the
method implementations in one lump, instead of doing it on a method by
method basis. If they all evolve in lockstep then that issue goes away.
On Apr 30, 2015 5:56 AM, "Robert Kern" [email protected] wrote:
At least for the core generators, I am much more inclined to handle them
with different classes, like the stdlib's random module does. The core
generators that I am most interested in adding are those that can be
parameterized, but each one in different ways. Making the argument
signature dependent on the value of one of the arguments is an antipattern
I would like to avoid.
I am inclined against having the distribution implementations change by a
configuration parameter, but I could be persuaded. Not least, having this
mechanism be orthogonal to the selection of the core generator would be
ideal. Some points on implementation: I would recommend that if we do have
multiple versions, each one can be explicitly requested by name, i.e.
box_mueller_normal() and ziggurat_normal() while normal() uses whichever
one is configured to be used.
Also note that some distributions use other distributions underneath,
often standard_exponential(), so if that is configured to change, we
should decide whether the dependent distributions also change. I think
arguments could go both ways. On the one hand, the whole point is to get
the best (fastest, whatever) implementation wherever that implementation is
used; you should get that implementation even when it is implicit. On the
other hand, it becomes a lot less clear what exactly you are changing when
you request a new implementation. On the gripping hand, changing anything about how you sample in your program essentially changes the
whole stream anyways, so it's no big deal if your weibull() method spits
out different numbers when you select the Ziggurat exponential
implementation.
—
Reply to this email directly or view it on GitHub #5299 (comment).
I wasn't talking about the implementation details; I was talking about the API. The user should select their core PRNG by instantiating different classes, a la stdlib's random.
At least for the core generators, I am much more inclined to handle them with different classes, like the stdlib's random module does. The core generators that I am most interested in adding are those that can be parameterized, but each one in different ways. Making the argument signature dependent on the value of one of the arguments is an antipattern I would like to avoid.
This is how it now stands. Right now, 4 python modules are produced:
randomkit - The core NumPy RNG, should be identical, although refactored
pcg32 - 32 bit PCG
pcg64 - 64 bit PCG
dummy - Dummy RNG
If one added more, e.g., SFMT, this would produce yet another module.
Each module exposes everything through a RandomState, so that there are different random states, randomkit.RandomState and pcg32.RandomState.
These are directly accessible. One could imagine a high level api that would provide some unification, although it isn't clear that this should be called RandomState. Something MATLAB-like would be rng('mt19337') to get MT 19337, rng('pcg32'), etc. These would return the module.RandomState with entropy initialization. Specific seeding can be done through RNG-specific seed, get_state, set_state functions..
Activity
njsmith commentedon Nov 20, 2014
I guess there are probably fancy algorithms out there for efficient
sampling-without-replacement but I don't know them off the top of my head
:-). One plausible approach would be
def int_choice(max_int, count):
out = np.empty((count,))
for i in range(count):
raw = randint(0, max_int - i)
out[i] = raw + np.sum(out[:i] <= raw)
return out
which is O(count^2) but faster than simple rejection sampling. Or,
emulating the classic random-permutation-by-swapping algorithm, something
like
def int_choice(max_int, count):
sparse_arr = {}
def sparse_get(idx)
return sparse_arr.get(idx, idx)
def sparse_swap(idx1, idx2):
val1 = sparse_get(idx1)
val2 = sparse_get(idx2)
sparse_arr[idx1] = val2
sparse_arr[idx2] = val1
out = np.empty((count,))
for i in range(count):
sparse_swap(i, randint(i, max_int))
out[i] = sparse_get(i)
return out
which is O(count) on time and requires O(count) auxiliary storage (but with
some non-trivial multiplier due to hash-table overhead, so if count is on
the same order as max_int then the current strategy is still probably
better).
Note also that I haven't tested these and could easily have made an error
in conception or implementation, treat these as off-the-cuff sketches :-).
Unfortunately we can't actually change implementations willy-nilly, because
changing the implementation would reproducibility of seeded results :-/. So
a precondition to making any improvements to this method is to implement
some infrastructure for letting people choose whether they want the
latest-and-greatest sampling algorithms or the old-but-compatible versions.
This has been extensively discussed, we can definitely do it, but no-one's
stepped up to do the work, so this bug will probably remain open for a
while...
On Thu, Nov 20, 2014 at 12:33 PM, Moritz Emanuel Beber <
[email protected]> wrote:
Nathaniel J. Smith
Postdoctoral researcher - Informatics - University of Edinburgh
http://vorpus.org
Midnighter commentedon Nov 20, 2014
Thank you for your suggestions and thoughts Nathaniel. When you mention that discussion, was that spread over one/several issues or more on the mailing list? Do you perhaps have a link to share? Thanks.
njsmith commentedon Nov 20, 2014
The best discussion I can find in a quick search is in #2047. Generally
speaking the idea is simple, though: have some "RNG version" that you can
specify as part of creating a RandomState object (or calling seed), so we
can have new versions that use fancier algorithms while keeping the old
versions around. The details of how exactly to arrange the API would need
to get hashed out on the mailing list, but fortunately it's not rocket
science :-)
On Thu, Nov 20, 2014 at 5:11 PM, Moritz Emanuel Beber <
[email protected]> wrote:
Nathaniel J. Smith
Postdoctoral researcher - Informatics - University of Edinburgh
http://vorpus.org
anntzer commentedon Apr 30, 2015
Actually, there is Floyd's algorithm (see e.g. http://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values, or just the pure-Python implementation in the stdlib's random.py (the
n < setsizecase)).I'd be happy to work on it, but only once API details w.r.t. as backwards compatibility are agreed upon. (My suggestion after thinking 30s about it: Provide various implementations of RandomState named after the version of numpy in which they were first introduced (RandomState_0_0 (or whenever the API appeared), RandomState_1_10 if we introduce a backwards incompatible change at the next release, etc.) and alias RandomState to the last version. Also provide a helper
random.patch_to_version("xxx")which changes the alias to some old version and also patches thenp.randommodule to use the methods of that RandomState. Now, if you want to future-proof your code, just callpatch_to_versionto fix the version.)njsmith commentedon Apr 30, 2015
Oo, I didn't know Floyd's algorithm, that's neat.
I'm not a big fan of your quick API sketch, mostly b/c we already have a way to say "I want to future-proof my code", that's
seed's job. (And monkeypatching is always bad news -- e.g. in this case it's particularly nasty, if someone hasfrom np.random import randnat the top of their file then yourpatch_to_versionwill mysteriously not work, b/c it would only affectnp.random.randn, notmymodule.randn.)I would love to see some improvement happen here though, and I don't think it would take much work to sort out an API that would be acceptable to everyone. It seems like one of those classic cases where there's a high activation energy to get started, but once someone takes the effort to overcome that then suddenly we'll see lots of neat improvements :-). @anntzer: If you're at Berkeley, want to grab lunch sometime and work out a good API? Like... Monday, maybe?
anntzer commentedon Apr 30, 2015
Sorry, I disagree, future-proofing your code means sticking to the same numpy version (I mean, apparently it was totally fine to completely change the behavior of
diag, which IMHO affects many more users than this). Also, if you really care about reproducibility of your random stream you should directly use a RandomState object for your module/package directly anyways, because using the globalseedwill fail as soon as somebody else tries to get some random number (e.g., you decide to use some randomizing unittest runner (pytest-random?) and they somehow decide to use numpy's RNG).As a side-note, I also believe that whenever the new code is "clearly" better than the old one (e.g. faster by all benchmarks but with equal amount of memory and quality of randomness) it should be enabled by default, again because this probably affects more people than reproducibility of random streams.
I'm always up for lunch. Let's move this discussion to email?
rkern commentedon Apr 30, 2015
I'll have to reiterate my view that
numpy.random.seed()should not exist and should not be used. @anntzer is correct in that passing around yourRandomStateis the best and most idiomatic way to control your output.That said, the current policy is that the implementations in
RandomStateare considered frozen, except for extensions and bug fixes. New methods can be added with alternative algorithms, and new classes can be made. I can't be fussed to care about thenumpy.random.*aliases, though, since you shouldn't be using them if you care about the output. The nameRandomStateshould not be a moving target, IMO. I could be convinced that we should have a name that is explicitly a moving target, though, i.e.CurrentBestPRNGor something like that.njsmith commentedon Apr 30, 2015
I agree that np.random.seed is terrible, and wouldn't even object to
deprecating it if you want to try pushing that through, but we're stuck
with it for now regardless. That's orthogonal to the issue here though --
np.random.seed, RandomState.seed, and RandomState.init (which basically
just calls self.seed with any arguments) are the same for present purposes.
.
The general approach I think we should take -- and which I think from what
you're saying should meet with your approval -- is something like this:
RandomState(integer) becomes an alias for something like
RandomState(seed=integer, underlying_generator="MT32",
method_implementations="1.0"), whereas plain RandomState() with no seed
specified becomes an alias for RandomState(seed=,
underlying_generator="the fastest one we have",
method_implementations="latest and greatest"). And of course you can also
specify this explicitly if you want to lock in RandomState(seed=integer,
underlying_generator="PCG", method_implementations="1.11") or whatever and
numpy 1.30 will still know what that means and be able to replicate numpy
1.11's best attempts.
.
And calling RandomState.seed() is the same as reinitializing the object
from scratch so it takes the same arguments.
.
Then this automatically works for np.random.seed(...) as well -- when you
first start up np.random.randn etc. give you the latest and greatest, but
people who do call np.random.seed(integer) still get the streams they were
hoping for. (At least in the lucky cases where this ever worked.)
On Thu, Apr 30, 2015 at 1:12 AM, Robert Kern [email protected]
wrote:
Nathaniel J. Smith -- http://vorpus.org
anntzer commentedon Apr 30, 2015
There are cases where you don't care that much about long-term reproducibility (i.e. across numpy versions), but do care about short-term reproducibility (e.g. to debug/profile/etc. some tricky randomized algorithm) (this happens to be my case right now, but I doubt I'm the only one). For that use case, I think @rkern's approach (a "CurrentBestPRNG", although that name sounds awkward) works.
rkern commentedon Apr 30, 2015
At least for the core generators, I am much more inclined to handle them with different classes, like the stdlib's
randommodule does. The core generators that I am most interested in adding are those that can be parameterized, but each one in different ways. Making the argument signature dependent on the value of one of the arguments is an antipattern I would like to avoid.I am inclined against having the distribution implementations change by a configuration parameter, but I could be persuaded. Not least, having this mechanism be orthogonal to the selection of the core generator would be ideal. Some points on implementation: I would recommend that if we do have multiple versions, each one can be explicitly requested by name, i.e.
box_mueller_normal()andziggurat_normal()whilenormal()uses whichever one is configured to be used.Also note that some distributions use other distributions underneath, often
standard_exponential(), so if that is configured to change, we should decide whether the dependent distributions also change. I think arguments could go both ways. On the one hand, the whole point is to get the best (fastest, whatever) implementation wherever that implementation is used; you should get that implementation even when it is implicit. On the other hand, it becomes a lot less clear what exactly you are changing when you request a new implementation. On the gripping hand, changing anything about how you sample in your program essentially changes the whole stream anyways, so it's no big deal if yourweibull()method spits out different numbers when you select the Ziggurat exponential implementation.njsmith commentedon May 3, 2015
Sure, I agree that the way to go would be to have the core generator a
separate object, and that's compatible with the api I sketched. (Assume the
strings I wrote are the convenience sugar for the most common options.)
Can you give any example of when you would want to be able to specify that
you want only box-mueller normal deviates versus ziggurat normal deviates?
(Keeping in mind also that we may well have multiple different ziggurat
samplers over time, etc., since iiuc there are ways to tweak and optimize
these algorithms that we may fine-tune over time.)
The issue you raise the end is part of why I suggest configuring all the
method implementations in one lump, instead of doing it on a method by
method basis. If they all evolve in lockstep then that issue goes away.
On Apr 30, 2015 5:56 AM, "Robert Kern" [email protected] wrote:
rkern commentedon May 3, 2015
I wasn't talking about the implementation details; I was talking about the API. The user should select their core PRNG by instantiating different classes, a la stdlib's
random.njsmith commentedon May 11, 2015
See also #5158
Allow multiple versions of RandomState: init' work.
bashtage commentedon Dec 16, 2015
This is how it now stands. Right now, 4 python modules are produced:
randomkit- The core NumPy RNG, should be identical, although refactoredpcg32- 32 bit PCGpcg64- 64 bit PCGdummy- Dummy RNGIf one added more, e.g., SFMT, this would produce yet another module.
Each module exposes everything through a
RandomState, so that there are different random states,randomkit.RandomStateandpcg32.RandomState.These are directly accessible. One could imagine a high level api that would provide some unification, although it isn't clear that this should be called
RandomState. Something MATLAB-like would berng('mt19337')to get MT 19337,rng('pcg32'), etc. These would return the module.RandomStatewith entropy initialization. Specific seeding can be done through RNG-specificseed,get_state,set_statefunctions..ENH: Add tail shuffle
ENH: Add tail shuffle
ENH: Improvce choice without replacement
ENH: Improvce choice without replacement
ENH: Improvce choice without replacement
bashtage commentedon Jun 1, 2019
@mattip Fixed in Generator, can't be fixed in RandomState
mattip commentedon Jun 1, 2019
Ok, closing. For performance use the new APIs.