Ein zufälliges Element aus einer Menge auswählen
Wie wähle ich ein zufälliges Element aus einer Menge aus? Ich bin besonders daran interessiert, ein zufälliges Element aus einem HashSet oder einem LinkedHashSet in Java auszuwählen. Lösungen für andere Sprachen sind ebenfalls willkommen.
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++;
}
Ein etwas verwandter Wussten Sie, dass:
Es gibt nützliche Methoden in Java.util.Collections zum Mischen ganzer Sammlungen: Collections.shuffle(List<?>) und Collections.shuffle(List<?> list, Random rnd) .
Schnelle Lösung für Java mit einem ArrayList und einem HashMap: [element -> index].
Motivation: Ich brauchte eine Reihe von Elementen mit RandomAccess -Eigenschaften, insbesondere um ein zufälliges Element aus der Reihe auszuwählen (siehe pollRandom -Methode). Die zufällige Navigation in einem Binärbaum ist nicht genau: Bäume sind nicht perfekt ausbalanciert, was nicht zu einer gleichmäßigen Verteilung führen würde.
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();
}
}
Dies ist schneller als die For-Each-Schleife in der akzeptierten Antwort:
int index = Rand.nextInt(set.size());
Iterator<Object> iter = set.iterator();
for (int i = 0; i < index; i++) {
iter.next();
}
return iter.next();
Das for-each-Konstrukt ruft Iterator.hasNext() in jeder Schleife auf, aber seit index < set.size() ist diese Prüfung nicht mehr erforderlich. Ich habe einen Geschwindigkeitszuwachs von 10-20% gesehen, aber YMMV. (Dies wird auch kompiliert, ohne dass eine zusätzliche return-Anweisung hinzugefügt werden muss.)
Beachten Sie, dass dieser Code (und die meisten anderen Antworten) auf jede Sammlung angewendet werden können, nicht nur auf Set. In generischer Methodenform:
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();
}
}
Wenn Sie dies in Java tun möchten, sollten Sie erwägen, die Elemente in eine Auflistung mit wahlfreiem Zugriff (z. B. eine ArrayList) zu kopieren. Denn solange Ihre Menge nicht klein ist, ist der Zugriff auf das ausgewählte Element teuer (O (n) anstelle von O (1)). [ed: Listenkopie ist auch O (n)]
Alternativ können Sie nach einer anderen Set-Implementierung suchen, die Ihren Anforderungen besser entspricht. Das ListOrderedSet von Commons Collections sieht vielversprechend aus.
In 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);
Clojure-Lösung:
(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]};
Hier ist eine Möglichkeit, dies zu tun.
Die obige Lösung bezieht sich auf die Latenz, garantiert jedoch nicht die gleiche Wahrscheinlichkeit, dass jeder Index ausgewählt wird.
Wenn dies berücksichtigt werden muss, probieren Sie die Probenahme aus dem Reservoir. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (wie von wenigen vorgeschlagen) verwendet einen solchen Algorithmus.
C++. Dies sollte relativ schnell gehen, da es nicht erforderlich ist, den gesamten Satz zu iterieren oder zu sortieren. Dies sollte bei den meisten modernen Compilern funktionieren, vorausgesetzt, sie unterstützen tr1 . Wenn nicht, müssen Sie möglicherweise Boost verwenden.
Die Boost-Dokumente sind hier hilfreich, um dies zu erklären, auch wenn Sie Boost nicht verwenden.
Der Trick besteht darin, die Tatsache zu nutzen, dass die Daten in Gruppen unterteilt wurden, und eine zufällig ausgewählte Gruppe schnell zu identifizieren (mit der entsprechenden Wahrscheinlichkeit).
//#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;
}
}
In Java 8:
static <E> E getRandomSetElement(Set<E> set) {
return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}
Dies ist identisch mit der akzeptierten Antwort (Khoth), jedoch ohne die unnötigen Variablen size und i.
int random = new Random().nextInt(myhashSet.size());
for(Object obj : myhashSet) {
if (random-- == 0) {
return obj;
}
}
Obwohl die beiden oben genannten Variablen wegfallen, bleibt die obige Lösung dennoch zufällig, da wir uns darauf verlassen, dass der Zufall (beginnend bei einem zufällig ausgewählten Index) sich bei jeder Iteration in Richtung 0 Dekrementiert.
Wie wäre es einfach
public static <A> A getRandomElement(Collection<A> c, Random r) {
return new ArrayList<A>(c).get(r.nextInt(c.size()));
}
Icon hat einen Settyp und einen Zufallselementoperator, unäres "?", Also den Ausdruck
? set( [1, 2, 3, 4, 5] )
erzeugt eine Zufallszahl zwischen 1 und 5.
Der Zufallsstartwert wird beim Ausführen eines Programms auf 0 initialisiert. Verwenden Sie also randomize(), um bei jedem Lauf unterschiedliche Ergebnisse zu erzielen.
Da Sie sagten "Lösungen für andere Sprachen sind auch willkommen", ist hier die Version für Python:
>>> import random
>>> random.choice([1,2,3,4,5,6])
3
>>> random.choice([1,2,3,4,5,6])
4
Können Sie nicht einfach die Größe/Länge der Menge/des Arrays ermitteln, eine Zufallszahl zwischen 0 und der Größe/Länge generieren und dann das Element aufrufen, dessen Index mit dieser Zahl übereinstimmt? HashSet hat eine .size () Methode, da bin ich mir ziemlich sicher.
Im Pseudocode -
function randFromSet(target){
var targetLength:uint = target.length()
var randomIndex:uint = random(0,targetLength);
return target[randomIndex];
}
In Mathematica:
a = {1, 2, 3, 4, 5}
a[[ ⌈ Length[a] Random[] ⌉ ]]
Oder in neueren Versionen einfach:
RandomChoice[a]
Dies wurde abgelehnt, vielleicht weil es keine Erklärung dafür gibt. Hier ist eines:
Random[] erzeugt einen pseudozufälligen Gleitkommawert zwischen 0 und 1. Dieser wird mit der Länge der Liste multipliziert und anschließend mit der Deckenfunktion auf die nächste Ganzzahl aufgerundet. Dieser Index wird dann aus a extrahiert.
Da Hashtabellen häufig mit Regeln in Mathematica ausgeführt werden und Regeln in Listen gespeichert werden, kann Folgendes verwendet werden:
a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};
PHP, vorausgesetzt "set" ist ein Array:
$foo = array("alpha", "bravo", "charlie");
$index = array_Rand($foo);
$val = $foo[$index];
Die Mersenne Twister-Funktionen sind besser, aber es gibt kein MT Äquivalent zu array_Rand in PHP.
Javascript Lösung;)
function choose (set) {
return set[Math.floor(Math.random() * set.length)];
}
var set = [1, 2, 3, 4], Rand = choose (set);
Oder alternativ:
Array.prototype.choose = function () {
return this[Math.floor(Math.random() * this.length)];
};
[1, 2, 3, 4].choose();
In 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"]);
Leider kann dies nicht effizient durchgeführt werden (besser als O(n)) in einem der Standard Library Set-Container).
Dies ist seltsam, da es sehr einfach ist, Hash-Mengen und Binärmengen mit einer zufälligen Auswahlfunktion zu versehen. In einem nicht zu spärlichen Hash-Set können Sie zufällige Einträge versuchen, bis Sie einen Treffer erhalten. Für einen binären Baum können Sie nach dem Zufallsprinzip zwischen dem linken und dem rechten Teilbaum wählen, mit maximal O(log2) Schritten. Ich habe eine Demo des folgenden implementiert:
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 __== '__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
Ich habe [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] als Ausgabe erhalten, so dass die Verteilungsnähte gut sind.
Ich habe mit dem gleichen Problem für mich selbst zu kämpfen, und ich habe noch nicht entschieden, ob der Leistungszuwachs dieses effizienteren Plektrums den Aufwand für die Verwendung einer auf python) basierenden Sammlung wert ist Natürlich verfeinere es und übersetze es nach C, aber das ist mir heute zu viel Arbeit :)
In LISP
(defun pick-random (set)
(nth (random (length set)) set))
Eine generische Lösung, bei der Khoths Antwort als Ausgangspunkt dient.
/**
* @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;
}
PHP mit 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];
Wenn die festgelegte Größe nicht groß ist, können Sie dies mithilfe von Arrays tun.
int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];
Zum Spaß habe ich ein RandomHashSet geschrieben, das auf dem Rejection Sampling basiert. Es ist ein bisschen hacky, da wir mit HashMap nicht direkt auf die Tabelle zugreifen können, aber es sollte gut funktionieren.
Es wird kein zusätzlicher Speicher verwendet und die Nachschlagezeit wird O(1) amortisiert. (Weil Java HashTable ist dicht)).
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;
}
}
}
Mit Guava können wir etwas besser als Khoths Antwort:
public static E random(Set<E> set) {
int index = random.nextInt(set.size();
if (set instanceof ImmutableSet) {
// ImmutableSet.asList() is O(1), as is .get() on the returned list
return set.asList().get(index);
}
return Iterables.get(set, index);
}
Wenn Sie wirklich nur "irgendein" Objekt aus dem Set auswählen möchten, ohne die Zufälligkeit zu garantieren, ist es am einfachsten, das erste vom Iterator zurückgegebene Objekt zu nehmen.
Set<Integer> s = ...
Iterator<Integer> it = s.iterator();
if(it.hasNext()){
Integer i = it.next();
// i is a "random" object from set
}
Das einfachste mit Java 8 ist:
outbound.stream().skip(n % outbound.size()).findFirst().get()
dabei ist n eine zufällige Ganzzahl. Natürlich ist es von geringerer Leistung als die mit der Funktion for(elem: Col)