Auswählen eines zufälligen Elements aus einer Menge

179

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.

Hinweis weniger
quelle
4
Sie sollten einige Bedingungen angeben, um festzustellen, ob dies wirklich das ist, was Sie wollen. - Wie oft werden Sie ein zufälliges Element auswählen? - Müssen die Daten in einem HashSet oder LinkedHashSet gespeichert werden, sind beide nicht zufällig zugänglich. - Ist der Hash groß eingestellt? Sind die Schlüssel klein?
David Nehme

Antworten:

88
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++;
}
Khoth
quelle
93
Wenn myHashSet groß ist, ist dies eine ziemlich langsame Lösung, da im Durchschnitt (n / 2) Iterationen erforderlich sind, um das zufällige Objekt zu finden.
Daniel
6
Wenn sich Ihre Daten in einem Hash-Set befinden, benötigen Sie O (n) Zeit. Es führt kein Weg daran vorbei, wenn Sie nur ein einzelnes Element auswählen und die Daten in einem HashSet gespeichert werden.
David Nehme
8
@ David Nehme: Dies ist ein Nachteil in der Spezifikation von HashSet in Java. In C ++ ist es typisch, direkt auf die Buckets zugreifen zu können, aus denen das Hashset besteht, wodurch wir zufällige Elemente effizienter auswählen können. Wenn in Java zufällige Elemente erforderlich sind, kann es sinnvoll sein, einen benutzerdefinierten Hash-Satz zu definieren, mit dem der Benutzer unter die Haube schauen kann. Weitere Informationen hierzu finden Sie in [Boosts Dokumentation] [1]. [1] boost.org/doc/libs/1_43_0/doc/html/unordered/buckets.html
Aaron McDaid
11
Wenn der Satz nicht über mehrere Zugriffe mutiert ist, können Sie ihn in ein Array kopieren und dann auf O (1) zugreifen. Verwenden Sie einfach myHashSet.toArray ()
ykaganovich
2
@ykaganovich würde dies die Sache nicht noch schlimmer machen, da das Set in ein neues Array kopiert werden müsste? docs.oracle.com/javase/7/docs/api/java/util/… "Diese Methode muss ein neues Array zuweisen, auch wenn diese Sammlung von einem Array unterstützt wird"
anton1980
73

Ein etwas verwandtes Wussten Sie schon:

Es gibt nützliche Methoden java.util.Collectionszum Mischen ganzer Sammlungen: Collections.shuffle(List<?>)und Collections.shuffle(List<?> list, Random rnd).

Hühnchen-Keks
quelle
Genial! Dies wird nirgendwo im Java-Dokument referenziert! Wie Pythons random.shuffle ()
smci
25
Dies funktioniert jedoch nur mit Listen, dh Strukturen mit der Funktion .get ().
Bourbaki4481472
4
@ Bourbaki4481472 ist absolut korrekt. Dies funktioniert nur für die Sammlungen, die die ListSchnittstelle erweitern, nicht für die Setvom OP diskutierte Schnittstelle.
Thomas
31

Schnelle Lösung für Java mit einem ArrayListund einem HashMap: [Element -> Index].

Motivation: Ich brauchte eine Reihe von Elementen mit RandomAccessEigenschaften, insbesondere um ein zufälliges Element aus der Gruppe auszuwählen (siehe pollRandomMethode). 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();
    }
}
fandrew
quelle
Nun, das würde funktionieren, aber die Frage betraf die Set-Oberfläche. Diese Lösung zwingt Benutzer zu konkreten Typreferenzen des RandomSet.
Johan Tidén
Ich mag diese Lösung wirklich, aber sie ist nicht threadsicher, es können Ungenauigkeiten zwischen der Karte und der Liste auftreten, daher würde ich einige synchronisierte Blöcke hinzufügen
Kostas Chalkias
@KonstantinosChalkias Die integrierten Sammlungen sind auch nicht threadsicher. Nur diejenigen mit dem Namen Concurrentsind wirklich sicher, diejenigen, die damit umwickelt Collections.synchronized()sind, sind halb sicher. Auch das OP hat nichts über Parallelität gesagt, daher ist dies eine gültige und gute Antwort.
TWiStErRob
Der hier zurückgegebene Iterator sollte keine Elemente entfernen können dta(dies kann über Guaven erreicht werdenIterators.unmodifiableIterator ). Andernfalls werden die Standardimplementierungen von z. B. removeAll und RetainAll in AbstractSet und seinen Eltern, die mit diesem Iterator arbeiten, Ihre Probleme lösen RandomSet!
Muued
Schöne Lösung. Sie können einen Baum tatsächlich verwenden, wenn jeder Knoten die Anzahl der Knoten in dem Teilbaum enthält, den er verwurzelt. Berechnen Sie dann einen zufälligen Real in 0..1 und treffen Sie an jedem Knoten eine gewichtete 3-Wege-Entscheidung (wählen Sie den aktuellen Knoten aus oder steigen Sie in den linken oder rechten Teilbaum ab), basierend auf den Knotenzahlen. Aber imo ist Ihre Lösung viel schöner.
Gene
29

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()jede Schleife auf, aber seitdemindex < set.size() diese Überprüfung unnötig ist. Ich sah eine Geschwindigkeitssteigerung von 10-20%, aber YMMV. (Außerdem wird dies 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 kann, 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();
    }
}
Sean Van Gorder
quelle
15

Wenn Sie dies in Java tun möchten, sollten Sie in Betracht ziehen, die Elemente in eine Sammlung mit wahlfreiem Zugriff (z. B. eine ArrayList) zu kopieren. Denn der Zugriff auf das ausgewählte Element ist teuer (O (n) anstelle von O (1)), es sei denn, Ihr Satz ist klein. [ed: Listenkopie ist auch O (n)]

Alternativ können Sie nach einer anderen Set-Implementierung suchen, die Ihren Anforderungen besser entspricht. Das ListOrderedSet aus Commons Collections sieht vielversprechend aus.

Dan Dyer
quelle
8
Das Kopieren in eine Liste kostet O (n) in der Zeit und verwendet auch O (n) Speicher. Warum sollte dies eine bessere Wahl sein, als direkt von der Karte abzurufen?
Mdma
12
Dies hängt davon ab, wie oft Sie aus dem Set auswählen möchten. Die Kopie ist eine einmalige Operation, und Sie können dann so oft aus dem Set auswählen, wie Sie benötigen. Wenn Sie nur ein Element auswählen, macht die Kopie die Dinge nicht schneller.
Dan Dyer
Es ist nur eine einmalige Operation, wenn Sie in der Lage sein möchten, mit Wiederholung zu wählen. Wenn Sie möchten, dass das ausgewählte Element aus dem Satz entfernt wird, kehren Sie zu O (n) zurück.
TurnipEntropy
12

In Java 8:

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}
Joshua Bone
quelle
9

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())]);
}
Jorge Ferreira
quelle
11
Ihre Antwort funktioniert, ist aber aufgrund des Teils set.toArray () nicht sehr effizient.
Hinweis weniger
12
Sie sollten das toArray außerhalb der Schleife verschieben.
David Nehme
8
List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);
Ben Noland
quelle
21
Das ist unglaublich ineffizient. Ihr ArrayList-Konstruktor ruft .toArray () für den angegebenen Satz auf. ToArray (in den meisten, wenn nicht allen Standard-Sammlungsimplementierungen) durchläuft die gesamte Sammlung und füllt dabei ein Array. Dann mischen Sie die Liste, die jedes Element gegen ein zufälliges Element austauscht. Sie sind viel besser dran, wenn Sie einfach über die Menge zu einem zufälligen Element iterieren.
Chris Bode
4

Dies ist identisch mit der akzeptierten Antwort (Khoth), jedoch werden die unnötigen sizeund iVariablen entfernt.

    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 immer noch zufällig, da wir uns auf zufällig (beginnend mit einem zufällig ausgewählten Index) verlassen, um sich 0über jede Iteration hinweg zu dekrementieren .

Jason Hartley
quelle
1
Dritte Zeile könnte auch sein if (--random < 0) {, wo randomerreicht -1.
Salvador
3

Clojure-Lösung:

(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq)))))
pjb3
quelle
1
Diese Lösung ist auch linear, da Sie das nthElement ebenfalls durchlaufen müssen , um das Element zu erhalten seq.
Bruno Kim
1
Es ist auch linear, da es gut in eine Zeile passt: D
Krzysztof Wolny
2

Perl 5

@hash_keys = (keys %hash);
$rand = int(rand(@hash_keys));
print $hash{$hash_keys[$rand]};

Hier ist eine Möglichkeit, dies zu tun.

JJ
quelle
2

C ++. Dies sollte relativ schnell gehen, da es nicht erforderlich ist, den gesamten Satz zu durchlaufen oder zu sortieren. Dies sollte bei den meisten modernen Compilern sofort 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 Buckets unterteilt wurden, und schnell einen zufällig ausgewählten Bucket 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;
  }
}
Aaron McDaid
quelle
2

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, versuchen Sie es mit einer Probenahme im Reservoir. http://en.wikipedia.org/wiki/Reservoir_sampling .
Collections.shuffle () (wie von wenigen vorgeschlagen) verwendet einen solchen Algorithmus.

die Geschwindigkeit
quelle
1

Da Sie sagten "Lösungen für andere Sprachen sind ebenfalls 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
Swaroop CH
quelle
3
Nur ist [1,2,3,4,5,6] kein Satz, sondern eine Liste, da es Dinge wie schnelle Suchvorgänge nicht unterstützt.
Thomas Ahle
Sie können immer noch Folgendes tun: >>> random.choice (list (set (range (5))) >>> 4 Nicht ideal, aber es reicht aus, wenn Sie es unbedingt müssen.
SapphireSun
1

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];
}
matt lohkamp
quelle
Dies funktioniert nur, wenn der betreffende Container eine zufällige Indexsuche unterstützt. Viele Container-Implementierungen tun dies nicht (z. B. Hash-Tabellen, Binärbäume, verknüpfte Listen).
David Haley
1

PHP unter der Annahme, dass "set" ein Array ist:

$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.

Dirtside
quelle
Die meisten Set-Implementierungen haben keinen get (i) - oder Indexing-Operator, daher gehe ich davon aus, dass OP vor
DownloadPizza
1

Icon hat einen Set-Typ und einen Zufallselement-Operator, unäres "?", Also den Ausdruck

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

erzeugt eine Zufallszahl zwischen 1 und 5.

Der zufällige Startwert wird beim Ausführen eines Programms auf 0 initialisiert, um bei jeder Ausführung unterschiedliche Ergebnisse zu erzielen randomize()

Hugh Allen
quelle
1

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"]);
Mitch Wheat
quelle
Es sieht so aus, als hätten sie herabgestimmt, weil auf das beschissene Java-Wörterbuch (oder das sogenannte LinkedHashSet, was auch immer zum Teufel ist) nicht "zufällig zugegriffen" werden kann (was vermutlich über einen Schlüssel zugegriffen wird). Der Java-Mist bringt mich so zum Lachen
Federico Berasategui
1

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();
Mathew Byrne
quelle
Ich bevorzuge die zweite Alternative. :-)
Marcospereira
ooh, ich mag es, die neue Array-Methode zu erweitern!
Matt Lohkamp
1

In lisp

(defun pick-random (set)
       (nth (random (length set)) set))
inglesp
quelle
Das funktioniert nur für Listen, oder? Damit ELTkönnte für jede Sequenz gearbeitet werden.
Ken
1

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 gibt. Hier ist eine:

Random[]erzeugt einen Pseudozufalls-Float zwischen 0 und 1. Dieser wird mit der Länge der Liste multipliziert und dann wird die Deckenfunktion verwendet, um auf die nächste Ganzzahl aufzurunden. Dieser Index wird dann extrahiert a.

Da die Funktionalität von Hash-Tabellen in Mathematica häufig mit Regeln ausgeführt wird und Regeln in Listen gespeichert werden, kann Folgendes verwendet werden:

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

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()));
}
Daniel Lubarov
quelle
1

Zum Spaß habe ich ein RandomHashSet geschrieben, das auf Ablehnungsstichproben basiert. Es ist ein bisschen hackig, 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 Suchzeit wird mit O (1) amortisiert. (Weil Java HashTable dicht ist).

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;
        }
    }
}
Thomas Ahle
quelle
1
Genau das, was ich dachte! Beste Antwort!
mmm
Wenn ich darauf zurückkomme, denke ich, dass dies nicht ganz einheitlich ist, wenn die Hashmap viele Kollisionen aufweist und wir viele Abfragen durchführen. Dies liegt daran, dass die Java-Hashmap Buckets / Chaining verwendet und dieser Code immer das erste Element im jeweiligen Bucket zurückgibt. Wir sind uns jedoch immer noch einig über die Zufälligkeit der Hash-Funktion.
Thomas Ahle
1

Am einfachsten mit Java 8 ist:

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

wo nist eine zufällige ganze Zahl. Natürlich ist es von geringerer Leistung als das mit demfor(elem: Col)

Nicu Marasoiu
quelle
1

Mit Guave 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);
}
dimo414
quelle
0

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];
da5id
quelle
0

Sie können das Set auch auf ein Array übertragen. Verwenden Sie das Array. Es wird wahrscheinlich im kleinen Maßstab funktionieren. Ich sehe, dass die for-Schleife in der am häufigsten gewählten Antwort ohnehin O (n) ist

Object[] arr = set.toArray();

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

Wenn Sie wirklich nur "irgendein" Objekt aus dem auswählen möchten Set, ohne die Zufälligkeit zu garantieren, ist es am einfachsten, das erste vom Iterator zurückgegebene zu nehmen.

    Set<Integer> s = ...
    Iterator<Integer> it = s.iterator();
    if(it.hasNext()){
        Integer i = it.next();
        // i is a "random" object from set
    }
Philipp
quelle
1
Dies wird jedoch keine zufällige Auswahl sein. Stellen Sie sich vor, Sie führen denselben Vorgang mehrmals über denselben Satz aus. Ich denke, die Reihenfolge wird dieselbe sein.
Menezes Sousa
0

Eine generische Lösung, die Khoths Antwort als Ausgangspunkt verwendet.

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

Leider kann dies in keinem der Set-Container der Standardbibliothek effizient (besser als O (n)) durchgeführt werden.

Dies ist seltsam, da es sehr einfach ist, Hash-Sets und Binär-Sets eine zufällige Auswahlfunktion hinzuzufügen. 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ärbaum können Sie zufällig zwischen dem linken oder rechten Teilbaum mit maximal O (log2) Schritten wählen. Ich habe eine Demo der 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 __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 erhalten, sodass 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 Leistungsgewinn dieser effizienteren Auswahl den Aufwand für die Verwendung einer Python-basierten Sammlung wert ist. Ich könnte es natürlich verfeinern und in C übersetzen, aber das ist mir heute zu viel Arbeit :)

Thomas Ahle
quelle
1
Ein Grund, warum ich denke, dass dies nicht in einem Binärbaum implementiert ist, ist, dass eine solche Methode Elemente nicht einheitlich auswählen würde. Da es sich um Knoten ohne linkes / rechtes Kind handelt, kann es vorkommen, dass das linke Kind mehr Elemente enthält als das rechte Kind (oder umgekehrt). Dies würde die Auswahl eines Elements am rechten (oder linken) Kind wahrscheinlicher machen.
Willem Van Onsem
1
@CommuSoft: Deshalb speichere ich die Größe jedes Teilbaums, damit ich meine Wahrscheinlichkeiten basierend auf diesen auswählen kann.
Thomas Ahle