Ist die Verwendung von Random und OrderBy ein guter Shuffle-Algorithmus?

Ich habe einen Artikel über verschiedene Shuffle-Algorithmen bei Coding Horror gelesen . Ich habe gesehen, dass irgendwo Leute dies getan haben, um eine Liste zu mischen:

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

Ist das ein guter Shuffle-Algorithmus? Wie funktioniert es genau? Ist das ein akzeptabler Weg?

Es ist keine Art zu mischen, die ich mag, hauptsächlich mit der Begründung, dass es O (n log n) ist, ohne guten Grund, wenn es einfach ist, ein O (n) Shuffle zu implementieren. Der Code in der Frage "funktioniert", indem er jedem Element eine zufällige (hoffentlich eindeutige!) Nummer gibt und die Elemente dann nach dieser Nummer ordnet.

Ich bevorzuge Durstenfields Variante des Fisher-Yates-Shuffle, bei dem Elemente ausgetauscht werden.

Die Implementierung einer einfachen ShuffleErweiterungsmethode würde im Wesentlichen darin bestehen, die Eingabe aufzurufen ToListoder ToArrayzu verwenden und dann eine vorhandene Implementierung von Fisher-Yates zu verwenden. (Geben Sie den Randomals Parameter ein, um das Leben im Allgemeinen schöner zu machen.) Es gibt viele Implementierungen ... Ich habe wahrscheinlich irgendwo eine Antwort.

Das Schöne an einer solchen Erweiterungsmethode ist, dass dem Leser dann sehr klar ist, was Sie tatsächlich versuchen.

EDIT: Hier ist eine einfache Implementierung (keine Fehlerprüfung!):

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

BEARBEITEN: Die folgenden Kommentare zur Leistung haben mich daran erinnert, dass wir die Elemente tatsächlich zurückgeben können, wenn wir sie mischen:

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

Dies erledigt jetzt nur noch so viel Arbeit wie nötig.

Beachten Sie, dass Sie in beiden Fällen vorsichtig mit der von RandomIhnen verwendeten Instanz sein müssen :

• Wenn Sie zwei Instanzen von Randomungefähr zur gleichen Zeit erstellen, erhalten Sie dieselbe Folge von Zufallszahlen (wenn Sie auf dieselbe Weise verwendet werden).
• Random ist nicht threadsicher.

Ich habe einen Artikel,Random der ausführlicher auf diese Probleme eingeht und Lösungen bietet.

Dies basiert auf Jon Skeets Antwort .

In dieser Antwort wird das Array gemischt und dann mit zurückgegeben yield. Das Nettoergebnis ist, dass das Array für die Dauer von foreach sowie für die Iteration erforderliche Objekte im Speicher gehalten wird und die Kosten dennoch am Anfang stehen - die Ausbeute ist im Grunde eine leere Schleife.

Dieser Algorithmus wird häufig in Spielen verwendet, in denen die ersten drei Elemente ausgewählt werden und die anderen erst später, wenn überhaupt, benötigt werden. Mein Vorschlag ist, yielddie Nummern zu tauschen, sobald sie getauscht werden. Dies reduziert die Startkosten, während die Iterationskosten bei O (1) bleiben (im Grunde 5 Operationen pro Iteration). Die Gesamtkosten würden gleich bleiben, aber das Mischen selbst würde schneller sein. In Fällen, in denen dies aufgerufen collection.Shuffle().ToArray()wird, macht es theoretisch keinen Unterschied, aber in den oben genannten Anwendungsfällen beschleunigt es den Start. Dies würde den Algorithmus auch für Fälle nützlich machen, in denen Sie nur wenige eindeutige Elemente benötigen. Wenn Sie beispielsweise drei Karten aus einem 52er-Deck herausziehen müssen, können Sie anrufen deck.Shuffle().Take(3)und es finden nur drei Swaps statt (obwohl das gesamte Array zuerst kopiert werden müsste).

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

Ausgehend von diesem Zitat von Skeet:

Es ist keine Art zu mischen, die ich mag, hauptsächlich mit der Begründung, dass es O (n log n) ist, ohne guten Grund, wenn es einfach ist, ein O (n) Mischen zu implementieren. Der Code in der Frage "funktioniert", indem er jedem Element eine zufällige ( hoffentlich eindeutige! ) Nummer gibt und die Elemente dann nach dieser Nummer ordnet.

Ich werde ein wenig den Grund für das hoffentlich Einzigartige erklären !

Nun aus dem Enumerable.OrderBy :

Diese Methode führt eine stabile Sortierung durch. Das heißt, wenn die Schlüssel zweier Elemente gleich sind, bleibt die Reihenfolge der Elemente erhalten

Dies ist sehr wichtig! Was passiert, wenn zwei Elemente dieselbe Zufallszahl "erhalten"? Es kommt vor, dass sie in derselben Reihenfolge bleiben, in der sie sich im Array befinden. Was ist nun die Möglichkeit dafür? Es ist schwierig, genau zu berechnen, aber es gibt das Geburtstagsproblem , das genau dieses Problem ist.

Ist es jetzt real? Ist es wahr?

Wie immer schreiben Sie im Zweifelsfall einige Programmzeilen: http://pastebin.com/5CDnUxPG

Dieser kleine Codeblock mischt ein Array von 3 Elementen eine bestimmte Anzahl von Malen, wobei der Fisher-Yates-Algorithmus rückwärts und der Fisher-Yates-Algorithmus vorwärts ausgeführt wird (auf der Wiki- Seite gibt es zwei Pseudocode-Algorithmen ... Sie erzeugen Äquivalente Ergebnisse, aber eines wird vom ersten bis zum letzten Element ausgeführt, während das andere vom letzten bis zum ersten Element ausgeführt wird), der naive falsche Algorithmus von http://blog.codinghorror.com/the-danger-of-naivete/ und unter Verwendung des .OrderBy(x => r.Next())und die .OrderBy(x => r.Next(someValue)).

Nun Random.Next ist

Eine 32-Bit-Ganzzahl mit Vorzeichen, die größer oder gleich 0 und kleiner als MaxValue ist.

also ist es gleichbedeutend mit

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

Um zu testen, ob dieses Problem besteht, können wir das Array vergrößern (etwas sehr Langsames) oder einfach den Maximalwert des Zufallszahlengenerators verringern ( int.MaxValuekeine "spezielle" Zahl ... Es ist einfach eine sehr große Zahl). Wenn der Algorithmus nicht durch die Stabilität von verzerrt ist, sollte letztendlich OrderByjeder Wertebereich das gleiche Ergebnis liefern.

Das Programm testet dann einige Werte im Bereich von 1 bis 4096. Wenn man das Ergebnis betrachtet, ist es ziemlich klar, dass der Algorithmus für niedrige Werte (<128) sehr voreingenommen ist (4-8%). Mit 3 Werten benötigen Sie mindestens r.Next(1024). Wenn Sie das Array größer machen (4 oder 5), r.Next(1024)reicht es nicht einmal aus. Ich bin kein Experte für Mischen und Mathematik, aber ich denke, dass Sie für jedes zusätzliche Bit der Länge des Arrays 2 zusätzliche Bits des Maximalwerts benötigen (da das Geburtstagsparadoxon mit dem sqrt (numvalues) verbunden ist) Wenn der Maximalwert 2 ^ 31 ist, sollten Sie in der Lage sein, Arrays mit bis zu 2 ^ 12/2 ^ 13 Bits (4096-8192 Elemente) zu sortieren.

Es ist wahrscheinlich für die meisten Zwecke in Ordnung und erzeugt fast immer eine wirklich zufällige Verteilung (außer wenn Random.Next () zwei identische zufällige ganze Zahlen erzeugt).

Es funktioniert, indem jedem Element der Reihe eine zufällige Ganzzahl zugewiesen wird und die Reihenfolge dann nach diesen Ganzzahlen geordnet wird.

Dies ist für 99,9% der Anwendungen völlig akzeptabel (es sei denn, Sie müssen den obigen Randfall unbedingt bearbeiten). Außerdem ist der Einwand von skeet gegen seine Laufzeit gültig. Wenn Sie also eine lange Liste mischen, möchten Sie sie möglicherweise nicht verwenden.

Dies ist schon oft vorgekommen. Suche nach Fisher-Yates auf StackOverflow.

Hier ist ein C # -Codebeispiel, das ich für diesen Algorithmus geschrieben habe. Sie können es bei Bedarf auch für einen anderen Typ parametrisieren.

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

Scheint ein guter Mischalgorithmus zu sein, wenn Sie sich keine Sorgen um die Leistung machen. Das einzige Problem, auf das ich hinweisen möchte, ist, dass das Verhalten nicht steuerbar ist, sodass Sie möglicherweise Schwierigkeiten haben, es zu testen.

Eine mögliche Option besteht darin, einen Startwert als Parameter an den Zufallszahlengenerator (oder den Zufallsgenerator als Parameter) zu übergeben, damit Sie mehr Kontrolle haben und ihn einfacher testen können.

Ich fand Jon Skeets Antwort völlig zufriedenstellend, aber der Robo-Scanner meines Kunden meldet jeden Fall Randomals Sicherheitslücke. Also habe ich es ausgetauscht System.Security.Cryptography.RNGCryptoServiceProvider. Als Bonus wird das erwähnte Thread-Sicherheitsproblem behoben. Auf der anderen Seite wurde RNGCryptoServiceProviderals 300x langsamer als mit gemessen gemessen Random.

Verwendung:

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

Methode:

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

Suchen Sie einen Algorithmus? Du kannst meine ShuffleListKlasse benutzen :

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

Verwenden Sie es dann folgendermaßen:

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

Wie funktioniert es?

Nehmen wir eine erste sortierte Liste der 5 ersten ganzen Zahlen : { 0, 1, 2, 3, 4 }.

Die Methode beginnt mit dem Zählen der Anzahl der Elemente und ruft sie auf count. Dann, mit countauf jedem Schritt abnimmt, nimmt es eine Zufallszahl zwischen 0und countund bewegt ihn an das Ende der Liste.

Im folgenden schrittweisen Beispiel sind die Elemente, die verschoben werden könnten, kursiv und das ausgewählte Element fett gedruckt :

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

Dieser Algorithmus mischt, indem er für jeden Wert in einer Liste einen neuen Zufallswert generiert und die Liste dann nach diesen Zufallswerten sortiert. Stellen Sie sich vor, Sie fügen einer In-Memory-Tabelle eine neue Spalte hinzu, füllen sie dann mit GUIDs und sortieren nach dieser Spalte. Sieht für mich nach einem effizienten Weg aus (besonders mit dem Lambda-Zucker!)

Etwas unabhängig, aber hier ist eine interessante Methode (die, obwohl sie wirklich übertrieben ist, WIRKLICH implementiert wurde) für die wirklich zufällige Erzeugung von Würfeln!

Dice-O-Matic

Der Grund, warum ich dies hier poste, ist, dass er einige interessante Punkte darüber macht, wie seine Benutzer auf die Idee reagiert haben, Algorithmen zum Mischen über tatsächliche Würfel zu verwenden. In der realen Welt ist eine solche Lösung natürlich nur für die wirklich extremen Bereiche des Spektrums geeignet, in denen Zufälligkeit einen so großen Einfluss hat und möglicherweise den Einfluss auf das Geld hat;).

Ich würde sagen, dass viele Antworten hier wie "Dieser Algorithmus mischt, indem er für jeden Wert in einer Liste einen neuen Zufallswert generiert und dann die Liste nach diesen Zufallswerten ordnet" möglicherweise sehr falsch sind!

Ich würde denken, dass dies NICHT jedem Element der Quellensammlung einen zufälligen Wert zuweist. Stattdessen könnte es einen Sortieralgorithmus geben, der wie Quicksort läuft und eine Vergleichsfunktion ungefähr n log n-mal aufruft. Einige Sorten erwarten wirklich, dass diese Vergleichsfunktion stabil ist und immer das gleiche Ergebnis liefert!

Könnte es nicht sein, dass der IEnumerableSorter eine Vergleichsfunktion für jeden Algorithmusschritt von z. B. Quicksort aufruft und jedes Mal die Funktion x => r.Next()für beide Parameter aufruft, ohne diese zwischenzuspeichern!

In diesem Fall könnten Sie den Sortieralgorithmus wirklich durcheinander bringen und ihn viel schlechter machen als die Erwartungen, auf denen der Algorithmus aufgebaut ist. Natürlich wird es irgendwann stabil und gibt etwas zurück.

Ich könnte es später überprüfen, indem ich die Debugging-Ausgabe in eine neue "Weiter" -Funktion setze, um zu sehen, was passiert. In Reflector konnte ich nicht sofort herausfinden, wie es funktioniert.

Startzeit für die Ausführung von Code mit allen Threads löschen und jeden neuen Test zwischenspeichern,

Erster erfolgloser Code. Es läuft auf LINQPad. Wenn Sie folgen, um diesen Code zu testen.

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

list.OrderBy (x => r.Next ()) verwendet 38,6528 ms

list.OrderBy (x => Guid.NewGuid ()) verwendet 36,7634 ms (wird von MSDN empfohlen.)

das nach dem zweiten Mal verwenden beide gleichzeitig.

BEARBEITEN: TESTCODE auf Intel Core i7 [email protected], Ram 8 GB DDR3 @ 1600, HDD SATA 5200 U / min mit [Daten: 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);
            }
            }

        }
    }
}

Ergebnisbeschreibung: https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
Ergebnisstatistik: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

Schlussfolgerung:
Angenommen, LINQ OrderBy (r.Next ()) und OrderBy (Guid.NewGuid ()) sind in der ersten Lösung nicht schlechter als die benutzerdefinierte Zufallsmethode.

Antwort: Sie sind Widerspruch.