Optimale requête LINQ pour obtenir aléatoires de la sous-collection - Shuffle

S'il vous plaît suggérer une façon la plus simple d'obtenir un aléatoire mélangées collection du comte 'n' à partir d'une collection ayant N éléments. où n <= N

InformationsquelleAutor Jobi Joy | 2009-10-30
  1. 37

    Une autre option est d'utiliser OrderBy et de trier sur un GUID de la valeur, vous pouvez le faire en utilisant:

    var result = sequence.OrderBy(elem => Guid.NewGuid());

    J'ai fait quelques tests empiriques pour me convaincre moi-même que ci-dessus génère une distribution aléatoire (ce qui semble le faire). Vous pouvez voir mes résultats à Les Techniques au Hasard et la Réorganisation d'un Tableau.

    • Cette solution constitue une violation du contrat de orderby, plus précisément, qu'un objet donné a une clé constante tout au long de la sorte. Si cela fonctionne, il le fait par le seul hasard, et pourrait se briser dans de futures versions du framework. Pour plus de détails, voir blogs.msdn.com/b/ericlippert/archive/2011/01/31/...
    • Bonne prise. Cependant, si cela était engagé dans une véritable collection, telles que l'ajout .ToList() ou .ToArray() à la fin -, alors il n'y a aucune chance de la collection traitées/itération du code Linq plus d'une heure pour effectuer le tri. J'imagine que ce serait survivre les futures mises à jour, car il serait prévisible de l'instantané.
    • Je viens de tombé sur cette page et pense que c'est génial, mais je ne comprends pas le commentaire. ce qui pourrait aller mal dans l'utilisation de cette méthode de lecture aléatoire d'une collection (je ne demande pas que sarcastique, je suis vraiment curieux de connaître les possibilités)?
    • Si vous regardez du point de vue de ces folles fonctionnelle programmeurs, cette utilisation de OrderBy ne pas violer le contrat, c'est juste que la cohérence de la clé unique est une fonction de toutes les semences utilisées pour générer le GUID, il est donc très difficile de les repérer sa cohérence. Pour une machine, le point dans le temps, etc, vous obtiendrez toujours le même GUID. Je sais qu'il s'étend à l'idée de le contrat un peu, mais en théorie, c'est du son, je pense. Peut-être que certains FP les gens peuvent commenter davantage.
    • il n'y a pas de problèmes pratiques, c'est juste que, théoriquement, il pourrait être considéré comme un abus de OrderBy parce que vous ne pouvez pas obtenir des résultats reproductibles (enfin, pas sans un diable de beaucoup de travail). La chose est, vous ne voulez pas l'obtention de résultats reproductibles dans ce cas.
    • Le problème ici n'est pas que la clé n'est pas compatible. John Melville a mal lu mon article; que l'article note que la création d'un comparaison - qui est, de ce point est plus grand, plus petit ou égal à l'autre -- qui est incompatible viole le contrat de la méthode de Tri. Cette réponse est fausse pour une toute autre raison: Guid ne sont garantis d'être unique, de leur caractère aléatoire est un détail d'implémentation, vous ne devriez pas compter sur.
    • En particulier, il est légal pour les guid pour être généré séquentiellement à partir d'un premier élément aléatoire; ce qui fait encore de bonnes garanties de l'unicité. Tout simplement parce que le générateur de guid aujourd'hui n'est pas réellement générer séquentielle guid jamais est un détail d'implémentation sujet à changement, et si il ne change pas, puis tout à coup, votre "shuffle" est "brouiller" les choses dans l'ordre à chaque fois. Utiliser les guid pour générer de l'unicité, jamais aléatoire. Utiliser une classe conçu pour générer de l'aléatoire pour le hasard.

    InformationsquelleAutor Scott Mitchell
  2. 102

    Plus de mquander la réponse de Dan Blanchard commentaire, voici une LINQ-amicale de la méthode d'extension qui effectue un De Fisher-Yates-Durstenfeld shuffle:

    //take n random items from yourCollection
var randomItems = yourCollection.Shuffle().Take(n);

//...

public static class EnumerableExtensions
{
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
    {
        return source.Shuffle(new Random());
    }

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (rng == null) throw new ArgumentNullException("rng");

        return source.ShuffleIterator(rng);
    }

    private static IEnumerable<T> ShuffleIterator<T>(
        this IEnumerable<T> source, Random rng)
    {
        var buffer = source.ToList();
        for (int i = 0; i < buffer.Count; i++)
        {
            int j = rng.Next(i, buffer.Count);
            yield return buffer[j];

            buffer[j] = buffer[i];
        }
    }
}
    • +1 Linqy et efficace. Coup de chapeau 🙂
    • Est-ce moi ou est-ce de cette méthode vis de l'indice de la liste? Chaque fois que l'utilisation d'elementAt() après avoir déplacé le résultat que j'obtiens est totalement inattendu...
    • La méthode renvoie un paresseusement évalué séquence. Si vous ne seq.Shuffle().ElementAt(n) plusieurs fois, puis, vous êtes re-brassage à chaque fois, donc il est probable que vous aurez un autre élément à la position n. Si vous voulez shuffle après ensuite, vous avez besoin de stocker la séquence en béton collection d'un certain type: par exemple, var list = seq.Shuffle().ToList(). Ensuite, vous pouvez faire list.ElementAt(n) aussi souvent que vous le souhaitez, ou simplement list[n] -- et vous obtiendrez toujours le même élément.
    • Ah merci! Va l'utiliser. Suis encore assez novice en C# et LINQ, j'ai donc été un peu dérouté par la suite j'ai été faire :-).
    • Quel est l'avantage d'avoir .ShuffleIterator() au lieu de mettre ce code dans .Shuffle()? Et puisque vous appelez .ToList(), n'est-ce pas à la parcourir l'ensemble de la collection plutôt que de simplement le montant demandé par .Take(n)? J'ai l'intuition que la première question peut répondre à ma deuxième question.
    • Cela donne des résultats peu fiables. Je reçois un élément différent à chaque fois que j'appel myList.ElementAt(0). Je reçois une autre chaîne chaque fois que j'appelle string.Join(",", myList).
    • C'est probablement parce que ces Shuffle méthodes retournent un paresseux IEnumerable<T> qui sera réévalué chaque fois que vous l'utilisez dans un string.Join ou ElementAt appel. C'est juste la nature de IEnumerable<T>; si vous voulez le comportement d'un béton de la collection, alors vous devriez vraiment créer un béton collection en appelant ToArray ou ToList sur le résultat de la Shuffle appel.
    • Est l'aide de .Shuffle() thread-safe? Je ne vois pas pourquoi il ne devrait pas être, mais j'obtiens des résultats étranges... plusieurs threads semblent tirer la même shuffle résultats.
    • Désolé d'intervenir, un an plus tard, mais le point de ShuffleIterator est de laisser Shuffle effectuer la validation d'arguments à l'avant, plutôt que de s'en remettre jusqu'à MoveNext est d'abord appelée sur l'énumérateur (qui peut-être jamais, ou dans le code qui n'est pas l'attendre). Voir msmvps.com/blogs/jon_skeet/archive/2008/03/02/...
    • Si vous utilisez la version qui ne prend pas une instance de Hasard, il permettra de créer un pour vous. Les Instances de l'Aléatoire est créé près dans le temps, le risque de l'utilisation de la même semence, et donc de donner la même séquence de nombres aléatoires. Si vous passez par la même instance de l'Aléatoire sur les différents threads, vous obtiendrez des résultats imprévisibles parce que les instances de Hasard ne sont pas thread-safe. Vous devez créer votre Aléatoires instances avec des graines, et ne pas les partager entre les threads.
    • Je suis d'accord avec gilly3 qu'il nous semble que la collecte est en train d'être remanié, plutôt que de les n résultats demandés.

    InformationsquelleAutor LukeH
  3. 13

    Ce qui a quelques problèmes avec "random biais" et je suis sûr que c'est pas optimal, c'est une autre possibilité:

    var r = new Random();
l.OrderBy(x => r.NextDouble()).Take(n);
    • Ce n'est pas tout aléatoire biais d'autres que tout insignifiant biais de Random lui-même. Il est également très efficace.
    • Venu ici pour le suggérer. Ce doit être la accepté de répondre.
    InformationsquelleAutor
  4. 6

    Shuffle la collection dans un ordre aléatoire et prendre la première n les éléments de la suite.

    • Notez que vous n'avez pas entièrement aléatoire de la collection n < N. il Vous suffit de parcourir Durstenfeld l'algorithme de n fois, et de prendre les n derniers éléments de l' (partiellement) mélangées résultat.
    InformationsquelleAutor mqp
  5. 0

    Un peu moins aléatoire, mais efficace:

    var rnd = new Random();
var toSkip = list.Count()-n;

if (toSkip > 0)
    toSkip = rnd.Next(toSkip);
else
    toSkip=0;

var randomlySelectedSequence = list.Skip(toSkip).Take(n);
    InformationsquelleAutor Majid
  6. -1

    J'écris ceci remplace la méthode:

    public static IEnumerable<T> Randomize<T>(this IEnumerable<T> items) where T : class
{
     int max = items.Count();
     var secuencia = Enumerable.Range(1, max).OrderBy(n => n * n * (new Random()).Next());

     return ListOrder<T>(items, secuencia.ToArray());
}

private static IEnumerable<T> ListOrder<T>(IEnumerable<T> items, int[] secuencia) where T : class
        {
            List<T> newList = new List<T>();
            int count = 0;
            foreach (var seed in count > 0 ? secuencia.Skip(1) : secuencia.Skip(0))
            {
                newList.Add(items.ElementAt(seed - 1));
                count++;
            }
            return newList.AsEnumerable<T>();
        }

    Puis, j'ai ma liste de source (tous les articles)

    var listSource = p.Session.QueryOver<Listado>(() => pl)
                        .Where(...);

    Enfin, je l'appelle "Aléatoire" et je suis aléatoires de la sous-collection d'éléments, dans mon cas, 5 éléments:

    var SubCollection = Randomize(listSource.List()).Take(5).ToList();
    • Vous perdez la mémoire, par la création d' newList. Peut-être envisager d'utiliser yield return à l'intérieur de la foreach déclaration.
    • La ligne Enumerable.Range(1, max).OrderBy(n => n * n * (new Random()).Next()) est terrible - c'est pas aléatoire du tout. l'appel de new Random()).Next() comme ça va juste retourner le même nombre dans la plupart des cas et la n * n fait le nombre biaisée - et, éventuellement, pourrait provoquer un débordement des exceptions.
    InformationsquelleAutor Hernaldo Gonzalez
  7. -3

    Désolé pour les vilaines code :-), mais

    
var result =yourCollection.OrderBy(p => (p.GetHashCode().ToString() + Guid.NewGuid().ToString()).GetHashCode()).Take(n);
    • p.GetHashCode().ToString() + Guid.NewGuid().ToString()).GetHashCode() n'est pas aléatoire. Il peut paraître aléatoire, mais il ne l'est pas. Vous devez utiliser un générateur de nombres aléatoires pour l'aléatoire de données, les scientifiques ont conçu spécifiquement pour être aussi aléatoire que possible.
    InformationsquelleAutor sh1ng