Aufnehmen eines Zufallselement aus einem Satz

StackOverflow https://stackoverflow.com/questions/124671

Frage

Wie hole ich ein zufälliges Element aus einem Satz? Ich interessiere mich besonders für ein zufälliges Element aus einem in der Kommissionierung HashSet oder ein LinkedHashSet, in Java. Lösungen für andere Sprachen sind auch willkommen.

War es hilfreich?

Lösung 

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++;
}

Andere Tipps

Ein etwas im Zusammenhang Wissen Sie schon:

Es gibt nützliche Methoden in java.util.Collections für schlurfenden ganze Sammlungen: Collections.shuffle(List<?>) und Collections.shuffle(List<?> list, Random rnd) .

Schnelle Lösung für Java unter Verwendung eines ArrayList und HashMap.: [Element -> index]

Motivation: Ich brauchte eine Menge von Elementen mit RandomAccess Eigenschaften, insbesondere ein zufälliges Element aus der Menge zu holen (pollRandom Methode sehen). Zufällige Navigation in einem binären Baum ist nicht korrekt. 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 foreach-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();

Die foreach-Konstrukt ruft Iterator.hasNext() auf jeder Schleife, aber da index < set.size(), dass der Check ist unnötiger Aufwand. Ich sah eine 10-20% Steigerung der Geschwindigkeit, aber YMMV. (Auch diese kompiliert ohne eine zusätzliche return-Anweisung zu müssen.)

Beachten Sie, dass dieser Code (und die meisten anderen Antworten) kann auf jede Sammlung angewendet werden, nicht nur ein. In generische Methode Form: 

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 es in Java tun mögen, sollten Sie die Elemente in eine Art von Schreib-Lese-Sammlung (wie ein Arraylist) Kopieren betrachten. Weil, es sei denn, Ihr Set klein ist, wird das ausgewählte Element Zugriff teuer sein (O (n) anstelle von O (1)). [Ed: Liste Kopie ist auch O (n)]

Alternativ können Sie auch für ein anderes Set Umsetzung aussehen könnte, die Ihren Anforderungen genauer übereinstimmt. Die ListOrderedSet von Commons Sammlungen 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, es zu tun.

C ++. Dies sollte ziemlich schnell sein, da es nicht über den gesamten Satz Iterieren erfordert, oder es zu sortieren. Dies sollte mit den meisten modernen Compilern der Box funktionieren, vorausgesetzt, sie unterstützen tr1 . Wenn nicht, müssen Sie möglicherweise Boost verwenden.

Die docs Erhöhung hilfreich hier, dies zu erklären, auch wenn Sie nicht-Boost verwenden.

Der Trick ist, sich die Tatsache zunutze zu machen, daß die Daten in Buckets unterteilt wurde, und um schnell einen zufällig ausgewählten bucket (mit der entsprechenden Wahrscheinlichkeit) zu identifizieren. 

//#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;
  }
}

Lösung sprechen oben in Bezug auf die Latenzzeit garantiert aber nicht die gleiche Wahrscheinlichkeit von jeder Index ausgewählt werden.
Wenn das zu berücksichtigen braucht, versuchen Reservoir Probenahme. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle ( ) (wie wenige) verwendet einen solchen Algorithmus vorgeschlagen.

Da sagte man „Lösungen für andere Sprachen sind auch willkommen“, hier ist 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

Kann nicht nur die Größe / Länge des Satzes / Array erhalten, eine Zufallszahl zwischen 0 und der Größe / Länge erzeugen, rufen Sie dann das Element, dessen Index entspricht diese Zahl? HashSet hat eine .Size () -Methode, ich bin mir ziemlich sicher.

In psuedocode - 

function randFromSet(target){
 var targetLength:uint = target.length()
 var randomIndex:uint = random(0,targetLength);
 return target[randomIndex];
}

PHP, unter der Annahme, "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 keine MT-Äquivalent von array_rand in PHP.

Icon hat einen Satz Typ und ein Zufallselement-Operator, einstellige " „?, so der Ausdruck 

? set( [1, 2, 3, 4, 5] )

wird eine Zufallszahl zwischen 1 und 5 erzeugen.

Der Zufall Samt auf 0 initialisiert wird, wenn ein Programm ausgeführt wird, so unterschiedliche Ergebnisse bei jedem Durchlauf Verwendung randomize()

zu erzeugen,

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"]);

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 Lisp 

(defun pick-random (set)
       (nth (random (length set)) set))

In Mathematica: 

a = {1, 2, 3, 4, 5}

a[[ ⌈ Length[a] Random[] ⌉ ]]

Oder in den letzten Versionen einfach wie folgt: 

RandomChoice[a]

Dieser erhielt eine Abwärts Stimme, vielleicht, weil es Erklärung fehlt, also hier ist:

Random[] erzeugt einen Pseudo-Zufalls-Schwimmers zwischen 0 und 1 ist dies durch die Länge der Liste multipliziert wird, und dann wird die Deckenfunktion runde bis zur nächsten ganzen Zahl verwendet wird. Dieser Index wird dann aus a extrahiert.

Da Hash-Tabelle Funktionalität wird häufig mit Regeln in Mathematica getan und Regeln in Listen gespeichert sind, könnte man verwenden: 

a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};

Wie wäre es nur 

public static <A> A getRandomElement(Collection<A> c, Random r) {
  return new ArrayList<A>(c).get(r.nextInt(c.size()));
}

Dies ist identisch mit akzeptierter Antwort (Khoth), aber mit dem unnötigen size und i Variablen entfernt. 

    int random = new Random().nextInt(myhashSet.size());
    for(Object obj : myhashSet) {
        if (random-- == 0) {
            return obj;
        }
    }

Obwohl mit den beiden genannten Variablen zu tun weg, die obige Lösung noch zufällig bleibt, weil wir auf zufällige setzen (bei einem zufällig ausgewählten Index beginnend) sich über jede Iteration in Richtung 0 zu verringern.

Leider kann dies nicht effizient durchgeführt werden (besser als O (n)) in eines des Standardbibliothek Behälter.

Das ist seltsam, da es sehr einfach ist, eine randomisierte Pick-Funktion hinzuzufügen Sets sowie binäre Sätze Hash. In einem nicht Hash-Set spärlich, können Sie zufällige Einträge versuchen, bis Sie einen Treffer erhalten. Für einen binären Baum können Sie zufällig zwischen der linken oder rechten Unterbaum, mit einem Maximum von O (log 2) Stufen wählen. Ich habe eine Demo von der später unter 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 __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

Ich habe [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] als Ausgabe, so dass die Verteilung Nähte gut.

Ich habe mit dem gleichen Problem für mich gekämpft, und ich habe noch nicht Wetter die Leistungssteigerung dieser effizienter Pick lohnt sich der Aufwand der Verwendung eines Python-basierten Sammlung entschieden. Ich könnte natürlich verfeinern sie und übersetzen es zu C, aber das ist zu viel Arbeit für mich heute:)

In Java 8: 

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(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];

Für Spaß habe ich ein RandomHashSet basierend auf Ablehnung Probenahme. Es ist ein bisschen hacky, da HashMap uns nicht lassen darauf zuzugreifen Tisch ist direkt, aber es sollte gut funktionieren.

Es verwendet keine zusätzlichen Speicher und Lookup-Zeit ist O (1) abgeschrieben. (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;
        }
    }
}

Sie können auch den Satz Transfer zum Array verwenden Array es wird wahrscheinlich auf kleinen Maßstab arbeiten ich die for-Schleife in den meisten Stimmen Antwort sehen ist O (n) sowieso 

Object[] arr = set.toArray();

int v = (int) arr[rnd.nextInt(arr.length)];

Wenn Sie wirklich nur holen wollen „any“ Objekt aus dem Set, ohne Garantien für die Zufälligkeit, die einfachste ist die erste von der Iterator zurück nehmen. 

    Set<Integer> s = ...
    Iterator<Integer> it = s.iterator();
    if(it.hasNext()){
        Integer i = it.next();
        // i is a "random" object from set
    }

Am einfachsten mit Java 8: 

outbound.stream().skip(n % outbound.size()).findFirst().get()

wo n ist eine Zufallszahl. Natürlich ist es von weniger Leistung als die mit dem for(elem: Col)

Eine generische Lösung Khoth Antwort als Ausgangspunkt verwendet wird. 

/**
 * @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;
}

Wenn festgelegte Größe nicht groß ist dann von Arrays verwenden dies getan werden kann. 

int random;
HashSet someSet;
<Type>[] randData;
random = new Random(System.currentTimeMillis).nextInt(someSet.size());
randData = someSet.toArray();
<Type> sResult = randData[random];
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top