Est-ce que Random and OrderBy est un bon algorithme de lecture aléatoire?

Question

J'ai lu un article sur divers algorithmes de mélange à Coding Horror . J'ai vu que quelque part les gens ont fait cela pour mélanger une liste:

 var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());
 

Est-ce un bon algorithme de mélange? Comment ça marche exactement? Est-ce une façon acceptable de le faire?

Answer 1

Il n'est pas une manière de brouiller que j'aime, principalement au motif que c'est O(n log n) pour aucune bonne raison quand il est facile à mettre en œuvre un O(n) shuffle. Le code de la question "œuvres" par essentiellement donné aléatoire (espérons-le unique!) nombre de chaque élément, puis de commander les éléments en fonction de ce nombre.

Je préfère Durstenfield de la variante de la shuffle de Fisher-Yates qui échange des éléments.

Mise en œuvre d'un simple, Shuffle extension de la méthode se composent essentiellement d'appel ToList ou ToArray sur l'entrée à l'aide d'un existant, la mise en œuvre de Fisher-Yates. (Passer dans l' Random comme paramètre pour rendre la vie généralement plus agréable.) Il y a beaucoup de mises en œuvre autour... j'ai probablement l'un dans une réponse quelque part.

La bonne chose à propos d'une telle extension de la méthode est qu'elle pourrait alors être très clair pour le lecteur de ce que vous êtes en train d'essayer de faire.

EDIT: Voici une mise en œuvre simple (pas de contrôle d'erreur!):

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length-1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

EDIT: Commentaires sur les performances ci-dessous m'a rappelé que nous pouvons retourner les éléments que nous avons shuffle:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        // ... except we don't really need to swap it fully, as we can
        // return it immediately, and afterwards it's irrelevant.
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

Ce sera désormais uniquement faire autant de travail que nécessaire.

Notez que dans les deux cas, vous devez être prudent au sujet de l'instance de Random vous utilisez:

• La création de deux instances de l' Random environ à la même heure, produira la même séquence de nombres aléatoires (lorsqu'il est utilisé de la même manière)
• Random n'est pas thread-safe.

J'ai un article sur Random qui va plus dans le détail sur ces questions et propose des solutions.

Answer 2

Ceci est basé sur Jon Skeet la réponse.

Dans sa réponse, le tableau est mélangé, puis retournée à l'aide d' yield. Le résultat net est que le tableau est conservé en mémoire pour la durée de foreach, ainsi que les objets nécessaires pour l'itération, et pourtant, le coût est tout au début, le rendement est à la base un vide boucle.

Cet algorithme est beaucoup utilisé dans les jeux, où les trois premiers éléments sont repris, et les autres ne seront nécessaires plus tard. Ma suggestion est d' yield les chiffres dès qu'ils sont échangés. Cela permettra de réduire le coût de démarrage, tout en gardant l'itération coût en O(1) (en gros 5 opérations par itération). Le coût total devrait rester le même, mais le déplacement lui-même serait plus rapide. Dans les cas où cela est appelé en tant que collection.Shuffle().ToArray() il ne sera théoriquement pas faire de différence, mais dans le cas d'utilisation il passera à la vitesse de démarrage. Aussi, ce serait faire l'algorithme utile pour les cas où vous avez seulement besoin de quelques objets uniques. Par exemple, si vous avez besoin de sortir de trois cartes d'un paquet de 52 cartes, vous pouvez appeler deck.Shuffle().Take(3) , et seulement trois swaps (bien que l'ensemble du tableau devra être copié en premier).

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length - 1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
        // we don't actually perform the swap, we can forget about the
        // swapped element because we already returned it.
    }

    // there is one item remaining that was not returned - we return it now
    yield return elements[0]; 
}

Answer 3

C'est probablly ok pour la plupart des fins, et presque toujours, il génère une véritable distribution aléatoire (sauf quand Aléatoire.Next() produit deux identiques entiers aléatoires).

Il fonctionne en attribuant à chaque élément de la série un nombre entier aléatoire, puis la commande de la séquence par ces entiers.

C'est tout à fait acceptable pour 99,9% des demandes (sauf si vous avez absolument besoin pour gérer le cas limite ci-dessus). Aussi, skeet son opposition à son exécution est valide, donc si vous êtes traînant une longue liste, vous pourriez ne pas vouloir l'utiliser.

Answer 4

Cela a été fait plusieurs fois auparavant. Recherchez Fisher-Yates sur StackOverflow.

Voici un exemple de code C # que j'ai écrit pour cet algorithme. Vous pouvez le paramétrer sur un autre type, si vous préférez.

 static public class FisherYates
{
        //      Based on Java code from wikipedia:
        //      http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
        static public void Shuffle(int[] deck)
        {
                Random r = new Random();
                for (int n = deck.Length - 1; n > 0; --n)
                {
                        int k = r.Next(n+1);
                        int temp = deck[n];
                        deck[n] = deck[k];
                        deck[k] = temp;
                }
        }
}
 

Answer 5

On dirait un bon algorithme de mélange, si vous n’êtes pas trop inquiet sur la performance. Le seul problème que je voudrais souligner est que son comportement n’est pas contrôlable, alors vous pouvez avoir un moment difficile de le tester.

Une option possible est d’avoir une graine doit être passé comme paramètre à la générateur de nombres aléatoires (ou le générateur aléatoire en tant que paramètre), ainsi vous pouvez avoir plus de contrôle et de tester plus facilement.