10 September 2008

Fastest Random Array Generator

While searching the net for fastest way to create random array of numbers I was surprised to see some very bad solutions. The idea behind algorithm I found was intuitive. Let’s say we want to create random array with numbers from 0 to 99. We will generate first one random number with:

var myRan:Number = Math.floor(Math.random()*100);

Then we will check if this number already exists in our array, which is empty at start. If it doesn’t exists we append this number with push(), if already exists we do nothing, code goes to next iteration and again it generate new random number. Seems like simple and good solution, but in fact this solution is very bad, very slow and it just might crush your application.

Let’s say we were very lucky and we populate first 99 places in our random array. All the code still have to do is to find one more. Let’s say we need just number 13. Algorithm will circle around the loop until it randomly generates number 13! This might be a problem if computer choose between 100 or even 1.000 numbers in every iteration. It might last seconds, which is eternity in web applications standard. And don’t forget that number 13 is not very lucky one!

I figured that in the end our random array will have all the numbers from 0 to 99, no more no less and that gave me the idea for fastest random array generator.
First, let’s name our function:

function createRandomArray(limit):Array {

limit will decide how many numbers we want from 0
At the beginning let’s have two empty arrays:

starter = [];
finale = [];

Now, we will push all needed numbers to starter:

for(i=0; i<limit; i++) {

starter.push(i);

}


The trick is to take one number from starter, add it to finale and delete that number from starter array in one iteration. To make things random, we will choose random starter INDEX, like this:

while(starter.length > 0) {

var choose = Math.floor(Math.random()*starter.length);

finale.push(starter[choose]);


starter.splice(choose, 1);


}


We do this until there are numbers inside starter array. At the end, we return result array:

return finale;}

I think this might be the candidate for fastest random array generator.
.

5 comments:

Keith Peters said...

Another idea is to create the linear array like you did in the first step, and then sort it with a random sort function:

list.sort(randomSort);
function randomSort(a:Object, b:Object):Number
{
return Math.random() - .5;
}

Untested code off the top of my head, but the concept is your sort function returns either a negative or positive number. By doing that randomly, it randomizes the array. No idea how fast it is though.

Anonymous said...

Came along this post... guess it does not work. If you use starter.length as the factor you multiply Math.random() by, then at the end there are not a lot options left. Big chance that you fill the finale array with items that DO exist...Btw, you don't seem to check for double items (this length thing is a issue... guess Keith is right with his approach)

Anonymous said...

no way, not the fastest. all you do is
function createRandomArray(num:int):Array{
var myArr:Array = new Array(num);
var i:int
for(i = 0; i < num; i++)
myArr[i] = i;
var ran:int;
var temp:int;
for(i = 0; i < num; i++){
ran = int(Math.random()*num);
temp = myArr[i];
myArr[i] = myArr[ran];
myArr[ran] = temp;
}
return myArr;
}

Braconnot Machado Family said...

It works!
Just some makeup needed for as2 in my case.

instead of: function createRandomArray(limit):Array {
place: function createRandomArray():Void {

instead of: starter = [];
place: var starter:Array = new Array();

instead of: finale = [];
place: var finale:Array = new Array();

the var limit should be the starter.length


instead of: var choose = Math.floor(Math.random()*starter.length);

place: var choose:Number = Math.floor(Math.random()*(starter.length));

VazdyK said...

But what do you think about this solution ?

int* genRand(int n){
int *tab=(int*)malloc(n*sizeof(int));
for(int i=0;i<n;i++)tab[i]=-1;
for(i=0;i<n;i++){
int k=rand()%n;
while(tab[k]!=-1){
k++;
if(k==n)k=0;
}
tab[k]=i;
}
return tab;
}

:)

 

template by blogger templates