bester Weg, um eine zufällige Teilmenge aus einer Sammlung zu holen?

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

Frage

ich eine Reihe von Objekten in einem Vektor hat, aus dem Ich mag würde eine zufällige Teilmenge wählen (zum Beispiel 100 kommenden Artikel zurück; Pick 5 zufällig). In meinem ersten (sehr voreilig) Pass habe ich eine extrem einfache und vielleicht allzu clevere Lösung: 

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

Während dies den Vorteil, dass sie schön und einfach hat, wie ich vermute, es wird nicht sehr gut skalieren, das heißt Collections.shuffle () muss O (n) zumindest sein. Meine weniger clevere Alternative ist 

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

Irgendwelche Vorschläge auf bessere Möglichkeiten, eine zufällige Teilmenge aus einer Sammlung zu ziehen?

War es hilfreich?

Lösung

Jon Bentley bespricht dies entweder 'Programmierung Pearls' oder 'Mehr Programming Pearls'. Sie müssen sich mit Ihrem N von M Auswahlprozess vorsichtig sein, aber ich denke, der Code funktioniert korrekt dargestellt. Anstatt wahllos alle Einzelteile zu mischen, können Sie die zufällige Shuffle tun nur die ersten N-Positionen schlurfend - was eine sinnvolle Einsparung ist, wenn N << M

.

Knuth bespricht auch diese Algorithmen - Ich glaube, dass Band sein würde 3 „Sortieren und Suchen“, aber mein Set verpackt ist eine Bewegung des Hauses anhängig, so kann ich nicht formell, dass der Check

.

Andere Tipps

@ Jonathan,

Ich glaube, dass dies die Lösung Sie sprechen: 

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

Es ist auf Seite 127 der Programmierung Pearls von Jon Bentley und basiert weg von Knuth-Implementierung.

EDIT: Ich habe gerade gesehen, die eine weitere Modifikation auf Seite 129: 

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

Dies ist auf die Idee, dass „... wir brauchen mische nur die erste Seite m Elemente des Arrays ...“

Wenn Sie versuchen, k unterschiedliche Elemente aus einer Liste von n auszuwählen, die Methoden, die Sie oben gegeben wird O (n) oder O (kn), weil von einem Vektor ein Element entfernt wird eine arraycopy führen alle verschieben die Elemente nach unten.

Da Sie nach dem besten Weg sind gefragt, es hängt davon ab, was Sie erlaubt werden, mit Ihrer Eingabeliste zu tun.

Wenn es akzeptabel, die Eingabeliste zu ändern, wie in Ihrem Beispiel, dann können Sie einfach k zufällige Elemente am Anfang der Liste tauschen und bringt sie in O (k) Zeit wie folgt aus: 

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

Wenn die Liste im gleichen Zustand am Ende muss es begann, Sie den Überblick über die Positionen halten können Sie vertauscht, und dann wieder die Liste in dem ursprünglichen Zustand nach dem ausgewählten Unterliste zu kopieren. Dies ist immer noch eine O (k) Lösung.

Wenn Sie jedoch nicht die Eingabeliste überhaupt ändern und k viel kleiner als n (wie 5 von 100), wäre es viel besser, nicht ausgewählte Elemente jedes Mal zu entfernen, sondern einfach jedes Element auswählen, und wenn Sie jemals ein Duplikat bekommen, werfen Sie es aus und wählen Sie erneut. Dies wird Ihnen O (kn / (n-k)), die noch in der Nähe O (k), wenn n k dominiert. (Zum Beispiel, wenn k kleiner als n / 2 ist, dann reduziert sie auf O (k)).

Wenn k nicht durch n dominiert, und Sie können die Liste nicht ändern, können Sie auch Ihre ursprüngliche Liste kopieren und verwenden Sie Ihre erste Lösung, da O (n) als O genauso gut sein wird (k).

Wie andere haben darauf hingewiesen, wenn Sie auf eine starke Zufälligkeit abhängig sind, wo jeder sublist möglich ist (und unvoreingenommenen), werden Sie auf jeden Fall brauchen etwas stärker als java.util.Random. Siehe java.security.SecureRandom.

Ich schrieb eine effiziente Umsetzung dieses ein paar Wochen zurück. Es ist in C #, aber die Übersetzung Java ist trivial (im Wesentlichen der gleiche Code). Die Plus-Seite ist, dass es auch völlig unvoreingenommen (die einige der vorhandenen Antworten sind nicht) - eine Möglichkeit, das zu testen ist hier .

Es basiert auf einer Durstenfeld Umsetzung des Fisher-Yates shuffle.

Ihre zweite Lösung mit Zufallselement zu holen scheint Sound, aber:

Wie viel kostet entfernen Kosten? Denn wenn das das Array zu einem neuen Teil des Speichers neu zu schreiben muss, dann haben Sie getan O (5N) Operationen in der zweiten Version, anstatt die O (n) Sie wollten vor.

Sie können eine Reihe von booleans auf false gesetzt erstellen und dann: 

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

Dieser Ansatz funktioniert, wenn Ihre Teilmenge ist kleiner als Ihre Gesamtgröße mit deutlichem Vorsprung. Da diese Größen nahe beieinander (dh 1/4 der Größe oder etwas) zu bekommen, würden Sie mehr Kollisionen auf diesem Zufallszahlengenerator erhalten. In diesem Fall würde ich eine Liste von ganzen Zahlen der Größe der größeren Arrays machen, und dann diese Liste von ganzen Zahlen mische, und ziehen Sie die ersten Elemente aus, dass Ihre (nichtkollidierend) Indizes zu erhalten. Auf diese Weise haben Sie die Kosten für O (n) in der Integer-Array bauen, und einen anderen O (n) in der Shuffle, aber keine Kollisionen von einem internen während Prüfer und weniger als das Potential O (5N), die zu entfernen kosten.

Ich würde persönlich entscheiden Sie sich für Ihre erste Implementierung: sehr prägnant. Performance-Tests werden zeigen, wie gut es skaliert. Ich habe einen sehr ähnlichen Code-Block in einer anständig missbraucht Methode implementiert und skaliert ausreichend. Der besondere Code stützte sich auf Arrays mit> 10.000 Artikel auch. 

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

Diese ist eine ganz ähnliche Frage Stackoverflow.

Zu meinen Lieblings Antworten von dieser Seite (furst ein von Benutzer Kyle) zusammenfassen:

  • O (n) Lösung : eine Iteration durch die Liste, und kopieren aus einem Element (oder Bezugnahme darauf) mit einer Wahrscheinlichkeit (#needed / #remaining). Beispiel: Wenn k = 5 und n = 100 ist, dann nimmt man das erste Element mit prob 5/100. Wenn Sie kopieren, dass ein, dann wählen Sie die nächste mit prob 4/99; aber wenn man die ersten nicht nehmen, das prob ist 5/99.
  • O (k log k) oder O (k 2 ) : Erstellen Sie eine sortierte Liste von k-Indizes (Zahlen in {0, 1, ..., n -1}) durch zufällig eine Zahl Auswahl 43 =, dann fügen Sie 1 zu. Also, wenn Ihre zweite Wahl 50 ist, dann fügen Sie 1, um es, und Sie haben {43, 51}. Wenn Sie Ihre nächste Wahl 51 ist, fügen Sie 2 , um es zu bekommen {43, 51, 53}.

Hier finden Sie einige pseudopython - 

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

Ich sage, dass die Zeitkomplexität O (k 2 ) oder O (k log k), weil es hängt davon ab, wie schnell Sie suchen und einfügen in Ihre Behälter für s. Wenn s eine normale Liste enthalten ist, ist eine dieser Operationen linear, und Sie erhalten k ^ 2. Allerdings, wenn Sie bereit sind, s als ein ausgewogener binärer Baum zu bauen, können Sie die O (k log k) Zeit auszusteigen.

zwei Lösungen, die ich glaube nicht, hier zu erscheinen - das entspricht ziemlich lang ist, und enthält einige Links, aber ich glaube nicht, alle die Beiträge auf das Problem bezieht eine subst von K bei der Wahl elemetns aus einem Satz von N Elementen. [Mit „Set“, ich auf den mathematischen Begriff beziehen, das heißt alle Elemente erscheinen einmal, um nicht wichtig ist].

Sol 1: 

//Assume the set is given as an array:
Object[] set ....;
for(int i=0;i<K; i++){
randomNumber = random() % N;
    print set[randomNumber];
    //swap the chosen element with the last place
    temp = set[randomName];
    set[randomName] = set[N-1];
    set[N-1] = temp;
    //decrease N
    N--;
}

Das sieht ähnlich wie die Antwort daniel gab, aber es ist eigentlich ganz anders. Es ist von O (k) Laufzeit.

Eine andere Lösung ist etwas Mathematik zu verwenden: betrachten die Array-Indizes als Z_n und so können wir wählen zufällig 2 Zahlen, x, die an n Co-Primzahl ist, dh chhose gcd (x, n) = 1, und eine andere, eine, die als „Startpunkt“ ist - dann wird die Serie : a% n, a + x% n, a + 2 * x% N, ... a + (k-1) * x% n eine Folge von verschiedenen Zahlen ist (solange k <= n)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top