2010-02-20 21 views
16

Mögliche Duplizieren:
Randomize a List<T> in C#Shuffle Liste <T>

Ich habe eine Liste, die viele Tausende von FilePath die zu Orten von Audiodateien enthält, und frage mich, was der effizienteste Weg sein würde, eine Liste "mischen"?

Jede Hilfe wird sehr geschätzt :)

Danke

+1

Wollen Sie eigentlich die * effizienteste Lösung * oder möchten Sie eine * effizientere Lösung *? Weil es Algorithmen gibt, die sogar noch effizienter sind, als Fischer-Yates, vorausgesetzt, Sie sind bereit, bestimmte schöne Eigenschaften aufzugeben, wie zB fehlende Voreingenommenheit. (Nicht, dass Fischer-Yates wie unten implementiert ist unvoreingenommen; es ist stark voreingenommen.) –

+0

@Eric: Fischer-Yates _ist_ unvoreingenommen. Die unten angegebene Implementierung ist falsch, wie Sie angemerkt haben. Natürlich gibt es effizientere Implementierungen, wenn Sie bereit sind, Verzerrungen zu haben. Zum Beispiel, tun _nothing_ überhaupt. Ich verstehe wirklich nicht, was du meinst. Das OP hat nichts spezifiziert, und es ist vernünftig (IMO) anzunehmen, dass sie nach einem einheitlichen Shuffle suchen. –

+0

Ist das wirklich * vernünftig? Der betreffende Shuffle-Algorithmus ist für Mediendateien gedacht. Man könnte das Shuffle dazu neigen, höher bewertete Songs häufiger zu wiederholen. –

Antwort

13

Fisher-Yates Shuffle oder wie es auch, Knuth Shuffle bekannt.

+2

... was O (n) ist, also kann man nicht besser werden. – Guffa

+3

... Ich habe dich gerade neugestimmt, weil ich deine Antwort mochte :) Weiß nicht, warum wurde sie abgelehnt? –

+3

BTW, für schnelleres Shuffling, würde ich vorschlagen, dass Sie eine Liste/ein Array von Ganzzahlen mischen (mit der von Ihnen gewählten Methode), und diese gemischte Liste/Array als Index in die Liste der Dateinamen verwenden. Der Austausch von Dateinamen könnte sich als Engpass erweisen. –

4

myList.OrderBy(Guid.NewGuid())

+1

Einige GUID-Generierungsalgorithmen generieren monotone Werte, sodass dies möglicherweise keine zufälligen Ergebnisse liefert. Etwas Ähnliches, das eine andere Quelle von Zufälligkeit (wahrscheinlich zufällig) verwendet, würde jedoch funktionieren. – heneryville

8

Hier ist eine einfache (aber effektiv) Umsetzung des Fischer-Yates/Knuth Shuffle:

Random rnd = new Random(); 
for (int i = files.Length; i > 1; i--) { 
    int pos = rnd.Next(i); 
    var x = files[i - 1]; 
    files[i - 1] = files[pos]; 
    files[pos] = x; 
} 

Oder eine leichte Variation:

Random rnd = new Random(); 
for (int i = 1; i < files.Length; i++) { 
    int pos = rnd.Next(i + 1); 
    var x = files[i]; 
    files[i] = files[pos]; 
    files[pos] = x; 
} 

Da es sich um ein O (n) Operation, es ist der effizienteste Weg, eine Liste zu mischen. Da alle Elemente in der Liste verschoben werden müssen, ist es nicht möglich, eine Liste effizienter zu mischen als O (n).

Ich habe einen kleinen Leistungstest gemacht, indem ich eine Million Elemente tausendmal mixte, wobei ich diese Methode und die aktuell akzeptierte Antwort (LINQ OrderBy) benutzte, und dies ist ungefähr 15 mal (!) Schneller.

+0

Sie verwechseln die asymptotische Grenze mit Effizienz. Effizienz ist definiert als Ressourcenverbrauch pro Arbeitseinheit. Die asymptotische Grenze beschreibt, wie die Ressourcen verbraucht werden, wenn die Problemgröße zunimmt. Der Algorithmus "Finden Sie einen Teilstring der Länge m in einem String der Länge n" in der System.String-Klasse ist O (nm) aber es ist * weit * effizienter * auf * typischen * Probleme als das O (n + m) Algorithmen, die wir hätten implementieren können. Um die Effizienz zu berechnen, müssen Sie die * wahrscheinlichen Fälle * berücksichtigen, nicht die asymptotischen Grenzen. –

+0

Ich bemerke auch, dass Ihre Implementierung von Fischer-Yates eine Tendenz hat; es erzeugt nicht alle möglichen Mischungen mit gleicher Wahrscheinlichkeit. Dies ist wahrscheinlich kein Problem für einen Musikmischungsalgorithmus, aber es ist ein Problem, wenn Sie dies verwenden, um ein Kartenspiel für ein Pokerspiel zu mischen; Mit meiner Hand konnte ich schnell feststellen, was alle anderen in der Hand hatten. –

+0

@Eric: Warum denken Sie, dass die Implementierung eine Verzerrung hat? Es gibt jedem Gegenstand die gleiche Chance, in jeder Position in der Liste zu landen. Auch habe ich die Implementierung verifiziert, indem ich Millionen von Shuffles gemacht habe, und es gibt keine bemerkbare Voreingenommenheit. – Guffa

1

Ich habe Jon Skeets Lösung von this question zu meiner Extensions-Bibliothek hinzugefügt. Ich habe Methoden implementiert, die sowohl einen externen Zufallszahlengenerator als auch eine Standardimplementierung (Random) verwenden.