Sign in to follow this  
gorgorath

randomizing an array

Recommended Posts

i have a input array, containing 3 million points (x, y, z) but i want to randomize the location of this points in the array. how to quickly( not realtime ) do this without wasting to much memory

Share this post


Link to post
Share on other sites
I think you'll still have to use an algorithm that runs through the whole lot, even if you have three million of them. Run through in order and for each one in normal order, swap it with one other randomly selected one.

Share this post


Link to post
Share on other sites
Quote:
Original post by gorgorath
but how do i know if the one in random order is not used before


I take it you mean you don't want to re-order an element thats already been re-ordered.

1. This is slower, because you have to make an additional check.
2. It doesn't matter, random means random. I think you would be making your algorithm 'less random' by doing the additional check. At the very least its not an improvement.

Share this post


Link to post
Share on other sites
It doesn't matter - it is still a random order. How do you know when you shuffle a deck of cards that a card you are shuffling hasn't been shuffled before?

The only alternative I can see would be to create another array of empty spaces then copy each item from the original list into a random space in the new array, first checking the random space selected hasn't been used but then you have potential indefinate postponement.

Perhaps there is some clever maths algorithm for this I don't know about.

[EDIT] Sorry Dabooksha. Just behind you.

Share this post


Link to post
Share on other sites
See here for a description of a common and uniformly distributed shuffling algorithm (second paragraph in section). Another link in there goes to here which then links to implementations in both C and Java (you'll have to scroll down a wee bit, or search for "Shuffling an array").

Share this post


Link to post
Share on other sites
Quote:
Original post by DaBookshah
So let me get this straight - You DO have to make that extra check to get a perfectly uniform distribution? I dont get it.

You pass through the list exactly once, there is nothing extra going on.

That shuffle is as good as you're going to get...you have to pass through each location at least once because to do otherwise would be to guarentee that certain positions won't move. This would eliminate a sizeable chunk of the possible permutations, which you most certainly don't want.

Or you could just use Collections.Shuffle. Hopefully, the good folks at Sun are smart enough to have read the material on random shuffles and have implemented a good one.

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
standard reference of mine for the algorithm.

But yeah, just use the standard library. :)

I can't stand that site, because there's way too much noise you sift through. While much of the discussions are extremely interesting, as a reference I find it falls pretty short.

However, in this case it does have one extremely useful passage that makes the Knuth shuffle really fall into place:
Quote:

These solutions only serve to illustrate that if you have a perfect random number generator, you have no need to 'shuffle' anything; simply extract a random element from your list of elements as needed. The original problem was:

Shuffle a deck of cards in linear time.

"Shuffle" could be more realistically defined in terms of human experience as:

Use an imperfect random number generator to create a distribution which approximates true randomness.

Try doing that in linear time. -- AndyPierce




With shuffling, you can't get the same item twice. With a perfect random number generator, you can. Unless "perfect" means "each number comes up exactly once" which means "not very random at all." -- DaveHarris




One could use a random number generator, *if* one can "extract" (remove without replacing) a random element in O(1) time. The problem is that most extraction schemes are more like O(N/2) time, where N is the number of elements. (One can probably improve the deletion time, but one also has to be able to efficiently choose a random element. Optimizing both of these seems hard.) -- anon.




Actually, this is the insight of the linear shuffle algorithm. If you don't care about corrupting the order of a list (such as the unshuffled cards), you can extract any given element in O(1) time by swapping it out with the final element in the list and decrementing the list size. [This made it all clear - see below.] I wonder if this additional mixing in the "unshuffled" part of the deck could be utilized somehow to decrease the shuffling time to faster than linear? -- AndyPierce

I've always understood what the algorithm does, but now I understand why the algorithm does.

CM

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this