Ce chapitre explique d'abord plusieurs façons de générer des nombres aléatoires Java, puis les démontre à travers des exemples.
Aperçu:
Direrez-vous ici, quelle est la difficulté de générer des nombres aléatoires? N'est-ce pas seulement pour utiliser Java encapsulé aléatoire? Bien sûr, c'est OK en général, et les algorithmes à expliquer dans cet article sont également basés sur cette fonction de bibliothèque aléatoire.
Cet article se concentre principalement sur le comportement de l'échantillonnage, et l'échantillonnage lui-même a une règle implicite qui ne consiste pas à avoir des données en double. OK, avec ces instructions. Vous pouvez d'abord essayer d'utiliser certaines de vos propres idées pour générer des nombres aléatoires sans génération répétée.
Tentatives d'algorithme:
Certains bons algorithmes apparaissent, souvent accompagnés de certains algorithmes pas si bons. Cependant, pour les algorithmes qui ne sont pas très efficaces, ils ont généralement une caractéristique commune, qui est facile à comprendre et à mettre en œuvre. Ce qui suit est une brève explication à travers une approche étape par étape.
Premier essai: algorithme aléatoire naïf
Cet algorithme est facile à comprendre, c'est aléatoire! Chaque fois qu'un nombre aléatoire est généré et ajouté à l'ensemble.
private void Simplerandom (int start, int fin, int count) {System.out.println ("algorithme aléatoire naturel:"); StringBuffer Buffer = new StringBuffer (); for (int i = 0; i <count; i ++) {int random = nombreutils.randominteger (start, end); Buffer.APPEND (i == 0? ("[" + Random): ("," + Random)); } buffer.append ("]"); System.out.println (tampon); } La deuxième tentative: vérifiez l'algorithme aléatoire existentiel
Nous savons qu'il y a un problème avec la méthode ci-dessus, c'est-à-dire qu'il peut y avoir des données en double. Nous avons donc pensé à vérifier si le nombre existe déjà lors de la génération d'un nombre aléatoire, et s'il existe, il sera régénéré.
private void checkrandom (int start, int end, int count) {System.out.println ("vérifier algorithme aléatoire existentiel:"); StringBuffer Buffer = new StringBuffer (); List <Integer> sauve = new ArrayList <> (); for (int i = 0; i <count; i ++) {int random = nombreutils.randominteger (start, end); if (quitte (sauver, aléatoire)) {i--; continuer; } sauve.add (aléatoire); Buffer.APPEND (i == 0? ("[" + Random): ("," + Random)); } buffer.append ("]"); System.out.println (tampon); } La troisième tentative: algorithme aléatoire de suppression des éléments
L'algorithme ci-dessus a résolu le problème de la duplication de données. Cependant, un très mauvais problème est qu'il peut nous prendre beaucoup de temps pour générer des échantillons de nombres aléatoires (cela dépend du visage ...).
Cependant, nous avons ici de nouvelles idées. C'est-à-dire d'utiliser au hasard un nombre dans un ensemble et de le supprimer lorsque celle-ci est sélectionnée. Ensuite, n'atteinrez-vous plus ce numéro au hasard lorsqu'il est aléatoire? Cela résout très bien le problème de la répétition des nombres aléatoires. Le code est le suivant:
Removerandom de void privé (int start, int fin, int count) {System.out.println ("Algorithme aléatoire de suppression d'éléments:"); StringBuffer Buffer = new StringBuffer (); List <Integer> nombres = initList (start, end); for (int i = 0; i <count; i ++) {int random = nombreutils.randominteger (count - i); buffer.append (i == 0? ("[" + nombres.get (aléatoire)): ("," + nombres.get (aléatoire))); nombres.Remove (aléatoire); } buffer.append ("]"); System.out.println (tampon); } Quatrième tentative: algorithme aléatoire de transfert d'état
Dans bon nombre de mes blogs précédents, certains sont des processus de transfert d'État dans les algorithmes. Le transfert d'état est également l'un de mes algorithmes préférés. La figure-1 ci-dessous marque la plage de valeur des nombres aléatoires, et le nombre orange dans la séquence est la séquence aléatoire du résultat. Il y a quelques flèches en pointillés dans la séquence inférieure, représentant la transition de l'état.
Algorithme de génération de nombres aléatoires de l'échantillonnage Figure-1 basé sur la transition d'état
Code d'implémentation:
private void statusrandom (int start, int end, int count) {System.out.println ("Algorithme aléatoire de transfert d'état:"); StringBuffer Buffer = new StringBuffer (); int [] status = new int [end + 1]; for (int i = 0; i <count; i ++) {int random = nombreutils.randominteger (start, end); System.err.println (aléatoire); if (status [random] == 0) {buffer.append (i == 0? ("[" + random): ("," + aléatoire)); Status [Random] = Random == end? Démarrer: (aléatoire + 1); // Il est impossible d'avoir un nombre avant de démarrer} else {// Status Transfer int index = Random; do {index = status [index]; } while (status [index]! = 0); buffer.append (i == 0? ("[" + index): ("," + index)); status [index] = index == end? Démarrer: (index + 1); // Il est impossible d'avoir un nombre avant de démarrer}} buffer.append ("]"); System.out.println (tampon); } La cinquième tentative: algorithme aléatoire de Floyd récursif
L'algorithme Floyd est finalement un processus de transfert d'état. L'algorithme nécessitera une liste ou un tableau pour stocker le numéro aléatoire déterminé. Comme son nom l'indique, j'utiliserai des solutions récursives ici. Dans le processus de récursivité, nous transférons l'état du numéro aléatoire du i-th au nombre aléatoire I-1. Le code est le suivant:
Liste privée <Integer> SimpleFloyd (list <Integer> list, int count, int start, int end) {if (count == 0) {return list; } list = SimpleFloyd (list, count - 1, start, end - 1); int random = NumberUtils.Randominteger (start, end); if (list.contains (random)) {list.add (end); } else {list.add (random); } Retour List; } Sixième tentative: itération sur l'algorithme aléatoire de Floyd
L'idée est similaire à l'algorithme aléatoire de Floyd récursif ci-dessus, mais nous ajoutons ici une variable à optimiser. Il n'est plus nécessaire de se reproduire. Le code est le suivant:
Liste privée <Integer> itérationfloyd (int start, int fin, int count) {System.out.println ("algorithme aléatoire itératif floyd:"); List <Integer> list = new ArrayList <> (); for (int i = end - count + 1; i <end; i ++) {int random = nombreutils.randominteger (start, i); if (list.contains (random)) {list.add (i); } else {list.add (random); }} Retour List; } Résultats des tests:
Figure-2 Résultats de test d'algorithme de génération de nombres aléatoires
Dans les résultats des tests ci-dessus, nous pouvons clairement voir que l'algorithme aléatoire naïf a non seulement des données en double, mais est également la plus longue. Par conséquent, évitez d'utiliser cet algorithme lors de la génération de nombres aléatoires échantillonnés. Parmi ces derniers algorithmes, l'algorithme aléatoire de transfert d'état est le meilleur, et l'algorithme aléatoire itératif de Floyd est deuxième. Cela peut être fait en fonction des préférences personnelles.