Je parle à une API qui me donne un Maintenant à mon problème: je veux obtenir un élément aléatoire de cette collection. Comment je fais ça? Je suppose que je pourrais construire une nouvelle collection qui permet un accès direct, mais n'est-ce pas si un peu de mémoire consommant? Je pourrais aussi itérer sur toute la collection et pour chaque élément "rouler un dés" pour voir si je devais prendre cet élément et quitter l'itération ou continuer. Mais alors j'ai besoin de la taille de la collection et je ne peux pas l'obtenir de l'itérateur.
Merci d'avance. java.util.iterator sur une collection. Cela signifie que je peux y attérer dessus, mais je ne peux pas obtenir d'accès direct / aléatoire aux éléments.
6 Réponses :
Lorsque l'itération, vous savez combien d'objets que vous avez itératés, vous connaissez donc la probabilité que l'élément actuel soit celui qui sélectionne au hasard. Donc, il vous suffit de garder le compte d'un compte et de l'élément sélectionné de manière aléatoire actuel.
public static <T> T selectRandom(final Iterator<T> iter, final Random random) {
if (!iter.hasNext()) {
throw new IllegalArgumentException();
}
if (random == null) {
throw new NullPointerException();
}
T selected = iter.next();
int count = 1;
while (iter.hasNext()) {
final T current = iter.next();
++count;
if (random.nextInt(count) == 0) {
selected = current;
}
}
return selected;
}
Je ne sais pas comment cela est aléatoire: avec chaque itération, probabilité que aléatoire.nextint (comptage) == 0 est inférieur et inférieur.
Lorsque je passe dans une liste avec un article, il y a une itération. Nombre Obtient la valeur 2 . Dans la moitié des cas, null sera renvoyé pour une liste avec un élément, non? Donc c'est faux.
@Tulkly Oui, lorsque vous devez dire, le dixième élément, alors il a la probabilité d'être sélectionné comme 1/10.
@Thejh Le premier élément est un cas particulier dans le code. (Cela pourrait être fait dans la boucle, mais ce serait le code icky.)
@Malwasser vous voudrez peut-être y penser plus. Pour chaque élément suivant, il est probable que l'élément sélectionné précédent soit déplacé. Sort comme juste.
@Tom tu as raison - j'ai commis une erreur lors de la compréhension de votre code. Merci d'avoir souligné cela. +1
Est-il possible d'exprimer la preuve mathématiquement? Je ne peux toujours pas comprendre pourquoi c'est juste, désolé. Solution très élégante cependant, si elle est prouvée, je vais vous louera :).
@Voho C'est effectivement la même chose que la réponse acceptée [ultérieure]. Preuve que le contour de l'article Wikipedia lié, simplifié uniquement parce que vous n'avez pas besoin d'une étape pour la probabilité que le dernier nombre aléatoire soit le plus extrême.
Ok, merci pour le conseil, je vais regarder ça. C'est un peu confus, car un ensemble n'a pas de démarrage ni de dernier élément.
La seule solution sûre (au cas où aucune autre information n'est connue / garantie) est la façon dont vous avez décrit:
Créez une liste Si la taille de la collection sous-jacente est toujours la même, vous pouvez réduire l'effort de moitié en moyenne - utilisez simplement l'élément que vous avez reçu après itérator.next () après un nombre aléatoire d'itérations.
à partir du itérateur et choisissez un élément aléatoire.
java.util.itéator ?
Cela dépend des exigences, si la taille de la collection n'est pas énorme, cela le fera, sinon vous devez itérer et utiliser la méthode des dés que vous avez mentionnée
List<Object> list = Arrays.asList(yourCollection.toArray(new Object[0])); result = list.get(new Random().nextInt(list.size()));
Il y a un moyen de le faire sur un passage à travers la collection qui n'utilise pas beaucoup de mémoire supplémentaire (juste la taille d'un élément de la collection plus un flotteur). En pseudocode:
Évidemment, cela a l'inconvénient d'itération à travers toute la collection chaque fois que vous l'appelez, mais vous n'avez pas beaucoup de choix avec les contraintes que vous faites face.
Mise à jour: Le nom de ce type de problème est finalement revenu à moi. C'est ce qu'on appelle échantillonnage du réservoir .
À peu près la même chose que ma solution (autre que je n'utilise pas de flotteurs (BTW, INTS ferait mieux))).
@Tom: Cela ressemble à peu près à la même idée de base. Pourquoi int est-il meilleur?
@Bill Le lézard AT vous donnerait une plus grande propagation de valeurs pour un nombre donné. Ne pas avoir à traiter avec tout ce que IEEE GUFF.
@Tom: Oh, ça. Je m'attendais à des trivia arcaniques sur aléatoire que je ne savais pas encore. :)
J'ai peut-être eu mes mathématiques, mais je pense que cela ne choisira pas uniformément sur la liste. Pour le prouver, réfléchissez à la manière dont cela fonctionnera pour 3 articles. Le premier élément est sélectionné avec une probabilité de 100%. Le deuxième article est sélectionné avec une probabilité de 50% (jusqu'à présent si bonne), mais le troisième élément ne sera sélectionné qu'avec une probabilité de 25%, pas une probabilité de 1/3, comme cela devrait être.
@Dean: le troisième nombre aléatoire d'un RNG a une chance de 1/3 d'être le plus bas. Chaque nombre a une probabilité égale d'être le plus bas (ou le plus élevé), cela fonctionnera donc peu importe la taille de la collection.
@Dean Povey Regardez-le de cette façon: avant de regarder la séquence générer les nombres aléatoires. Le plus haut survient toujours à une position uniformément aléatoire.
Je pense que vous avez la fois tort. Pour deux articles aléatoires, il y a 50% de chances que l'on soit plus élevé que l'autre. Pour deux articles, cela fonctionne, mais pour le troisième élément, il doit être supérieur à celui de les autres articles, à savoir. Vous devez associer les probabilités, il n'a donc que 25% de chances d'être plus élevé que les deux premiers chiffres.
@Dean: Vous n'avez pas à multiplier les probabilités. Ce n'est pas des coups de monnaie, c'est une distribution uniforme de valeurs. Chacun d'entre eux a une chance de 1 / N d'être le plus élevé.
Et plus loin, je voulais dire plus bas :-) (ou plus, comme votre réponse suggère)
@Dean Povey: "Pour deux articles aléatoires, il y a 50% de chances que l'on soit plus élevé" est faux. "Près de 50%" serait correct. Ils pourraient être égaux, non? ;)
@Bill, d'accord, pardonnez-moi d'être n00b. Je comptais juste les permutations correctement et réalisa que vous avez raison. Il existe deux traitements sur 6 que le 3ème nombre peut être supérieur aux deux autres.
@Bill Le lézard merci, c'est exactement la solution que je ne pouvais pas envelopper ma tête autour de moi-même.
Si vous lisez la page Wikipedia liée à partir de la réponse, vous verrez que vous devez réduire la probabilité de chaque réponse étant celle sélectionnée comme vous iTerez. Sinon, vous créez un biais vers la fin de l'ordre d'itération.
Si vous n'avez vraiment pas d'accès aléatoire, vous avez une liste très volumineuse afin que vous ne puissiez pas la copier, vous pouvez effectuer ce qui suit:
int n = 2
iterator i = ...
Random rand = new Random();
Object candidate = i.next();
while (i.hasNext()) {
if (rand.nextInt(n)) {
candidate = i.next();
} else {
i.next();
}
n++;
}
return candidate;
Tant la même chose que ma solution.
Oui. Vous l'avez ajouté pendant que je tapais :-).
Utilisez ceci pour générer des données de test pondérées. Ce n'est pas efficace mais est facile Remarque: les paramètres de probabilité seront relatifs au total non à 1,0 p> Utilisation: P> public static void main(String[] args) {
ProbabilitySet<String> stati = new ProbabilitySet<String>();
stati.add("TIMEOUT", 0.2);
stati.add("FAILED", 0.2);
stati.add("SUCCESSFUL", 1.0);
for (int i = 0; i < 100; i++) {
System.out.println(stati.getRandomElement());
}
}
La collection ne devrait normalement pas être la classe qui implémente
itérateur .Votre collection est-elle un
java.util.collection ?La consommation de mémoire ne devrait pas être tout ce qui est grand. La nouvelle collection contient simplement des pointeurs vers les données réelles, de sorte que la taille du nouvel objet de collection! = La taille de la collection.
@Jonathan B Dans les cas pathologiques La collection contient de nombreux éléments en double ou
null S, qui pourrait faire une arraylistede la collection relativement grande.@Thejh c'est mon écriture maladroite, merci de l'avoir mentionné. J'ai mis à jour la question.