Lecture aléatoire en utilisant IComparer
https://stackoverflow.com/questions/557911
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Tout d'abord, je ne sais au sujet de la lecture aléatoire Fisher-Yates. Mais disons que pour l'amour des arguments que je veux permettre à l'utilisateur de choisir une option de tri dans une liste déroulante. Cette liste comprendrait une option « aléatoire ». Sur la base du résultat de leur sélection, je veux juste substituer dans une instance IComparer pour mon genre. À quoi ressemblerait le IComparer comme?
Google apporte une pléthore de résultats imparfaits que tous prennent la forme suivante:
public class NaiveRandomizer<T> : IComparer<T>
{
private static Random rand = new Random();
public int Compare(T x, T y)
{
return (x.Equals(y))?0:rand.Next(-1, 2);
}
}
Cependant, cette mise en œuvre est biaisé et va même lancer une exception dans certaines circonstances. La polarisation peut être mise en évidence par le code suivant:
void Test()
{
Console.WriteLine("NaiveRandomizer Test:");
var data = new List<int>() {1,2,3};
var sortCounts = new Dictionary<string, int>(6);
var randomly = new NaiveRandomizer<int>();
for (int i=0;i<10000;i++)
{ //always start with same list, in _the same order_.
var dataCopy = new List<int>(data);
dataCopy.Sort(randomly);
var key = WriteList(dataCopy);
if (sortCounts.ContainsKey(key))
sortCounts[key]++;
else
sortCounts.Add(key, 1);
}
foreach (KeyValuePair<string, int> item in sortCounts)
Console.WriteLine(item.Key + "\t" + item.Value);
}
string WriteList<T>(List<T> list)
{
string delim = "";
string result = "";
foreach(T item in list)
{
result += delim + item.ToString();
delim = ", ";
}
return result;
}
Alors, comment pourriez-vous mettre en œuvre un IComparer<T> aléatoire qui a résolu ces problèmes? Il est permis d'exiger que chaque appel à .Sort() d'utiliser une instance IComparer séparée, comme je ne vois pas d'autre façon de le faire: les éléments doivent être comparés à l'aide d'une autre, la valeur réellement aléatoire, mais valeur doit aussi être cohérent pour un élément dans une opération de tri donné.
J'ai un début ici , mais il a été publié à la hâte, est très lent et ne retourne même pas toutes les sortes possibles (test montre qu'il a au moins éliminer les préjugés, si vous ne « t compter les options manquantes). Je ne pense pas O (n) performance comme Fisher-Yates, mais je ne veux quelque chose de raisonnable (n log n pour un petit-ish n), et je ne m'y attendais pas à montrer toutes sortes possibles. Malheureusement, ce lien est la réponse actuelle acceptée pour sa question et j'espère être en mesure de le remplacer par quelque chose d'un peu mieux.
Si rien d'autre, je veux que ce soit un aimant pour toutes les requêtes de Google à la recherche d'un IComparable qu'ils vont solution qui consisterait à s'y trouver au lieu de leur dire quelque part ailleurs d'utiliser la version incorrecte.
La solution 2
Une suggestion que je suis ailleurs était de créer une interface IArranger distincte qui décrit une seule opération à Organiser une collection. Cela peut fonctionner où IComparer / IComparable ne peut pas parce qu'il fonctionne sur une collection entière, au lieu des objets. Il pourrait ressembler à ceci:
public interface IArranger<T>
{
IEnumerable<T> Arrange(IEnumerable<T> items);
}
Alors je pourrais mettre en œuvre un Shuffle de l'interface IArranger en utilisant un algorithme approprié Fisher-Yates, et ont également mises en œuvre qui enveloppent chaque variétés de IEnumerable.Sort()/IComparable/IComparer supplémentaires que je me soucie. Cela pourrait ressembler à ceci:
public class ComparerArranger<T> : IArranger<T>
{
private IComparer<T> comparer;
public ComparableArranger(IComparer<T> comparer)
{
this.comparer = comparer;
}
public IEnumerable<T> Arrange(IEnumerable<T> items)
{
return items.OrderBy(i => i, comparer);
}
}
ou
//uses the default Comparer for the type (Comparer<T>.Default)
public class TypeArranger<T> : IArranger<T>
{
public IEnumerable<T> Arrange(IEnumerable<T> items)
{
return items.OrderBy(i => i);
}
}
ou
public class ShuffleArranger<T> : IArranger<T>
{
//naive implementation for demonstration
// if I ever develop this more completely I would try to
// avoid needing to call .ToArray() in here
// and use a better prng
private Random r = new Random();
public IEnumerable<T> Arrange(IEnumerable<T> items)
{
var values = items.ToArray();
//valid Fisher-Yates shuffle on the values array
for (int i = values.Length; i > 1; i--)
{
int j = r.Next(i);
T tmp = values[j];
values[j] = values[i - 1];
values[i - 1] = tmp;
}
foreach (var item in values) yield return item;
}
}
Pour une dernière étape, ajouter le support pour cela à tout IEnumerable via une méthode d'extension. Ensuite, vous obtenez toujours simple algorithme swapping temps d'exécution, vous avez une meilleure mise en œuvre de l'algorithme aléatoire, et le code pour l'utiliser semble naturel:
public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
return arranger.Arrange(items);
}
Autres conseils
Je suis un peu surpris dans ce fil combien de mauvaises réponses ont été affichées. Juste pour le bien des autres qui viennent avec une solution similaire à celui affiché par l'OP, le code suivant regarde correct:
int[] nums = new int[1000];
for (int i = 0; i < nums.Length; i++)
{
nums[i] = i;
}
Random r = new Random();
Array.Sort<int>(nums, (x, y) => r.Next(-1, 2));
foreach(var num in nums)
{
Console.Write("{0} ", num);
}
Cependant, le code lancera une exception de temps en temps, mais pas toujours. C'est ce qui le rend amusant de débogage :) Si vous avez suffisamment de fois, ou d'exécuter la procédure de tri dans une boucle quelque 50 fois, vous obtiendrez une erreur indiquant:
IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: '0' x's type: 'Int32' The IComparer: ''.
En d'autres termes, le tri rapide par rapport à un nombre x lui-même et a obtenu un résultat non nul. La solution évidente au code serait écrire:
Array.Sort<int>(nums, (x, y) =>
{
if (x == y) return 0;
else return r.NextDouble() < 0.5 ? 1 : -1;
});
Mais même cela ne fonctionne pas, parce qu'il ya des occasions où .NET compare 3 numéros les uns aux autres qui renvoient des résultats incohérents, tels que A> B, B> C et C> A (oups!). Peu importe si vous utilisez un Guid, GetHashCode, ou toute autre entrée aléatoire, une solution comme celle ci-dessus est encore mal.
Cela étant dit, Fisher-Yates est le moyen standard de tableaux brassage, donc il n'y a aucune raison d'utiliser IComparer en premier lieu. Fisher-Yates est O (n), alors que toute mise en œuvre à l'aide IComparer utilise un quicksort les scènes qui derrières a un temps de complexité O (n log n). Il est tout simplement pas une bonne raison de ne pas utiliser le bien connu, algorithme standard efficace pour résoudre ce genre de problème.
Cependant, si vous insistez vraiment sur l'utilisation d'un IComparer et un rand, puis appliquez vos données aléatoires avant vous triez. Cela nécessite une projection des données sur un autre objet afin que vous ne perdez pas vos données au hasard:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Pair<T, U>
{
public T Item1 { get; private set; }
public U Item2 { get; private set; }
public Pair(T item1, U item2)
{
this.Item1 = item1;
this.Item2 = item2;
}
}
class Program
{
static void Main(string[] args)
{
Pair<int, double>[] nums = new Pair<int, double>[1000];
Random r = new Random();
for (int i = 0; i < nums.Length; i++)
{
nums[i] = new Pair<int, double>(i, r.NextDouble());
}
Array.Sort<Pair<int, double>>(nums, (x, y) => x.Item2.CompareTo(y.Item2));
foreach (var item in nums)
{
Console.Write("{0} ", item.Item1);
}
Console.ReadKey(true);
}
}
}
Ou procurez-vous LINQy avec votre mauvaise auto:
Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
orderby r.NextDouble()
select x;
IComparer nécessitant un retour à zéro à un moment donné (pour les instances égales de T), rend mathématiquement impossible de créer un IComparer générique qui imitent un Fisher-Yates aléatoire statistiquement. Il y aura toujours un parti pris. Pour un vrai remaniement, tu ne veux jamais le forcer à retourner une valeur particulière.
Comment « bout tri basé sur un champ caché, qui est attribué au préalable une valeur aléatoire?
Pour donner suite à l'idée de James Curran: laisser le IComparer maintenir la « sorted » valeurs comme une liste; si une nouvelle valeur se produit, l'insérer dans la liste dans une position aléatoire; comparer par index de liste. Optimiser en maintenant la liste comme un arbre équilibré ou quelque chose. Chaque instance d'une telle IComparer maintiendra un ordre de tri cohérent et aléatoire de sorte que vous avez le choix de laisser votre tri aléatoire soit toujours le même ordre aléatoire ou un différent à chaque fois. modification mineure permettra même des éléments égaux à « classés » dans différentes positions de commande, si vous préférez lire cette façon « aléatoire ».
Une entreprise intéressante. Très probablement un mauvais usage / abus de IComparer.
Vous essayez de faire une sorte pondérée aléatoire en utilisant un mécanisme qui n'a pas été construit à cet effet.
Pourquoi ne pas mettre en œuvre votre propre routine de tri et de votre comparateur? Je sens que même cela serait insuffisant.
Ne pas le faire.
Tous les algorithmes proposés introduisent donc bien une sorte de parti pris dans la sortie (certains plus que d'autres).
@Princess et @Luke proposent le stockage d'un nombre aléatoire à côté des données. Cependant, car il est possible que deux de ces nombres aléatoires pourrait avoir la même valeur que l'autre, l'ordre de tri entre ces deux éléments sera biaisé déterministe
Le pire des cas pour ce serait si la routine de tri est « stable » (c'est que les objets qui sont considérés comme égaux sont toujours sortie dans le même ordre d'entrée dans). Array.Sort ne se produit pas stable (il utilise QuickSort en interne), mais il y a encore un préjugé qui se produit chaque fois que deux éléments ont la même valeur qui dépend de l'endroit où ils se trouvent dans l'entrée (et plus précisément où ils sont par rapport à celui du QuickSort pivot).
En tant que keyspace pour ce nombre aléatoire augmente, la probabilité d'une collision va vers le bas (avec une bonne source de hasard), mais gardez à l'esprit que le nombre de valeurs que vous triez monte, le paradoxe d'anniversaire dicte que le likelyhood d'au moins une paire d'entre eux va entrer en collision très rapidement.
Pour une clé entière, il y a 2 ^ 32 valeurs uniques pour la clé et même en supposant qu'il y ait une parfaite répartition homogène des valeurs aléatoires, avec 75.000 lignes, il y a une probabilité de 50% qu'il y aura une collision. Wikipedia .
L'approche de hachage cryptographique que vous proposiez a potentiellement un assez grand keyspace (160) bits pour faire la chance d'une collision négligeable, mais votre algorithme se décompose tout cela aléatoire vers le bas à un seul int avant de faire réellement le comparer ce qui annule le bénéfice de cette keyspace plus.
La meilleure approche consiste à associer une valeur « sortOrder » distincte avec chacun de vos éléments de données mélanger ces valeurs à l'aide d'un algorithme éprouvé, puis trier les résultats par cette valeur.
Si vous utilisez Array.Sort, il y a une surcharge qui prend un tableau de « clés » et un tableau de « valeurs ». La matrice de touches est triée normalement, mais à chaque fois une valeur dans la matrice de touches est déplacé, l'entrée correspondante dans la matrice de valeurs est également déplacé.
Quelque chose comme:
Something[] data;//populated somewhere
int[] keys = new int[data.Length];//or long if you might have lots of data
for(int i=0;i<keys.Length;++i) {
keys[i] = i;
}
Shuffle(keys);
Array.Sort(keys, data);
