Skip to content

using random.choice to sample integers in a large range #5299

Closed

Description

@Midnighter

So I wanted to generate some unique integers with the following code:

import numpy as np
max_int = np.iinfo(np.uint32).max
numbers = np.random.choice(max_int, 10, replace=False)

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.

Activity

  1. njsmith commented on Nov 20, 2014

    @njsmith
    Member

    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:

    import numpy as np
    max_int = np.iinfo(np.uint32).max
    numbers = np.random.choice(max_int, 10, replace=False)

    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.

    Nathaniel J. Smith
    Postdoctoral researcher - Informatics - University of Edinburgh
    http://vorpus.org

  2. Midnighter commented on Nov 20, 2014

    @Midnighter
    Author

    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.

  3. njsmith commented on Nov 20, 2014

    @njsmith
    Member

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

    Nathaniel J. Smith
    Postdoctoral researcher - Informatics - University of Edinburgh
    http://vorpus.org

  4. anntzer commented on Apr 30, 2015

    @anntzer
    Contributor

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

  5. njsmith commented on Apr 30, 2015

    @njsmith
    Member

    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 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?

  6. anntzer commented on Apr 30, 2015

    @anntzer
    Contributor

    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?

  7. rkern commented on Apr 30, 2015

    @rkern
    Member

    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.

  8. njsmith commented on Apr 30, 2015

    @njsmith
    Member

    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:

    I'll have to reiterate my view that numpy.random.seed() should not exist
    and should not be used. @anntzer https://github.com/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.

    —
    Reply to this email directly or view it on GitHub
    #5299 (comment).

    Nathaniel J. Smith -- http://vorpus.org

  9. anntzer commented on Apr 30, 2015

    @anntzer
    Contributor

    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.

  10. rkern commented on Apr 30, 2015

    @rkern
    Member

    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.

  11. njsmith commented on May 3, 2015

    @njsmith
    Member

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

  12. rkern commented on May 3, 2015

    @rkern
    Member

    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.

  13. njsmith commented on May 11, 2015

    @njsmith
    Member

    See also #5158

  14. bashtage commented on Dec 16, 2015

    @bashtage
    Contributor

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

  15. bashtage commented on Jun 1, 2019

    @bashtage
    Contributor

    @mattip Fixed in Generator, can't be fixed in RandomState

    In [1]: import numpy as np
       ...: max_int = np.iinfo(np.uint32).max
    In [2]: g = np.random.Generator()
    In [3]: %timeit numbers = g.choice(max_int, 10, replace=False)
    19.2 µs ± 1.72 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  16. mattip commented on Jun 1, 2019

    @mattip
    Member

    Ok, closing. For performance use the new APIs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions