Mischen mit IComparer

Question

Zunächst weiß ich über die Fisher-Yates Shuffle. Aber lassen Sie uns Argumente sagen, dass ich dem Benutzer erlauben möchte, eine Sortieroption aus einer Dropdown-Liste auszuwählen. Diese Liste würde eine "zufällige" Option enthalten. Basierend auf dem Ergebnis ihrer Auswahl möchte ich nur eine IComparer-Instanz für meine Sorte einsetzen. Wie würde der IComparer aussehen?

Google bringt eine Fülle von fehlerhaften Ergebnissen, das all diese Form annehmen:

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); 
    } 
} 

jedoch, dass die Umsetzung vorgespannt ist, und wird sogar eine Ausnahme unter bestimmten Umständen werfen. Die Vorspannung kann mit dem folgenden Code demonstriert werden:

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; 
} 

So wie könnte man ein zufälliges IComparer<T> implementieren, die diese Probleme gelöst? Es ist zulässig, dass jeder Aufruf an .Sort() eine separate IComparer-Instanz verwendet, da ich keine andere Möglichkeit sehe: Elemente müssen mit einem anderen, wirklich zufälligen Wert verglichen werden, aber dieser Wert muss auch sein für einen Artikel innerhalb einer Sortieroperation konsistent sein.

Ich habe einen Start here, aber es war in Eile geschrieben, ist extrem langsam, und kehrt nicht sogar alle möglichen Sorten (Tests zeigen, dass es am wenigsten entbindet bei bias, wenn Sie die nicht zählen fehlende Optionen). Ich erwarte keine O (n) Leistung wie Fisher-Yates, aber ich möchte etwas Vernünftiges (n log n für ein kleines i n), und ich erwarte, dass es alle möglichen Arten zeigt. Leider ist dieser Link die aktuell akzeptierte Antwort für seine Frage und ich hoffe, dass ich ihn durch etwas Besseres ersetzen kann.

Wenn nichts anderes, möchte ich, dass dies ein Magnet für all diese Google-Abfragen auf der Suche nach einer IComparable-Lösung ist - dass sie hier landen anstatt irgendwo anders zu sagen ihnen die falsche Version zu verwenden.

Answer 1

Ein Vorschlag, den ich woanders bekam, war, eine separate IArranger-Schnittstelle zu erstellen, die eine einzelne Operation zu einer Sammlung beschreibt. Dies kann dort funktionieren, wo IComparer/IComparable nicht möglich ist, da es sich auf eine gesamte Sammlung statt auf einzelne Elemente bezieht. Es könnte wie folgt aussehen:

public interface IArranger<T> 
{ 
    IEnumerable<T> Arrange(IEnumerable<T> items); 
} 

Dann habe ich eine Shuffle von der IArranger Schnittstelle implementieren könnte eine richtige Fisher-Yates-Algorithmus verwendet, und auch Implementierungen haben, dass jede zusätzliche IEnumerable.Sort()/IComparable/IComparer Sorten wickeln, die mich interessiert. Das könnte wie folgt aussehen:

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); 
    } 
} 

oder

//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); 
    } 
} 

oder

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; 
    } 
} 

Für einen abschließenden Schritt, ich die Unterstützung für diese zu einer IEnumerable über ein Verlängerungsverfahren.Dann noch Sie die einfache Laufzeit Algorithmus Swapping bekommen, haben Sie eine bessere Umsetzung des Shuffle-Algorithmus und den Code zu verwenden, es fühlt sich natürlich:

public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger) 
{ 
    return arranger.Arrange(items); 
} 

Answer 2

Wie erfolgt die Sortierung anhand eines versteckten Feldes, dem ein zufälliger Wert zugewiesen wurde?

Answer 3

Ich war etwas überrascht in this thread, wie viele falsche Antworten geschrieben wurden. Gerade im Interesse des anderen, die mit einer Lösung ähnlich den von der OP veröffentlicht kommen, der folgende Code sieht richtig:

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); 
} 

Allerdings wird der Code eine Ausnahme gelegentlich werfen, aber nicht immer. Das ist, was macht es Spaß zu debuggen :) Wenn Sie es oft genug ausgeführt werden, oder die Sortierverfahren in einer Schleife 50 oder so mal ausführen, erhalten Sie eine Fehlermeldung erhalten, die besagt:

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: ''.

Mit anderen Worten, die schnelle Sortierung verglich einige Zahlen x mit sich selbst und erhielt ein Ergebnis ungleich Null. Die offensichtliche Lösung, um den Code schreiben würde sein:

Array.Sort<int>(nums, (x, y) => 
    { 
     if (x == y) return 0; 
     else return r.NextDouble() < 0.5 ? 1 : -1; 
    }); 

Aber auch dies nicht funktioniert, denn es gibt Gelegenheiten, bei denen .NET vergleicht 3 Zahlen gegeneinander, die inkonsistente Ergebnisse zurückgeben, wie A> B, B > C und C> A (oops!). Ganz gleich, ob Sie Guid, GetHashCode oder andere zufällig generierte Eingaben verwenden, eine Lösung wie die oben gezeigte ist immer noch falsch.

---

Mit diesem wird gesagt, Fisher-Yates ist der normale Weg Anordnungen von schlurfenden, also gibt es keinen wirklichen Grund, IComparer in erster Linie zu verwenden. Fisher-Yates ist O (n), während jede Implementierung, die IComparer verwendet, einen Quicksort hinter den Szenen verwendet, der eine Zeitkomplexität von O (n log n) aufweist. Es gibt einfach keinen guten Grund, nicht den bekannten, effizienten Standardalgorithmus zu verwenden, um diese Art von Problem zu lösen.

Wenn Sie jedoch wirklich darauf bestehen, einen IComparer und einen Rand zu verwenden, dann wenden Sie Ihre zufälligen Daten vor Sie sortieren. Dies erfordert eine Projektion der Daten auf ein anderes Objekt, so dass Sie Ihre Zufallsdaten nicht verlieren:

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); 
     } 
    } 
} 

Oder bekommen LINQy mit Ihrem schlechten Selbst:

Random r = new Random(); 
var nums = from x in Enumerable.Range(0, 1000) 
      orderby r.NextDouble() 
      select x; 

Answer 4

IComparer erfordern eine Null-Rückkehr an Irgendein Punkt (für gleiche Fälle von T), macht es mathematisch unmöglich, einen generischen IComparer zu erstellen, der statistisch eine Fisher-Yates Shuffle nachahmen wird. Es wird immer eine Voreingenommenheit geben. Für einen echten Shuffle möchten Sie niemals einen bestimmten Wert zurückgeben.

Answer 5

Um James Currans Idee zu folgen: Lassen Sie den IComparer die "sortierten" Werte als eine Liste beibehalten; Wenn ein neuer Wert auftritt, fügen Sie ihn an einer zufälligen Position in die Liste ein; Vergleichen nach Listenindex. Optimieren Sie, indem Sie die Liste als ausgewogenen Baum oder etwas beibehalten. Jede Instanz eines solchen IComparers behält eine konsistente und zufällige Sortierreihenfolge bei, so dass Sie die Wahl haben, dass Ihre zufällige Sortierung immer die gleiche zufällige Reihenfolge oder eine andere sein muss. Geringfügige Änderungen ermöglichen es sogar, gleiche Elemente in verschiedene Reihenfolgepositionen zu "sortieren", wenn Sie es vorziehen, auf diese Weise "zufällig" zu lesen.

Answer 6

Ein interessantes Unterfangen. Höchstwahrscheinlich ein Missbrauch/Missbrauch von IComparer.

Sie versuchen, eine zufällige gewichtete Sortierung durchzuführen, indem Sie einen Mechanismus verwenden, der nicht für diesen Zweck erstellt wurde.

Warum implementieren Sie nicht Ihre eigene Sortierroutine und Ihren eigenen Vergleicher? Ich habe das Gefühl, dass selbst das nicht ausreichen würde.

Answer 7

Sie es nicht tun.

Alle bisher vorgeschlagenen Algorithmen führen zu einer gewissen Verzerrung in der Ausgabe (einige größer als andere).

@Princess und @Luke schlagen vor, eine Zufallszahl neben den Daten zu speichern. Da jedoch die Möglichkeit besteht, dass zwei dieser Zufallszahlen den gleichen Wert haben wie der andere, wird die Sortierreihenfolge zwischen diesen beiden Elementen deterministisch verzerrt sein. Der schlechteste Fall wäre, wenn die Sortierroutine "stabil" wäre "(Das heißt, Objekte, die als gleich betrachtet werden, werden immer in der Reihenfolge ausgegeben, in der sie eingegeben wurden). Array.Sort ist nicht stabil (es verwendet intern QuickSort), aber es gibt immer noch eine Verzerrung, die auftritt, wenn zwei Elemente denselben Wert haben, der davon abhängt, wo sie sich in der Eingabe befinden (und insbesondere, wo sie relativ zu den QuickSorts sind) Drehpunkt). Wenn der Schlüsselraum für diese Zufallszahl ansteigt, sinkt die Wahrscheinlichkeit einer Kollision (mit einer guten Quelle von Zufälligkeit), aber bedenken Sie, dass, wenn die Anzahl der Werte, die Sie sortieren, ansteigt, das Geburtstagsparadox dies vorschreibt die Wahrscheinlichkeit, dass mindestens ein Paar unter ihnen kollidiert, steigt sehr schnell an.

Für einen Integer-Schlüssel gibt es 2^32 eindeutige Werte für den Schlüssel, und selbst bei einer perfekt gleichmäßigen Verteilung von Zufallswerten mit 75.000 Zeilen besteht eine Wahrscheinlichkeit von 50%, dass eine Kollision auftritt. Wikipedia. Der cryptographische Hash-Ansatz, den Sie vorgeschlagen haben, hat möglicherweise genug Schlüsselraum (160) Bits, um die Wahrscheinlichkeit einer Kollision vernachlässigbar zu machen, aber Ihr Algorithmus zerlegt all diese Zufälligkeit zurück auf einen einzelnen int, bevor er den Vergleich durchführt negiert den Vorteil dieses größeren Schlüsselraums.

Ihre beste Vorgehensweise besteht darin, jedem Ihrer Datenelemente einen eindeutigen "sortOrder" -Wert zuzuweisen, der diese Werte mithilfe eines bewährten Algorithmus mischt und dann die Ergebnisse nach diesem Wert sortiert.

Wenn Sie Array.Sort verwenden, gibt es eine Überladung, die ein Array von "Schlüsseln" und ein Array von "Werten" erfordert. Das Schlüssel-Array wird normal sortiert, aber wenn ein Wert im Schlüssel-Array verschoben wird, wird auch der entsprechende Eintrag im Werte-Array verschoben.

Etwas wie:

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);