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

Question

J'ai un ensemble d'objets dans un Vecteur à partir duquel je voudrais sélectionner un sous-ensemble aléatoire (par exemple de 100 articles de revenir; pick 5 au hasard). Dans mon premier (à la hâte) passer j'ai fait une très simple et peut-être trop intelligent solution:

Vector itemsVector = getItems();

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

Tout cela a l'avantage d'être simple et sympathique, je pense qu'elle ne va pas à l'échelle très bien, c'est à dire des Collections.shuffle() doit être en O(n) au moins. Mon alternative est moins intelligent

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

Toutes les suggestions sur les meilleures façons de tirer un sous-ensemble aléatoire à partir d'une Collection?

Answer 1

Je viens de poster un article sur l'échantillonnage aléatoire dans mon blog Java. Il couvre les algorithmes mentionnés ici, ainsi que les implémentations et les analyses.

Voir http://eyalsch.wordpress.com/2010/04/01/random-sample/

Answer 2

Jon Bentley décrit ce soit dans la Programmation de Perles " ou " Plus de la Programmation des Perles. Vous devez être prudent avec votre N de M processus de sélection, mais je pense que le code fonctionne correctement. Plutôt que de façon aléatoire lecture aléatoire de tous les éléments, vous pouvez faire de l'aléatoire shuffle seulement brouiller les N premières positions, qui est une utile d'économie lorsque N << M.

Knuth parle également de ces algorithmes - je crois que ce serait Vol 3 "de Tri et de Recherche", mais mon ensemble est emballé dans l'attente d'un déménagement de la maison donc je ne peux pas officiellement vérifier.

Answer 3

@ Jonathan ,

Je crois 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 m premiers éléments du tableau ..."

Answer 4

J'ai écrit une mise en œuvre efficace de cette y a quelques semaines. C'est en C#, mais la traduction en Java est trivial (essentiellement le même code). Le côté positif est que c'est aussi complètement impartial (dont certaines de ces réponses ne sont pas) - un moyen de tester c'est ici.

Il est basé sur un Durstenfeld mise en œuvre de l'shuffle de Fisher-Yates.

Answer 5

Votre deuxième solution, qui consiste à utiliser Aléatoire pour sélectionner un élément, semble correcte, cependant:

• En fonction de la sensibilité de vos données, je suggère d'utiliser une sorte de méthode de hachage pour brouiller la graine de nombres aléatoires. Voyez comment nous avons appris à tricher au poker en ligne pour une bonne étude de cas.
• Le vecteur est synchronisé. Si possible, utilisez plutôt ArrayList pour améliorer les performances.