Tri par Random.Next()

Question

Dans this question une des suggestions est de trier une liste par Random.Next().

Je suppose (peut-être à tort) qu'il propose ce

public static IEnumerable<T> RandomSort<T>(this IEnumerable<T> items) 
    { 
     Random r = new Random(); 
     var a = items.ToArray(); 
     Array.Sort(a, (t1, t2) => (r.Next()%2==0)?-1 : 1); 
     return a; 
    } 

(Oui, il y a déjà une fonction Array.RandomShuffle qui vous évidemment utiliser à la place qui n'est pas la question.)

EDIT: L'affiche a clarifié la réponse. Il suggérait l'utilisation de la clause OrderBy

La question est, est le code ci-dessus (Using Array.Sort()) sûr d'exécuter?

Mon problème est qu'il enfreindrait une loi fondamentale de prédicats de tri:

si (a < b) et (b < c) puis (a < c)

Il est même pas garantir que si (un < b) puis (un < b) la prochaine fois que vous demandez.

Cela vous mènerait-il dans un territoire de "comportement non défini"? Par exemple, il pourrait tomber en panne ou tomber dans une boucle infinie en fonction de la séquence de nombres que retourne Random()?

Answer 1

Utilisez simplement un mélange aléatoire.

http://www.techtalkz.com/c-c-sharp/66613-shuffle-collection.html

Answer 2

Ceci est un dispositif utile pour créer une permutation aléatoire de la liste. Pour une permutation donnée, il est absolument vrai que si a est avant b et b est avant c alors a est avant c.

Une autre façon d'y penser est la suivante: si vous semez un générateur de nombres aléatoires avec la même graine à chaque fois, il produira toujours le même ordre. Vous pouvez donc penser à chaque graine du générateur de nombres aléatoires comme produisant un ordre (éventuellement) différent de la liste.

Il est même pas garantir que si (a < b) puis (a < b) la prochaine fois que vous demandez.

C'est très bien. Mais comme expliqué ci-dessus si nous ensemençons le générateur de nombres aléatoires avec la même graine et le présentons à Array.Sort comme dans votre exemple de code dans le même état, il produira le même ordre.

Answer 3

la façon dont ça a l'air de fonctionner est demandé une seule fois, puis chaque requête suivante sur cette valeur est la même.

ce serait comme ajouter une colonne supplémentaire à une table, en remplissant chaque champ avec un nombre aléatoire, puis en ordonnant par cette colonne.

Answer 4

Vous avez raison de dire que l'utilisation d'une fonction de nombre aléatoire pour le tri est un moyen facile de rompre les exigences formelles généralement imposées aux fonctions de tri, y compris celles que vous avez mentionnées.

L'implémentation actuelle de LINQ semble calculer toutes les clés de tri à l'avance. Le code suivant montre que les clés de tri sont obtenues séquentiellement et exactement une fois. Ceci est probablement une mise en œuvre judicieuse car elle évite les scénarios problématiques qui vous inquiètent.

Néanmoins, je ne me fierais pas sur ce comportement (il n'est pas documentée dans MSDN pour Enumerable.OrderBy.

public void Test() 
    { 
     int[] nums = Enumerable.Range(1, 100).ToArray(); 
     var sorted = from i in nums orderby Display(i) select i; 
     sorted.ToArray(); 
    } 

    private static int Display(int i) 
    { 
     Console.WriteLine(i); 
     return i; 
    } 

(Le code imprime ci-dessus 1 à 100 séquentiellement, montrant comment orderby évalue les clés de tri.)

Answer 5

juste pour faire une observation rapide, comme je l'ai juste essayé de faire une telle sorte aléatoire en utilisant le code suivant (pour obtenir des tests unitaires pour exécuter dans un ordre aléatoire):

Action<object>[] tests = new Action<object>[] { 
    delegate { SearchStringByTree(SOURCE, distinctor.Keys, out treeResults, out treeTicks); }, 
    delegate { SearchStringByIndexOf(SOURCE, distinctor.Keys, out indexOfResults, out indexOfTicks); }, 
    delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.UTF8, TERMS), out utf8Results, out utf8Ticks); }, 
    delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.ASCII, TERMS), out asciiResults, out asciiTicks); } 
}; 
Random r = new Random(); 
Array.Sort(tests, delegate { return r.Next(-1, 2); }); 

j'ai eu au hasard les éléments suivants ArgumentException:

IComparer (or the IComparable methods it relies upon) did not return zero 
when Array.Sort called x. CompareTo(x). x: '' x's type: 'Action`1' 
The IComparer: 'System.Array+FunctorComparer`1[System.Action`1[System.Object]]'.

Il semble ne règle affirme l'égalité sur les articles qu'il sait être la même (en supposant par object.ReferenceEquals) et, si le comparateur ne retourne pas 0 pour ceux-là qu'il sait devrait être égal, il invalide tout le genre.