lundi 26 janvier 2015

Performant way to select N random distinct ints in java?

I currently am looking for the best way so select x unique ints among a range of n ints. It would be like doing Random.nextInt(range) multiple time except it should never select twice the same int. If it happens that x > n then the result would only contain n ints


I tried to do this myself and I currently have done this based on the Fisher/Yates shuffle:



private static final Random R = new Random();

public static int[] distinctRandoms(int nb, int max) {
int[] all = new int[max];
for (int i = 0; i < all.length; i++) {
all[i] = i;
}
if (max <= nb) {
return all;
}
int index;
int[] result = new int[nb];

for (int j = 0, k = all.length - 1; k > 0 && j < nb; k--, j++) {
index = R.nextInt(k + 1);
result[j] = all[index]; // save element
all[index] = all[k]; // overwrite chosen with last element
}
return result;
}


It works and performance seems good but I can't help thinking there must still be some more performant way to do so and that i'm reinventing the wheel. I thought about doing things differently if nb > (max / 2) (remove elements rather than select elements) but as you can't truncate an array in java you still end up copying all the elements you need. This method costs alot if nb = max-1


Is there any built in way to randomly select distinct ints efficiently in java ?





Aucun commentaire:

Enregistrer un commentaire