CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: random shuffle

  1. #1
    Join Date
    Aug 2000
    Posts
    18

    random shuffle

    Does anybody have a fast routine to do a random shuffle of an array of integers? I have looked at the random_shuffle template, but I want to shuffle the array itself, rather than vectors. I have been using the rand() function then using a modulus to pick a random entry and then swapping memory. It works, but I can't help thinking that there must be a faster way.

    thanks


  2. #2
    Join Date
    Nov 1999
    Location
    Dresden / Germoney
    Posts
    1,402

    Re: random shuffle



    From inquiry.com:
    >>>>
    Using random_shuffle() with Built-in Arrays
    You shouldn't be concerned about the overhead of using containers instead of built-in arrays. All STL algorithms apply to sequences, not just containers. Thus, you can use random_shuffle() with built-in arrays as well. Make sure that the second argument of random_shuffle() points one element past the array bounds:

    char carr[4] = {'a', 'b', 'c', 'd'};
    /*carr+4 points one position past array bounds*/
    random_shuffle(carr, carr+4);
    for (int i = 0; i < 4; i++)
    cout<<carr[i]; /* display shuffled elements */




    However, it depends on the actual STL implementation how fast it is.

    A simple algorithm to shuffle N integers a[0]..a[N-1]:
    pick an random number r from [0..N-1]
    swap a[r] with a[N-1]
    N=N-1 and repeat until N reaches 1




    (I haven't tested it, I just proved it correct ;-)





  3. #3
    Join Date
    Aug 2000
    Posts
    18

    Re: random shuffle

    The simple routine at the end of your post was the same way I originally coded mine, but I hoped that something else would be faster. I needed to shuffle an array many times to test a simulation. When I tested the template class, it was exactly the same speed as my original routine. (49 seconds to shuffle a deck of cards 5 million times on 500 mHz P3)

    thanks


  4. #4
    Join Date
    Nov 1999
    Location
    Dresden / Germoney
    Posts
    1,402

    Re: random shuffle

    Hi,

    No, As much as I meditated about it, there is no faster algorithm - unless you want to sacrifice some randomness.

    5 million shuffles in fifty seconds sounds relatively cool - but I don't know what you need.

    I assume you already switched to a release build, and perhaps played with the optimization options a bit, if so you could just eval some low level optimizations - but only if it#s woth the trouble. I could imagine using an inlined rand() replacement (one of the x=(a+x)%b generators should be perfect, if you re-shuffle the previous table you need no extra shuffle table) Check Knuth for good values of a and b.

    If you don't know if your snipped is "optimal" (mostly it is if you don't do something blatantly wrong with nowadays compilers), just post it.

    Good luck.
    Peter




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)