Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Check randomly generated numbers have not been used before (shuffle)

by oiskuu (Hermit)
on Jun 20, 2014 at 20:17 UTC ( #1090688=note: print w/replies, xml ) Need Help??


in reply to Check randomly generated numbers have not been used before

Two approaches that might be of interest. In case you require a randomized list of unique numbers, then the problem isn't really about rand() generation, it's a list shuffling task.

use List::Util q(shuffle); print join q(,), shuffle 1 .. 1000;
With a large number of elements, various optimizations may become appropriate, such as packed vectors, mmap'ed files, etc.

The second approach is to use a suitable pseudo-random number generator. One might choose a very simple linear congruential generator with a period of m. E.g. with m==224, a range and period of 16777216 is obtainable. Discard values >= 1e7 and you have a sequence of non-repeating pseudo-random numbers to cover the required 7-digit range. Keep in mind that this list will be a very weak and pseudo random sequence, suitable only in cases where the demands are casual.

  • Comment on Re: Check randomly generated numbers have not been used before (shuffle)
  • Download Code

Replies are listed 'Best First'.
Re^2: Check randomly generated numbers have not been used before (shuffle)
by LanX (Chancellor) on Jun 21, 2014 at 01:30 UTC
    ++ for suggesting a pseudo random generator! :)

    This thread became (as usual) so long b/c the OP doesn't give us much detail, like

    • motivation: why the numbers need to be random
    • quantity: how many of them need to be generated
    • performance: how fast the solution needs to be

    My first guess was to suggest a very simple algebraic Linear congruential generator where each element in the sequence is predictable and collisions are avoided.

    But as usual because of lack of information we try to answer a wide range of possible questions. :(

    Cheers Rolf

    (addicted to the Perl Programming Language)

Re^2: Check randomly generated numbers have not been used before (2 dimensional shuffle)
by LanX (Chancellor) on Jun 21, 2014 at 15:38 UTC
    > With a large number of elements, various optimizations may become appropriate

    Actually shuffling 1..1e7 takes an eternity, but shuffling 1..1000 for 10000 times only takes seconds and is deterministic depending on the seed of srand .

    So a second rand to chose one of these 10000 arrays and shift one element should be easy, fast, deterministic and produce quite good distributed results.

    The mileage of the OP may vary. :)

    BTW

    The real complication of this whole approach of "try again another random number if already taken" idea, cause this will slow down considerably after a while if millions of random numbers need to be tried out.

    Thats why shuffling is the far better approach.

    Cheers Rolf

    (addicted to the Perl Programming Language)

      BTW

      The real complication of this whole approach of "try again another random number if already taken" idea, cause this will slow down considerably after a while if millions of random numbers need to be tried out.

      Here are the average times, per 1000 part numbers, for the first 9 millions from the 10 million range:

      [1000000]Ave: 0.003626 [2000000]Ave: 0.004084 [3000000]Ave: 0.004650 [4000000]Ave: 0.005443 [5000000]Ave: 0.006492 [6000000]Ave: 0.008238 [7000000]Ave: 0.010892 [8000000]Ave: 0.017433 [9000000]Ave: 0.300273

      So sure, allocating the 9th million takes roughly 100 times as long as the first.

      But that still means that unless the OPs company are going to need to allocate 1 million new part numbers in less than 5 minutes, the "slow down" isn't going to be any kind of a problem.

      And if they are going to allocate such ridiculously high numbers of new part numbers, that the allocation rate is a limiting factor; then they sure as heck need to be starting with a much larger range, otherwise they will run out in their first hour of trading.

      You've yet to learn the difference between knowledge and expertise.

      The knowledgeable are aware of theories, concepts and formulae.

      The experienced know when to apply them.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1090688]
help
Chatterbox?
[Corion]: marioroy: Oh, that's always cool, having API-compatible modules. This makes testing and comparing things much easier
[marioroy]: IPC in MCE::Shared can handle 400k (sends) per second. That's seems a lot for being a pure-Perl module. After making the release, will come back and post a solution for a node by a fellow wanting faster logging.
[Corion]: While working on WWW::Mechanize:: Chrome, I had the suspicion that AnyEvent was doing something wrong, but I was able to swap it out for Mojolicious and the error persisted.
[Corion]: Of course, the error was in my own code ;)
[marioroy]: Corion, start and start_child in MCE::Hobo::Manager return a MCE::Hobo object, whereas P::FM returns the PID. I can have it return the PID though. I tried Hobo::Manager with several P::FM modules, just changed P::FM to MCE::Hobo::Manager and it works.
[marioroy]: I also have a Hobo driver for Forklift allowing folks to use in multiple classes, no conflicts with one another. That's not possible for P::FM.
[Discipulus]: congrats marioroy!
[marioroy]: CORE::wait works well eventhough multiple instances or classes using Hobo::Manager.

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (5)
As of 2017-05-26 08:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?