L'utilisation de Random et OrderBy est-elle un bon algorithme de mélange?

Ceci est basé sur Jon Skeet réponse .

dans cette réponse, le tableau est mélangé, puis retourné en utilisant yield . Le résultat net est que le tableau est gardé en mémoire pour la durée de foreach, ainsi que les objets nécessaires à l'itération, et pourtant le coût est tout au début - le rendement est essentiellement une boucle vide.

Cet algorithme est beaucoup utilisé dans les jeux, où les trois premiers éléments sont repris, et la d'autres ne seront nécessaires plus tard. Ma suggestion est de yield les chiffres dès qu'ils sont échangés. Cela réduira le coût de démarrage, tout en maintenant le coût d'itération à O(1) (essentiellement 5 opérations par itération). Le coût total resterait le même, mais le brassage lui-même serait plus rapide. Dans les cas où cela s'appelle collection.Shuffle().ToArray() , cela ne fera théoriquement aucune différence, mais dans les cas d'utilisation susmentionnés, cela accélérera le démarrage. Aussi, ce serait faire l' algorithme utile pour les cas où vous n'avez besoin que de quelques éléments uniques. Par exemple, si vous avez besoin de retirer trois cartes d'un deck de 52, Vous pouvez appeler deck.Shuffle().Take(3) et seulement trois swaps auront lieu (bien que le tableau entier devrait ê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]; 
}

à partir de cette citation de Skeet:

ce n'est pas une façon de mélanger que j'aime, surtout parce que C'est O(N log n) Pour aucune bonne raison quand il est facile de mettre en œuvre un O(N) mélange. Le code dans la question "fonctionne" en donnant fondamentalement un aléatoire ( espérons unique! ) à chaque élément, puis ordonnant les éléments en fonction de ce nombre.

je vais aller faire un peu de expliquer la raison pour le espérons unique!

Maintenant, à partir de la Énumérable.OrderBy :

cette méthode effectue un tri stable; c'est-à-dire, si les touches de deux éléments sont égales, l'ordre des éléments est préservé

C'est très important! Qu'advient-il si deux éléments de "recevoir" le même nombre aléatoire? Il arrive qu'ils restent dans la même ordre qu'ils sont dans le tableau. Maintenant, quelle est la possibilité pour que cela arrive? Il est difficile de calculer exactement, mais il y a le Problème d'Anniversaire c'est exactement ce problème.

maintenant, est-ce réel? Est-il vrai?

comme toujours, en cas de doute, écrivez quelques lignes de programme: http://pastebin.com/5CDnUxPG

ce petit bloc de code mélange un tableau de 3 éléments a un certain nombre de fois en utilisant L'algorithme de Fisher-Yates fait en arrière, L'algorithme de Fisher-Yates fait en avant (dans le wiki page il y a deux algorithmes de pseudo-code... Ils produisent des résultats équivalents, mais l'un est fait du premier au dernier élément, tandis que l'autre est fait du dernier au premier élément), le naïf faux algorithme de http://blog.codinghorror.com/the-danger-of-naivete / et en utilisant le .OrderBy(x => r.Next()) et le .OrderBy(x => r.Next(someValue)) .

Maintenant, Au Hasard.Suivant est

un entier signé de 32 bits qui est supérieur ou égal à 0 et inférieur à MaxValue.

donc c'est équivalent à

OrderBy(x => r.Next(int.MaxValue))

pour tester si ce problème existe, nous pourrions agrandir le tableau (quelque chose de très lent) ou simplement réduire la valeur maximale du générateur de nombres aléatoires ( int.MaxValue n'est pas un nombre" spécial"... C'est tout simplement un très grand nombre). En fin de compte , si l'algorithme n'est pas biaisé par la stabilité du OrderBy , alors n'importe quelle plage de valeurs devrait donner le même résultat.

le programme teste ensuite certaines valeurs, dans l'intervalle 1...4096. En regardant le résultat, il est clair que pour de faibles valeurs (< 128), l'algorithme est très biaisée (4-8%). Avec 3 valeurs, vous avez besoin d'au moins r.Next(1024) . Si vous faites le tableau plus grand (4 ou 5), alors même r.Next(1024) n'est pas suffisant. Je ne suis pas un expert en mélange et en mathématiques, mais je pense que pour chaque bit de longueur supplémentaire du tableau, vous avez besoin de 2 bits supplémentaires de valeur maximale (parce que le paradoxe de l'anniversaire est connecté au sqrt (numvalues)), de sorte que si la valeur maximale est 2^31, je dirais que vous devriez être en mesure de trier les tableaux jusqu'à 2^12/2^13 bits (4096-8192 éléments)

il est probablement ok pour la plupart des buts, et presque toujours il génère une distribution vraiment aléatoire (sauf quand aléatoire.Next () produit deux entiers aléatoires identiques).

il fonctionne en assignant chaque élément de la série un entier aléatoire, puis l'ordre de la séquence par ces entiers.

c'est tout à fait acceptable pour 99,9% des applications (à moins que vous ayez absolument besoin de gérer le boîtier de bord ci-dessus). De plus, skeet s'oppose à sa durée de fonctionnement est valide, donc si vous êtes traînant une longue liste, vous pourriez ne pas vouloir l'utiliser.

semble être un bon algorithme de mélange, si vous n'êtes pas trop inquiet sur la performance. Le seul problème que je ferais remarquer est que son comportement n'est pas contrôlable, donc vous pourriez avoir du mal à le tester.

une option possible est d'avoir une graine à passer comme paramètre au générateur de nombres aléatoires (ou le générateur aléatoire comme paramètre), de sorte que vous pouvez avoir plus de contrôle et le tester plus facilement.

C'est déjà arrivé plusieurs fois. Cherchez Fisher-Yates sur StackOverflow.

Voici une exemple de code C# j'ai écrit pour cet algorithme. Vous pouvez 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;
                }
        }
}

j'ai trouvé la réponse de Jon Skeet entièrement satisfaisante, mais le Robo-scanner de mon client signalera n'importe quel cas de Random comme un défaut de sécurité. Donc je l'ai échangé pour System.Security.Cryptography.RNGCryptoServiceProvider . En prime, il corrige ce problème de sécurité du thread qui a été mentionné. Par contre, RNGCryptoServiceProvider a été mesuré 300 fois plus lentement que Random .

Utilisation:

using (var rng = new RNGCryptoServiceProvider())
{
    var data = new byte[4];
    yourCollection = yourCollection.Shuffle(rng, data);
}

méthode:

/// <summary>
/// Shuffles the elements of a sequence randomly.
/// </summary>
/// <param name="source">A sequence of values to shuffle.</param>
/// <param name="rng">An instance of a random number generator.</param>
/// <param name="data">A placeholder to generate random bytes into.</param>
/// <returns>A sequence whose elements are shuffled randomly.</returns>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data)
{
    var elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        rng.GetBytes(data);
        var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

légèrement sans rapport, Mais voici une méthode intéressante (qui même si elle est vraiment excessible, a vraiment été mis en œuvre) pour la génération vraiment aléatoire de rouleaux de dés!

Dice-O-Matic

la raison pour laquelle je poste ceci ici, est qu'il fait quelques points intéressants sur la façon dont ses utilisateurs ont réagi à l'idée d'utiliser des algorithmes pour mélanger, sur de véritables dés. Bien sûr, dans le monde réel, une telle solution est uniquement pour les extrémités vraiment extrêmes du spectre où le hasard a un si grand impact et peut-être l'impact affecte l'argent ;).

je dirais que beaucoup de réponses ici comme" cet algorithme mélange en générant une nouvelle valeur aléatoire pour chaque valeur dans une liste, puis en ordonnant la liste par ces valeurs aléatoires " pourrait être très faux!

je pense que cela n'attribue pas de valeur aléatoire à chaque élément de la collection source. Au lieu de cela, il pourrait y avoir un algorithme de tri tournant comme Quicksort qui appellerait une fonction de comparaison approximativement n log n Temps. Une sorte d'algortihm s'y attend vraiment. comparer-fonction pour être stable et toujours retourner le même résultat!

ne se pourrait-il pas que le IEnumerableSorter appelle une fonction de comparaison pour chaque étape de l'algorithme de par exemple quicksort et appelle à chaque fois la fonction x => r.Next() pour les deux paramètres sans les mettre en cache!

dans ce cas, vous pourriez vraiment gâcher l'algorithme de tri et le rendre bien pire que les attentes que l'algorithme est construit sur. Bien sûr, il finira par devenir stable et retourner quelque chose.

je pourrais le vérifier plus tard en mettant la sortie de débogage dans une nouvelle fonction" Next " donc voir ce qui se passe. Dans Reflector Je ne pouvais pas immédiatement savoir comment cela fonctionne.

vous cherchez un algorithme? Vous pouvez utiliser ma classe ShuffleList :

class ShuffleList<T> : List<T>
{
    public void Shuffle()
    {
        Random random = new Random();
        for (int count = Count; count > 0; count--)
        {
            int i = random.Next(count);
            Add(this[i]);
            RemoveAt(i);
        }
    }
}

alors, utilisez - le comme ceci:

ShuffleList<int> list = new ShuffleList<int>();
// Add elements to your list.
list.Shuffle();

comment ça marche?

prenons une première liste triée des 5 premiers entiers: { 0, 1, 2, 3, 4 } .

la méthode commence par compter le nubmer des éléments et l'appelle count . Ensuite ,avec count décroissant sur chaque pas, il prend un nombre aléatoire entre 0 et count et le déplace à la fin de la liste.

dans l'exemple suivant, les éléments qui pourraient être déplacés sont en italique , l'élément choisi est en gras :

0 1 2 3 4

0 1 2 3 4

0 1 2 4 3

0 1 2 4 3

1 2 4 3 0

1 2 4 3 0

1 2 3 0 4

1 2 3 0 4

2 3 0 4 1

2 3 0 4 1

3 0 4 1 2

cet algorithme mélange en générant une nouvelle valeur aléatoire pour chaque valeur d'une liste, puis en ordonnant la liste par ces valeurs aléatoires. Pensez - y comme ajouter une nouvelle colonne à une table en mémoire, puis la remplir de GUIDs, puis la Trier par cette colonne. Ressemble un moyen efficace pour moi (surtout avec le lambda de sucre!)

temps de démarrage pour exécuter le code avec effacer tous les threads et cache chaque nouveau test,

premier code infructueux. Il fonctionne sur LINQPad. Si vous suivez pour tester ce code.

Stopwatch st = new Stopwatch();
st.Start();
var r = new Random();
List<string[]> list = new List<string[]>();
list.Add(new String[] {"1","X"});
list.Add(new String[] {"2","A"});
list.Add(new String[] {"3","B"});
list.Add(new String[] {"4","C"});
list.Add(new String[] {"5","D"});
list.Add(new String[] {"6","E"});

//list.OrderBy (l => r.Next()).Dump();
list.OrderBy (l => Guid.NewGuid()).Dump();
st.Stop();
Console.WriteLine(st.Elapsed.TotalMilliseconds);

liste.OrderBy(x = > R. Suivant ()) utilise 38.6528 ms

liste.OrderBy (x => Guid.NewGuid ()) utilise 36.7634 ms (recommandé D'après MSDN.)

la deuxième fois que tous les deux utilisent dans le même temps.

EDIT: Code de TEST sur Intel Core i7 4@2.1GHz, Ram 8 GB DDR3 @1600, HDD SATA 5200 rpm avec [données: www.dropbox.com/s/pbtmh5s9lw285kp/data]

using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;

namespace Algorithm
{
    class Program
    {
        public static void Main(string[] args)
        {
            try {
                int i = 0;
                int limit = 10;
                var result = GetTestRandomSort(limit);
                foreach (var element in result) {
                    Console.WriteLine();
                    Console.WriteLine("time {0}: {1} ms", ++i, element);
                }
            } catch (Exception e) {
                Console.WriteLine(e.Message);
            } finally {
                Console.Write("Press any key to continue . . . ");
                Console.ReadKey(true);
            }
        }

        public static IEnumerable<double> GetTestRandomSort(int limit)
        {
            for (int i = 0; i < 5; i++) {
                string path = null, temp = null;
                Stopwatch st = null;
                StreamReader sr = null;
                int? count = null;
                List<string> list = null;
                Random r = null;

                GC.Collect();
                GC.WaitForPendingFinalizers();
                Thread.Sleep(5000);

                st = Stopwatch.StartNew();
                #region Import Input Data
                path = Environment.CurrentDirectory + "\data";
                list = new List<string>();
                sr = new StreamReader(path);
                count = 0;
                while (count < limit && (temp = sr.ReadLine()) != null) {
//                  Console.WriteLine(temp);
                    list.Add(temp);
                    count++;
                }
                sr.Close();
                #endregion

//              Console.WriteLine("--------------Random--------------");
//              #region Sort by Random with OrderBy(random.Next())
//              r = new Random();
//              list = list.OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with OrderBy(Guid)
//              list = list.OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with Parallel and OrderBy(random.Next())
//              r = new Random();
//              list = list.AsParallel().OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with Parallel OrderBy(Guid)
//              list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with User-Defined Shuffle Method
//              r = new Random();
//              list = list.Shuffle(r).ToList();
//              #endregion

//              #region Sort by Random with Parallel User-Defined Shuffle Method
//              r = new Random();
//              list = list.AsParallel().Shuffle(r).ToList();
//              #endregion

                // Result
//              
                st.Stop();
                yield return st.Elapsed.TotalMilliseconds;
                foreach (var element in list) {
                Console.WriteLine(element);
            }
            }

        }
    }
}

Description du résultat: https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG

Résultat: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

Conclusion:

Hypothèse: LINQ OrderBy(R. Next ()) et OrderBy (Guid.NewGuid ()) ne sont pas pires que la méthode de mélange définie par L'utilisateur dans la première Solution.

réponse: ce sont des contradictions.