Choisir des nombres aléatoires efficacement

J'ai une méthode, qui utilise des échantillons aléatoires de se rapprocher d'un calcul. Cette méthode est appelée millions de fois, donc, il est très important que le processus de choix de nombres aléatoires est efficace.

Je ne suis pas sûr de savoir comment rapide javas Random().nextInt sont vraiment, mais mon programme ne semble pas bénéficier autant que je l'aime aussi.

Au moment de choisir le nombres aléatoires, je ne les suivants: (en semi pseudo-code):

//Repeat this 300000 times
Set set = new Set();
while(set.length != 5)
    set.add(randomNumber(MIN,MAX));

Maintenant, de toute évidence, cela a un mauvais cas les pires temps d'exécution, comme l'aléatoire-fonction dans la théorie peut ajouter dupliqué numéros pour une éternité, donc rester dans la boucle pour toujours. Toutefois, les numéros sont choisis à partir de {0..45}, un double de la valeur est, pour la plupart, peu probable.

Lorsque j'utilise la méthode ci-dessus, son seul 40% plus rapide que mon autre méthode, qui ne se rapproche pas, mais donne le résultat correct. C'est couru ~ 1 millions de fois, donc je m'attendais à cette nouvelle méthode à au moins 50% plus rapide.

Avez-vous des suggestions pour une méthode plus rapide? Ou peut-être vous connaissez un moyen plus efficace de génération d'un ensemble de nombres aléatoires.

Pour clarifier, voici deux méthodes:

//Run through all combinations (1 million). This takes 5 seconds
 for(int c1 = 0; c1 < deck.length; c1++){
    for(int c2 = c1+1; c2 < deck.length; c2++){
     for(int c3 = c2+1; c3 < deck.length; c3++){
        for(int c4 = c3+1; c4 < deck.length; c4++){
         for(int c5 = c4+1; c5 < deck.length; c5++){
             enumeration(hands, cards, deck, c1, c2, c3, c4, c5);
         }
            } 
      }     
   }
   }

//Approximate (300000 combinations). This takes 3 seconds
Random rand = new Random();
HashSet<Integer> set = new HashSet<Integer>();
int[] numbers = new int[5];
while(enumerations < 300000){
set.clear();
while(set.size() != 5){
    set.add(rand.nextInt(deck.length));
}
Iterator<Integer> i = set.iterator();
int n = 0;
while(i.hasNext()){
    numbers[n] = i.next();
    n++;
}

Après quelques tests et le profilage, j'ai trouvé que cette méthode soit la plus efficace:

Random rand = new Random();
int[] numbers = new int[5];
ArrayList<Integer> list = new ArrayList<Integer>();
while(enumerations < 300000){
 while(list.size() != 5) {
     int i = rand.nextInt(deck.length);
        if(!list.contains(i)) list.add(i);
 }
 int index = 0;
 for(int i : list){ numbers[index] = i; index++; }
 enumeration(hands, cards, deck,numbers);
}

source d'informationauteur

  1. 11

    Vous pouvez essayer d'utiliser un Java existantes de mise en œuvre (ou celui-ci) pour un le nombre de Mersenne Twister.

    Garder à l'esprit que la plupart MT sont pas cryptographique sécurisé.

  2. 5

    Il semble que vous voulez sélectionner un k-combinaison à partir d'un ensemble S sans remplacement, avec S avoir n valeurs distinctes, k = 5 et n = 52. Vous pouvez shuffle() l'ensemble et sélectionnez k éléments (comme @Tesserex l'indique), ou pick() k éléments tout en évitant les doublons (comme vous l'avez indiqué). Vous aurez envie de profil à la fois dans votre environnement et de votre générateur. J'ai souvent, mais pas toujours, voir une légère pointe pour pick().

    private static final Random rnd = new Random();
private static final int N = 52;
private static final int K = 5;
private static final List<Integer> S = new ArrayList<Integer>(N);
static {
    for (int i = 0; i < N; i++) {
        S.add(i + 1);
    }
}
private final List<Integer> combination = new ArrayList<Integer>(K);

...

private void shuffle() {
    Collections.shuffle(S, rnd);
    combination.addAll(S.subList(0, K));
}

private void pick() {
    for (int i = 0; i < K; i++) {
        int v = 0;
        do {
            v = rnd.nextInt(N) + 1;
        } while (combination.contains(v));
        combination.add(v);
    }
}
  3. 2

    Une technique courante est de commencer avec une liste de toutes les entrées possibles, et de choisir au hasard, la suppression de ceux que vous allez. De cette façon, il n'y a pas de risque de sélection d'un double et d'avoir à boucle pour un montant indéterminé de temps. Bien sûr, cette méthode ne fonctionne qu'avec des données discrètes, mais heureusement, les entiers sont. Rappelez-vous aussi que votre liste (ou d'autres structures de données) de sélection et de suppression doit être O(1) si cela est possible, puisque vous êtes en se concentrant sur la vitesse.

  4. 2

    Vous pouvez utiliser congruence linéaire comme un générateur aléatoire: http://en.wikipedia.org/wiki/Linear_congruential_generator [encore compte de leurs statistiques inconvénients]

    Vous avez seulement besoin d'un calcul de (x + c) % m pour chaque numéro. Pourtant, dans mon expérience, la création d'objets (comme on pourrait le faire avec chaque appel de nouveau et d'ajouter, selon l'application que vous utilisez) pourrait vous coûter plus de vitesse qu'un appel à la nextInt(). Vous devriez peut-être essayer un profiler comme par exemple celui-ci: http://www.eclipse.org/tptp/

  5. 1

    Je n'ai pas de commentaires sur votre réel problème, et je ne sais pas trop de Java (juste de fouiller). Cependant il me semble que vous êtes en train de construire une part de l'évaluateur pour le poker, et ce fil http://pokerai.org/pf3/viewtopic.php?f=3&t=16 contient certains extrêmement rapide java de la part des évaluateurs. J'espère que certains de ce code pourrait être de l'aide.

  6. 1

    Si vous êtes d'être ralenti par le fait que vous avez à sauter par-dessus les doublons, vous pouvez résoudre ce problème en créant une liste de toutes les valeurs de carte, puis de la retirer de la liste à mesure que les cartes sont sélectionnés et choisir un nombre aléatoire dans un intervalle plus petit la prochaine fois. Quelque chose comme ceci:

    //Assuming we're just numbering all the cards 0 to 51. This could be more sophisticated, of course.
ArrayList cards=new ArrayList(52);
for (int x=0;x<52;++x)
  cards=new Integer(x);

Integer[] hand=new Integer[5];
for (int h=0;h<5;++h)
{
  //Pick a card from those remaining
  int n=random.nextInt(cards.size());
  hand[h]=cards.get(n);
  //Remove the picked card from the list
  cards.remove(n);
}

    Pour le premier tirage, les cartes.get(n) sera de retour n, peu importe ce n est. Mais à partir de là, les valeurs seront supprimés si les cartes.get(3) peut-retour 7, etc.

    De la création de la liste et de les retirer de la il ajoute un tas de frais généraux. J'imagine que si vous êtes seulement à la cueillette de 5 cartes à la fois, la probabilty de la collision est assez petit pour que l'élimination des duplices après que vous les trouvez, serait plus rapide que de les prévenir. Même sur le dernier tirage, la probabilité d'un duplicata est à seulement 4 contre 52=1/13, donc, si vous voulez rarement frappé un double et la probabilité que 2 dessine une ligne à la fois être des doublons serait minuscule. Tout dépend de combien de temps il faut pour générer un nombre aléatoire par rapport à combien de temps il faut pour configurer le tableau et ne le supprime. La meilleure façon de faire serait de faire quelques expériences et à mesure. (Ou de profil!)

  7. 0

    Jamais deviner, toujours mesure.

     long time = System.getCurrentMilliseconds();
 Random().nextInt()
 System.out.println(System.getCurrentMilliseconds() - time);

    Aussi, vous ne devez jamais compter sur la rareté d'un bug connu qui va se passer, juste le code defensivley de sorte qu'il n'est pas. Détecter un duplicata, et si c'est un doublon alors ne pas l'ajouter, puis passez à l'itération avec un continue déclaration.

    Comme pour la plus rapide des méthodes et des nombres aléatoires...
    Vous ne pouvez pas obtenir des nombres aléatoires de Java Math.random(). Vous ne pouvez obtenir des pseudo-aléatoire de nombres. À quelle vitesse vous voulez que ce soit arrive à le sacrifice de façon apparemment aléatoire, vous devez apparaître. Le moyen le plus rapide pour générer un nombre pseudo-aléatoire impliquerait le décalage de bits et plus en fonction de la valeur de départ comme System.getCurrentMilliSeconds() Aussi, pseudo-génération de nombres aléatoires est déjà assez rapide puisque c'est juste cru PROCESSEUR arithmétique de toute façon, vous aurez probablement être heureux une fois que vous voyez combien de millisecondes qu'il faut pour générer une avec Math.random().

  8. 0

    Ne pas essayer de développer votre connu aléatoire num générateur. Utiliser un connu comme SecureRandom à la place:

    http://www.owasp.org/index.php/Using_the_Java_Cryptographic_Extensions