Choisir un élément aléatoire d'un ensemble
https://stackoverflow.com/questions/124671
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment choisir un élément aléatoire dans un ensemble? Je suis particulièrement intéressé par la sélection d'un élément aléatoire d'un HashSet ou un LinkedHashSet, en Java. Des solutions pour d'autres langues sont également les bienvenues.
La solution
int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
if (i == item)
return obj;
i++;
}
Autres conseils
Un peu en relation Le saviez-vous:
Il existe des méthodes utiles dans java.util.Collections pour mélanger des collections entières: Collections.shuffle(List<?>) et Collections.shuffle(List<?> list, Random rnd) .
Solution rapide pour Java utilisant un ArrayList et un HashMap: [element - > index].
Motivation: j'avais besoin d'un ensemble d'éléments avec des propriétés RandomAccess, notamment pour sélectionner un élément au hasard dans l'ensemble (voir la méthode pollRandom). La navigation aléatoire dans un arbre binaire n’est pas précise: les arbres ne sont pas parfaitement équilibrés, ce qui ne conduirait pas à une distribution uniforme.
public class RandomSet<E> extends AbstractSet<E> {
List<E> dta = new ArrayList<E>();
Map<E, Integer> idx = new HashMap<E, Integer>();
public RandomSet() {
}
public RandomSet(Collection<E> items) {
for (E item : items) {
idx.put(item, dta.size());
dta.add(item);
}
}
@Override
public boolean add(E item) {
if (idx.containsKey(item)) {
return false;
}
idx.put(item, dta.size());
dta.add(item);
return true;
}
/**
* Override element at position <code>id</code> with last element.
* @param id
*/
public E removeAt(int id) {
if (id >= dta.size()) {
return null;
}
E res = dta.get(id);
idx.remove(res);
E last = dta.remove(dta.size() - 1);
// skip filling the hole if last is removed
if (id < dta.size()) {
idx.put(last, id);
dta.set(id, last);
}
return res;
}
@Override
public boolean remove(Object item) {
@SuppressWarnings(value = "element-type-mismatch")
Integer id = idx.get(item);
if (id == null) {
return false;
}
removeAt(id);
return true;
}
public E get(int i) {
return dta.get(i);
}
public E pollRandom(Random rnd) {
if (dta.isEmpty()) {
return null;
}
int id = rnd.nextInt(dta.size());
return removeAt(id);
}
@Override
public int size() {
return dta.size();
}
@Override
public Iterator<E> iterator() {
return dta.iterator();
}
}
Ceci est plus rapide que la boucle for-each dans la réponse acceptée:
int index = rand.nextInt(set.size());
Iterator<Object> iter = set.iterator();
for (int i = 0; i < index; i++) {
iter.next();
}
return iter.next();
La construction for-each appelle Iterator.hasNext() à chaque boucle, mais depuis index < set.size(), cette vérification est une surcharge inutile. J'ai vu une augmentation de 10-20% de la vitesse, mais YMMV. (En outre, cela compile sans avoir à ajouter une instruction de retour supplémentaire.)
Notez que ce code (et la plupart des autres réponses) peut être appliqué à n’importe quelle collection, pas seulement à Set. Sous forme de méthode générique:
public static <E> E choice(Collection<? extends E> coll, Random rand) {
if (coll.size() == 0) {
return null; // or throw IAE, if you prefer
}
int index = rand.nextInt(coll.size());
if (coll instanceof List) { // optimization
return ((List<? extends E>) coll).get(index);
} else {
Iterator<? extends E> iter = coll.iterator();
for (int i = 0; i < index; i++) {
iter.next();
}
return iter.next();
}
}
Si vous souhaitez le faire en Java, vous devez envisager de copier les éléments dans une sorte de collection à accès aléatoire (telle qu'une liste de tableaux). Parce que, à moins que votre ensemble ne soit petit, accéder à l'élément sélectionné sera coûteux (O (n) au lieu de O (1)). [ed: la copie de la liste est aussi O (n)]
Vous pouvez également rechercher une autre implémentation de Set qui correspond mieux à vos besoins. Le ListOrderedSet dans Commons Collections semble prometteur.
En Java:
Set<Integer> set = new LinkedHashSet<Integer>(3);
set.add(1);
set.add(2);
set.add(3);
Random rand = new Random(System.currentTimeMillis());
int[] setArray = (int[]) set.toArray();
for (int i = 0; i < 10; ++i) {
System.out.println(setArray[rand.nextInt(set.size())]);
}
List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);
Solution Clojure:
(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))
Perl 5
@hash_keys = (keys %hash);
$rand = int(rand(@hash_keys));
print $hash{$hash_keys[$rand]};
Voici une façon de le faire.
C ++. Cela devrait être assez rapide, car cela ne nécessite pas d'itérer sur l'ensemble, ni de le trier. Cela devrait fonctionner immédiatement avec la plupart des compilateurs modernes, en supposant qu'ils prennent en charge tr1 . . Sinon, vous devrez peut-être utiliser Boost.
Les de la documentation Boost sont utiles. ici pour expliquer cela, même si vous n'utilisez pas Boost.
Le truc consiste à exploiter le fait que les données ont été divisées en compartiments et à identifier rapidement un compartiment choisi au hasard (avec la probabilité appropriée).
//#include <boost/unordered_set.hpp>
//using namespace boost;
#include <tr1/unordered_set>
using namespace std::tr1;
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;
int main() {
unordered_set<int> u;
u.max_load_factor(40);
for (int i=0; i<40; i++) {
u.insert(i);
cout << ' ' << i;
}
cout << endl;
cout << "Number of buckets: " << u.bucket_count() << endl;
for(size_t b=0; b<u.bucket_count(); b++)
cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl;
for(size_t i=0; i<20; i++) {
size_t x = rand() % u.size();
cout << "we'll quickly get the " << x << "th item in the unordered set. ";
size_t b;
for(b=0; b<u.bucket_count(); b++) {
if(x < u.bucket_size(b)) {
break;
} else
x -= u.bucket_size(b);
}
cout << "it'll be in the " << b << "th bucket at offset " << x << ". ";
unordered_set<int>::const_local_iterator l = u.begin(b);
while(x>0) {
l++;
assert(l!=u.end(b));
x--;
}
cout << "random item is " << *l << ". ";
cout << endl;
}
}
La solution ci-dessus parle en termes de latence mais ne garantit pas une probabilité égale de sélection de chaque index.
Si cela doit être pris en compte, essayez un échantillonnage de réservoir. http://fr.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle ( ) (comme suggéré par quelques-uns) utilise un tel algorithme.
Puisque vous avez dit & "Des solutions pour d'autres langues sont également les bienvenues &"; voici la version pour Python:
>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4
Ne pouvez-vous pas simplement obtenir la taille / longueur de l'ensemble / du tableau, générer un nombre aléatoire compris entre 0 et la taille / longueur, puis appeler l'élément dont l'index correspond? HashSet a une méthode .size (), je suis presque sûr.
En psuedocode -
function randFromSet(target){
var targetLength:uint = target.length()
var randomIndex:uint = random(0,targetLength);
return target[randomIndex];
}
PHP, en supposant " set " est un tableau:
$foo = array("alpha", "bravo", "charlie");
$index = array_rand($foo);
$val = $foo[$index];
Les fonctions Mersenne Twister sont meilleures mais il n’existe pas d’équivalent MT de array_rand en PHP.
L'icône a un type de jeu et un opérateur d'élément aléatoire, unary < !> quot;? " ;, donc l'expression
? set( [1, 2, 3, 4, 5] )
produira un nombre aléatoire compris entre 1 et 5.
La graine aléatoire est initialisée à 0 lors de l'exécution d'un programme. Par conséquent, pour obtenir des résultats différents à chaque exécution, utilisez randomize()
En C #
Random random = new Random((int)DateTime.Now.Ticks);
OrderedDictionary od = new OrderedDictionary();
od.Add("abc", 1);
od.Add("def", 2);
od.Add("ghi", 3);
od.Add("jkl", 4);
int randomIndex = random.Next(od.Count);
Console.WriteLine(od[randomIndex]);
// Can access via index or key value:
Console.WriteLine(od[1]);
Console.WriteLine(od["def"]);
solution Javascript;)
function choose (set) {
return set[Math.floor(Math.random() * set.length)];
}
var set = [1, 2, 3, 4], rand = choose (set);
Ou alternativement:
Array.prototype.choose = function () {
return this[Math.floor(Math.random() * this.length)];
};
[1, 2, 3, 4].choose();
En lisp
(defun pick-random (set)
(nth (random (length set)) set))
Dans Mathematica:
a = {1, 2, 3, 4, 5}
a[[ ⌈ Length[a] Random[] ⌉ ]]
Ou, dans les versions récentes, simplement:
RandomChoice[a]
Cela a suscité un vote négatif, peut-être parce qu'il manque d'explication. En voici un:
Random[] génère un flottant pseudo-aléatoire compris entre 0 et 1. Celui-ci est multiplié par la longueur de la liste, puis la fonction de plafond est utilisée pour arrondir au nombre entier le plus proche. Cet index est ensuite extrait de a.
La fonctionnalité de table de hachage étant fréquemment utilisée avec des règles dans Mathematica, et les règles étant stockées dans des listes, vous pouvez utiliser:
a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};
Que diriez-vous de juste
public static <A> A getRandomElement(Collection<A> c, Random r) {
return new ArrayList<A>(c).get(r.nextInt(c.size()));
}
Ceci est identique à la réponse acceptée (Khoth), mais en supprimant les variables inutiles size et i.
int random = new Random().nextInt(myhashSet.size());
for(Object obj : myhashSet) {
if (random-- == 0) {
return obj;
}
}
Bien que l’on supprime les deux variables susmentionnées, la solution ci-dessus reste aléatoire, car nous nous basons sur l’aléatoire (en partant d’un index choisi aléatoirement) pour se décrémenter vers 0 à chaque itération.
Malheureusement, cela ne peut pas être fait efficacement (mieux que O (n)) dans les conteneurs d'ensembles de bibliothèques standard.
Cela est étrange, car il est très facile d’ajouter une fonction de sélection aléatoire aux ensembles de hachage ainsi qu’aux ensembles binaires. Dans un ensemble de hachage peu dense, vous pouvez essayer des entrées aléatoires jusqu'à ce que vous obteniez un hit. Pour une arborescence binaire, vous pouvez choisir de manière aléatoire entre la sous-arborescence gauche ou droite, avec un maximum de 0 étapes (log2). J'ai mis en place une démo de ce qui suit:
import random
class Node:
def __init__(self, object):
self.object = object
self.value = hash(object)
self.size = 1
self.a = self.b = None
class RandomSet:
def __init__(self):
self.top = None
def add(self, object):
""" Add any hashable object to the set.
Notice: In this simple implementation you shouldn't add two
identical items. """
new = Node(object)
if not self.top: self.top = new
else: self._recursiveAdd(self.top, new)
def _recursiveAdd(self, top, new):
top.size += 1
if new.value < top.value:
if not top.a: top.a = new
else: self._recursiveAdd(top.a, new)
else:
if not top.b: top.b = new
else: self._recursiveAdd(top.b, new)
def pickRandom(self):
""" Pick a random item in O(log2) time.
Does a maximum of O(log2) calls to random as well. """
return self._recursivePickRandom(self.top)
def _recursivePickRandom(self, top):
r = random.randrange(top.size)
if r == 0: return top.object
elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a)
return self._recursivePickRandom(top.b)
if __name__ == '__main__':
s = RandomSet()
for i in [5,3,7,1,4,6,9,2,8,0]:
s.add(i)
dists = [0]*10
for i in xrange(10000):
dists[s.pickRandom()] += 1
print dists
J'ai reçu [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] en sortie, donc la répartition semble bonne.
J'ai moi-même eu le même problème avec le même problème, et je n'ai pas encore décidé que le gain de performances obtenu par ce choix plus efficace valait la charge supplémentaire liée à l'utilisation d'une collection basée sur Python. Je pourrais bien sûr l’affiner et le traduire en C, mais c’est trop de travail pour moi aujourd’hui:)
En Java 8:
static <E> E getRandomSetElement(Set<E> set) {
return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}
PHP, en utilisant MT:
$items_array = array("alpha", "bravo", "charlie");
$last_pos = count($items_array) - 1;
$random_pos = mt_rand(0, $last_pos);
$random_item = $items_array[$random_pos];
Pour le plaisir, j’ai écrit un RandomHashSet basé sur l’échantillonnage de rejet. C'est un peu hacky, car HashMap ne nous permet pas d'accéder directement à sa table, mais cela devrait fonctionner correctement.
Il n’utilise pas de mémoire supplémentaire et le temps de recherche est amorti à O (1). (Parce que java HashTable est dense).
class RandomHashSet<V> extends AbstractSet<V> {
private Map<Object,V> map = new HashMap<>();
public boolean add(V v) {
return map.put(new WrapKey<V>(v),v) == null;
}
@Override
public Iterator<V> iterator() {
return new Iterator<V>() {
RandKey key = new RandKey();
@Override public boolean hasNext() {
return true;
}
@Override public V next() {
while (true) {
key.next();
V v = map.get(key);
if (v != null)
return v;
}
}
@Override public void remove() {
throw new NotImplementedException();
}
};
}
@Override
public int size() {
return map.size();
}
static class WrapKey<V> {
private V v;
WrapKey(V v) {
this.v = v;
}
@Override public int hashCode() {
return v.hashCode();
}
@Override public boolean equals(Object o) {
if (o instanceof RandKey)
return true;
return v.equals(o);
}
}
static class RandKey {
private Random rand = new Random();
int key = rand.nextInt();
public void next() {
key = rand.nextInt();
}
@Override public int hashCode() {
return key;
}
@Override public boolean equals(Object o) {
return true;
}
}
}
vous pouvez également transférer l'ensemble à array use array cela fonctionnera probablement à petite échelle. Je vois que la boucle for dans la réponse la plus votée est de toute façon O (n)
Object[] arr = set.toArray();
int v = (int) arr[rnd.nextInt(arr.length)];
Si vous voulez vraiment choisir & "n'importe quel &"; objet du Set, sans aucune garantie sur le caractère aléatoire, le plus simple consiste à prendre le premier renvoyé par l'itérateur.
Set<Integer> s = ...
Iterator<Integer> it = s.iterator();
if(it.hasNext()){
Integer i = it.next();
// i is a "random" object from set
}
Le plus simple avec Java 8 est:
outbound.stream().skip(n % outbound.size()).findFirst().get()
où n est un entier aléatoire. Bien sûr, il est moins performant que celui du for(elem: Col)
Une solution générique utilisant la réponse de Khoth comme point de départ.
/**
* @param set a Set in which to look for a random element
* @param <T> generic type of the Set elements
* @return a random element in the Set or null if the set is empty
*/
public <T> T randomElement(Set<T> set) {
int size = set.size();
int item = random.nextInt(size);
int i = 0;
for (T obj : set) {
if (i == item) {
return obj;
}
i++;
}
return null;
}
Si la taille définie n'est pas grande, vous pouvez le faire en utilisant des tableaux.
int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];
