Tirage au sort SANS redondance !

Tirer au sort une liste de possibilité c’est bien, le faire de façon optimale c’est mieux !

Tout le monde connait (ou va connaitre dans 3 lignes) la façon de tirer au sort un nombre :


Random random = new Random();
random.nextInt(10); //chiffre entre 0 et 10
    

Voila c’est fait !

Le Mode Basique

Maintenant imaginons que l’on ai 10 joueurs et que l’on veuille tirer au sort l’ordre de passage, de manière “simple” sans architecture cela donne :


public static void pickWithRedundancy(int min, int max) {
    Random random = new Random();
    List<integer> result = new ArrayList<integer>();
    for (int i = 0; i < (max - min + 1); i++) {
        int tmp = 0;
        do {
            tmp = random.nextInt(max - min + 1) + min;
        } while (result.contains(tmp));
        out.println(tmp + "");
        result.add(tmp);
    }
}

On a donc une fonction qui reçois les min & max, par exemple pour 10 jours entre 0 et 9, mais aussi 46 et 55 etc……

Le principe est simple : on tire au sort un chiffre dans l’interval voulu, et on vérifie si il a déjà été tiré ou non (via la liste result qui contient tous les résultats déjà obtenu). Cependant on peut remarquer 3 choses dans ce code :

  • C’est assez long
  • C’est assez peu compréhensible
  • C’est non optimisé

Pour les deux premiers points, un code rapide est assez souvent un code trop long et peu compréhensible, mais c’est rapide donc c’est une bonne excuse …

Pourquoi non optimisé, car avec 10 possibilités de tirage,le nombre de relance du chiffre aléatoire est faible si celui ci est déjà tiré, maintenant si on utilse 100 ou 1000 possibilités, le temps de tirage sera de plus en plus long !

C’est pourquoi on peut faire une classe tirage que l’on pourra aussi bien mettre dans sa bibliothèque de classe perso pour l’utiliser quand on en a besoin.

La Classe Pick

Qu’avons nous besoin ?

  • Une liste de possibilité
  • Un max et un min en initialisation
  • Une fonction qui retourne si il reste des nombres a tiré
  • Une fonction qui renvoi le chiffre choisi aléatoirement

Initialiser sa classe :


public Pick (int min, int max) {
    int i = min;
    while(i <= max) {
        numbers.add(i);
        i++;
    }
    Collections.shuffle(numbers);
}

Avec le min et le max on rempli la liste numbers de type ArrayList<Integer>, dans ce cas j’utilise un while, un for fera aussi bien l’affaire !
Collections.shuffle sert à mélanger la liste, donc on n’utilisera plus Random, car la liste étant déjà dans un ordre aléatoire

La fonction isFinish


public boolean isFinish() {
    if (numbers.size() > 0)
        return false;
    else
        return true;
}

Ou de manière raccourcie :


public boolean isFinish() {
    return (numbers.size() > 0) ? false : true;
}

La fonction Random :


public int getRandom() {
    int retour = -1;
    if (numbers.size() > 0) {
        retour = numbers.get(0);
        numbers.remove(0);
    }
    return retour;
}

La liste ayant déja été mélangée, il nous reste deux choses à faire :

  • Enlever le numéro de la liste
  • Le renvoyer

A noter que l’on peut utiliser !isFinish() au lieu de numbers.size() > 0, on utilse la variable retour pour pouvoir stocker le numéro avant de le retirer de la liste.

Les Résultats !

Histoire de ne pas dire c’est mieux et c’est tout, voici les chiffres des test menés :

Le Draw 1 correspond à la manière brute, le 2 à celui dit joli 😀 , les résultats sont la moyenne de 3 tests à la suite et non un coup de chance ….

Avec 10 chiffres:


Draw N°1 : <1 ms
Draw N°2 : 2 ms

Avec 100:


Draw N°1 : 3 ms
Draw N°2 : 2 ms

Avec 1000:


Draw N°1 : 24 ms
Draw N°2 : 5 ms

Avec 10000 !


Draw N°1 : 1497 ms
Draw N°2 : 31 ms

Donc on remarque clairement une bonne efficacité, imaginé avec des chiffres énoooooooooormes genre le million, plus besoin d’imaginé j’avais envie de savoir aussi 😀

Draw N°1 : 20255781 ms soit plus de 5h30
Draw N°2 : 163447 ms soit moins de 3mn

Le plus long étant de trouver les derniers numéro, donc on peut estimer que sur les test avant 5 000 possibilités le temps de réponse est encore assez rapides, après on le vois bien le temps de réponse deviens un handicap pour le programme ! Ah justement le test du million vient de se finir …. enfin !

A noter que pour ce test du million, les derniers chiffres sont les pires : les chances de trouver le chiffre du premier coup est super faible !
Pour le dernier chiffre cette chance est de 1 sur 1 000 000 …. soit 0,0001% de chance ^^
Idem un pc plus puissant testera plus de possibilité qu’un pc faible dans le même temps, les test ont ici été effectués sur un ultrabook ThinkPad yoga 14 (i5, 8go ram, SSD).
IMPORTANT : toujours tester ses logiciels sur une machine moins puissante, afin que les utilisateurs ayant des pc faibles ne soit pas génés dans leurs utilisations de votre logiciel.

Code disponible sur GITHUB !


22. décembre 2017 Développement 0