meilleure façon de choisir un sous-ensemble aléatoire à partir d'une collection?

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

Question

J'ai un ensemble d'objets dans un vecteur à partir duquel j'aimerais sélectionner un sous-ensemble aléatoire (par exemple, 100 éléments revenant; en choisir 5 au hasard). Lors de mon premier passage (très précipité), j’ai proposé une solution extrêmement simple et peut-être trop astucieuse: 

Vector itemsVector = getItems();

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

Bien que cela ait l’avantage d’être simple et agréable, j’imagine que cela ne se fera pas très bien, c.-à-d. Collections.shuffle () doit être au moins égal à O (n). Mon alternative moins intelligente est 

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())));
}

Des suggestions sur de meilleurs moyens de tirer un sous-ensemble aléatoire d'une collection?

Était-ce utile?

La solution

Jon Bentley en parle dans "Programmation des perles" ou "Plus de programmation des perles". Vous devez faire attention avec votre processus de sélection N sur M, mais je pense que le code affiché fonctionne correctement. Plutôt que de mélanger tous les éléments de manière aléatoire, vous pouvez effectuer la lecture aléatoire uniquement en mélangeant les N premières positions - ce qui est une sauvegarde utile lorsque N & Lt; & Lt; M.

Knuth discute également de ces algorithmes - je crois que ce serait le volume 3 & "Trier et rechercher &"; mais mon ensemble est emballé en attendant un déménagement, je ne peux donc pas le vérifier formellement.

Autres conseils

@Jonathan,

Je pense que c'est la solution dont vous parlez: 

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

C’est à la page 127 de Programming Pearls de Jon Bentley et est basé sur l’implémentation de Knuth.

EDIT: je viens de voir une modification supplémentaire à la page 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";
}

Ceci est basé sur l'idée que & "; ... nous n'avons besoin de mélanger que les premiers m éléments du tableau ... &";

Si vous essayez de sélectionner k éléments distincts dans une liste de n, les méthodes que vous avez indiquées ci-dessus seront O (n) ou O (kn), car la suppression d'un élément d'un vecteur entraînerait le déplacement de tous les éléments en bas.

Puisque vous demandez le meilleur moyen, cela dépend de ce que vous êtes autorisé à faire avec votre liste de saisie.

S'il est acceptable de modifier la liste d'entrée, comme dans vos exemples, vous pouvez simplement permuter k éléments aléatoires au début de la liste et les renvoyer en temps O (k) comme ceci: 

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

Si la liste doit se retrouver dans le même état que vous avez commencé, vous pouvez suivre les positions que vous avez permutées, puis rétablir l'état d'origine de la liste après avoir copié la sous-liste sélectionnée. C’est toujours une solution O (k).

Si, toutefois, vous ne pouvez pas du tout modifier la liste des entrées et que k est bien inférieur à n (comme 5 à 100), il serait préférable de ne pas supprimer les éléments sélectionnés à chaque fois, mais simplement de sélectionner chaque élément, et si vous obtenez un duplicata, jetez-le et resélectionnez. Cela vous donnera O (kn / (n-k)) qui est toujours proche de O (k) lorsque n domine k. (Par exemple, si k est inférieur à n / 2, il se réduit à 0 (k)).

Si k n'est pas dominé par n et que vous ne pouvez pas modifier la liste, vous pouvez également copier votre liste d'origine et utiliser votre première solution, car O (n) sera aussi bon que O (k).

Comme d'autres l'ont déjà noté, si vous dépendez d'un fort caractère aléatoire, où chaque sous-liste est possible (et impartiale), vous aurez certainement besoin de quelque chose de plus fort que java.util.Random. Voir java.security.SecureRandom.

J'ai écrit une mise en œuvre efficace de cette un moyen de tester qui se trouve ici .

Il est basé sur une implémentation de Durstenfeld du shuffle Fisher-Yates.

Votre deuxième solution, qui consiste à utiliser Random pour choisir un élément, semble bonne, cependant:

Combien coûte le retrait? Parce que si cela doit réécrire le tableau sur un nouveau bloc de mémoire, alors vous avez effectué des opérations O (5n) dans la deuxième version, plutôt que le O (n) que vous vouliez auparavant.

Vous pouvez créer un tableau de booléens défini sur false, puis: 

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

Cette approche fonctionne si votre sous-ensemble est plus petit que votre taille totale d'une marge significative. À mesure que ces tailles se rapprochent les unes des autres (c'est-à-dire 1/4 de la taille ou quelque chose), vous obtiendrez plus de collisions sur ce générateur de nombres aléatoires. Dans ce cas, je ferais une liste d’entiers de la taille de votre plus grand tableau, puis je mélangerais cette liste d’entiers et en extrairais les premiers éléments pour obtenir vos index (non en collision). De cette façon, vous avez le coût de O (n) dans la construction du tableau entier, et un autre O (n) dans le shuffle, mais pas de collisions avec un vérificateur interne et moins que le potentiel O (5n) que supprimer peut coûter.

Je préférerais personnellement opter pour votre implémentation initiale: très concis. Les tests de performance montreront à quel point il évolue. J'ai implémenté un bloc de code très similaire dans une méthode mal exploitée et sa taille a été suffisamment réduite. Le code particulier reposait sur des tableaux contenant & Gt; 10 000 éléments également. 

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

Ceci est une question très similaire à propos de stackoverflow.

Pour résumer mes réponses préférées sur cette page (l'une de l'utilisateur Kyle):

  • Solution O (n) : parcourez votre liste et copiez un élément (ou sa référence) avec une probabilité (#needed / #remaining). Exemple: si k = 5 et n = 100, vous prenez le premier élément avec prob 5/100. Si vous copiez celui-ci, vous choisissez le suivant avec prob 4/99; mais si vous n'avez pas pris le premier, le problème est de 5/99.
  • O (k log k) ou O (k 2 ) : créez une liste triée de k indices (nombres entre {0, 1, ..., n -1}) en choisissant au hasard un nombre & Lt; n, puis en choisissant au hasard un nombre < n-1, etc. A chaque étape, vous devez rappeler votre choix pour éviter les collisions et maintenir les probabilités égales. Par exemple, si k = 5 et n = 100 et que votre premier choix est 43, votre prochain choix se situe dans la plage [0, 98] et s'il s'agit de & Gt; = 43, vous ajoutez 1 à celui-ci. . Donc, si votre deuxième choix est 50, vous ajoutez 1, et vous avez {43, 51}. Si votre prochain choix est 51, vous y ajoutez 2 pour obtenir {43, 51, 53}.

Voici un 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

Je dis que la complexité temporelle est O (k 2 ) ou O (k log k) car cela dépend de la rapidité avec laquelle vous pouvez rechercher et insérer votre conteneur pour s. Si s est une liste normale, l’une de ces opérations est linéaire et vous obtenez k ^ 2. Toutefois, si vous souhaitez construire s sous forme d'arborescence binaire équilibrée, vous pouvez obtenir le temps O (k log k).

Deux solutions que je ne pense pas apparaître ici - la correspondance est assez longue, et contient quelques liens, cependant, je ne pense pas que tous les articles se rapportent au problème du choix d’un sous-groupe de K elémen dans un ensemble de N éléments. [Par & Quot; set & Quot ;, je fais référence au terme mathématique, c’est-à-dire que tous les éléments apparaissent une fois, l’ordre n’est pas important].

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

Cela ressemble à la réponse donnée par Daniel, mais en réalité, il est très différent. C'est du temps d'exécution O (k).

Une autre solution consiste à utiliser des mathématiques: considérons les indices du tableau comme étant Z_n et nous pouvons donc choisir aléatoirement 2 nombres, x co-amorçant à n, c’est-à-dire chhose gcd (x, n) = 1, et un autre, a, qui est & «point de départ < !> quot; - puis la série: a% n, a + x% n, a + 2 * x% n, ... a + (k-1) * x% n est une suite de nombres distincts (tant que k < = n).

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top