Quelle est la meilleure façon d'extraire efficacement un petit sous-ensemble aléatoire d'une grande énumérable?

Question

Quelle est la meilleure façon de récupérer n éléments d'un IEnumerable <T> dans un ordre aléatoire? J'écris une API de magasin et j'ai besoin de fournir un petit ensemble d'éléments aléatoires à partir d'une énumération parfois énorme d'éléments. L'énumérable sous-jacent est parfois un tableau, et parfois un filtre évalué paresseux dudit tableau. Comme je ne fais que saisir un nombre proportionnellement faible d'éléments des énumérations, il est préférable d'utiliser une sorte d'index aléatoire répété dans l'énumération et la vérification de dupe à chaque fois plutôt que de trier aléatoirement la liste entière en utilisant un algorithme existant et saisir le haut x, non?

De meilleures idées?

Answer 1

Si vous connaissez le nombre d'éléments à l'avance, il est assez trivial de calculer n nombres aléatoires dans cette plage, puis saisir ceux avec ces index.

Answer 2

Dans une autre réponse j'ai fourni un moyen de retourner a single random element à partir d'une séquence, en utilisant juste un seul passage.

Je suspect cela pourrait être ajusté raisonnablement facile à utiliser un tampon circulaire et sélectionner une séquence aléatoire d'une taille donnée, mais vous devriez être assez prudent pour obtenir les probabilités équilibrée.

Answer 3

Si vous utilisez Knuthe Shuffle, il est possible de faire une lecture aléatoire sur une partie de la liste. Donc, il n'est pas nécessaire de trier une liste entière juste pour obtenir n éléments aléatoires. Je ne sais pas si cela peut être fait efficacement dans vos contraintes puisque vous aurez encore besoin de convertir ce que vous saisissez dans une liste avant de pouvoir appliquer l'algorithme.

En substance, la stratégie consiste à attraper un élément aléatoire, l'échanger avec le premier élément de la liste. La prochaine fois que vous avez besoin d'un élément aléatoire, ignorez le premier.

Answer 4

Voici une autre idée:

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace RandomElements 
{ 
    class Program 
    { 
     static IEnumerable<int> GetRandomElements(IEnumerable<int> source, int count) 
     { 
      var random = new Random(); 
      var length = source.Count(); 
      var enumerator = source.GetEnumerator(); 

      if (length < count) 
      { 
       throw new InvalidOperationException("Seriously?"); 
      } 

      while (count > 0) 
      { 
       const int bias = 5; 
       var next = random.Next((length/bias) - count - bias) + 1; // To make sure we don't starve. 
       length -= next; 

       while (next > 0) 
       { 
        if (!enumerator.MoveNext()) 
        { 
         throw new InvalidOperationException("What, we starved out?"); 
        } 

        --next; 
       } 

       yield return enumerator.Current; 

       --count; 
      } 
     } 

     static void Main(string[] args) 
     { 
      var sequence = Enumerable.Range(1, 100); 
      var random = GetRandomElements(sequence, 10); 

      random.ToList().ForEach(Console.WriteLine); 
     } 
    } 
} 

Il n'a besoin que de passer par l'énumération une fois (si vous passez dans un ICollection, qui est, sinon il a besoin de connaître la longueur). Cela peut être utile s'il est coûteux de parcourir l'énumération ou de copier tous les éléments ou quoi que ce soit. Je ne suis pas un statisticien, un mathématicien ou un magicien, alors ne m'en tenez pas rigueur, mais je me suis rendu compte que sans le 'biais' introduit à la ligne 22, je pensais que je voulais en choisir plus à l'arrière. de la séquence. Peut-être que quelqu'un pourrait modifier les probabilités plus? Si l'énumération est vraiment coûteuse, vous pourriez la biaiser davantage vers l'avant.

Les commentaires sont les bienvenus.