Erzeugen Sie Zufallszahlen ohne Wiederholungen

163352
Kao

Ich möchte eine Liste mit N verschiedenen Zufallszahlen erstellen:

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

Aber ich finde, es gibt einen besseren Weg. Diese do...whileSchleife macht das besonders hässlich. Irgendwelche Vorschläge, wie man das verbessern kann?

Antworten
91
Ist dies nicht ein Fall für den [Fisher-Yates_shuffle] (http://en.wikipedia.org/wiki/Fisherâ$ „Yates_shuffle)? Martin R vor 6 Jahren 0
@MartinR Nicht genau. Fisher-Yates-Shuffle gibt Ihnen die Möglichkeit, ** alle ** Elemente in einem bestimmten Bereich zu verändern. Kao vor 6 Jahren 2
Sie haben recht, ich habe es nicht richtig gelesen. Martin R vor 6 Jahren 0
@MartinR Wenn Sie diesen Shuffle jedoch für eine Liste mit unterschiedlichen Zahlen ausführen und diese dann auf die erwartete Größe zuschneiden, haben Sie einen anderen Ansatz Kao vor 6 Jahren 0
Was ist der Anwendungsfall hier? Was versuchst du eigentlich zu tun? Möglicherweise gibt es eine domänenspezifische Anwendung, die besser ist als etwas generisches (und schlechtes). corsiKa vor 6 Jahren 0
Haben Sie von linearen kongruenten Generatoren gehört? Es könnte (mit den richtigen Parametern) es Ihnen ermöglichen, in einer pseudozufälligen Reihenfolge n eindeutige Zahlen zwischen 1 und m auszuwählen, für einige m> = n. Olivier vor 6 Jahren 0
Leider bin ich für eine vollständige Antwort nicht inspiriert, aber jemand könnte auf diesen Kommentar eingehen. Die Folge X (n) = (a * X (n-1) + b)% m überspannt alle Zahlen zwischen 0 und m-1 in einer pseudozufälligen Reihenfolge mit der richtigen Wahl der Parameter a, b (und möglicherweise) einige Einschränkungen für m). Führen Sie einfach die Sequenz n mal für die n Zahlen zwischen 0 und m-1 aus, die Sie benötigen. Die Standardauswahl von Parametern (in vielen Bibliotheken verwendet) ist a = 16807, b = 0 und m = 2 ^ (31) - 1. Olivier vor 6 Jahren 0
@BrunoCosta: "Wenn also die Zahlen nicht wiederholt werden, kann man sie nicht mehr zufällig nennen, da sie die Eigenschaft haben, sich nicht zu wiederholen, was eine sehr einzigartige Eigenschaft ist": Das stimmt nicht. "Zufällig" bedeutet nicht "unabhängig", geschweige denn "keine interessanten Eigenschaften zu haben". Nach Ihrer Definition von "zufällig" konnten wir nicht einmal "zufällige ganze Zahl" sagen, weil die Eigenschaft, eine ganze Zahl zu sein, bedeuten würde, dass sie nicht zufällig war. . . ruakh vor 6 Jahren 3
Dieser Beitrag wurde vom System [wegen zu vieler Kommentare automatisch gekennzeichnet] (http://meta.stackexchange.com/q/101531/241497). Bitte setzen Sie alle Diskussionen in [The 2nd Monitor-Chatroom] (http://chat.stackexchange.com/rooms/8595/the-2nd-monitor) fort, wo diese Frage bereits viel diskutiert wurde. rolfl vor 6 Jahren 0
Bob Floyd hat zu diesem Zweck einen Algorithmus erfunden. Siehe: http://stackoverflow.com/a/2394292/179910. Es ist wesentlich besser als das, was Sie bereits gezeigt haben * oder *. Jerry Coffin vor 6 Jahren 8
Ein kleiner Vorschlag: Verwenden Sie das Ergebnis-Schlüsselwort, um das Erstellen einer Liste zu vermeiden. http://stackoverflow.com/questions/39476/what-is-the-yield-keyword-used-for-in-c simoneL vor 6 Jahren 0
@ Kao - es wäre großartig, wenn wir diese Frage (und Kopfgeld) im Chat besprechen könnten ...] (http://chat.stackexchange.com/rooms/8595/the-2nd-monitor) rolfl vor 6 Jahren 1
@ JerryCoffin - Ich habe nachgesehen, der Algorithmus ist gut für die effiziente Handhabung von Kollisionen, hat aber Einschränkungen hinsichtlich der Qualität der Zufälligkeit der Ergebnisse. rolfl vor 6 Jahren 0
@rolfl: Ich glaube, du hast die Absicht falsch verstanden. Wenn Sie den Links in den Kommentaren folgen, finden Sie einige mathematische Beweise für die Qualität der Zufälligkeit der Ergebnisse. Jerry Coffin vor 6 Jahren 1
@ JerryCoffin, ich glaube, ich bin richtig, und zum Beispiel kann der erste Wert im Ergebnis niemals "N" sein, was bedeutet, dass die Zufälligkeit des Ergebnisses nicht erhalten bleibt. Die Zufälligkeit der Auswahl wird beibehalten, aber die Reihenfolge ist nicht zufällig (genug). Können wir das in [dem 2. Monitor] (http://chat.stackexchange.com/rooms/8595/the-2nd-monitor) aufklären? rolfl vor 6 Jahren 2
@ JerryCoffin User Kache ** beweist nicht die Zufälligkeit der Ergebnisse **. Es beweist nur **, dass jede Zahl die gleiche Wahrscheinlichkeit hat, als Ergebnis ** aufzutreten. Die letzten rangeLenght - count - Elemente ** können jedoch nicht in Index 0 des Ergebnisses ** angezeigt werden. Wie ich bereits zu oft erwähnte, nähern sich die angeforderten Elemente der Entfernungslänge, und das Ergebnis nähert sich einer linearen Sequenz mit x (n) = x (n-1) + 1 an. Ich bin also mit rolfl in dieser . Bruno Costa vor 6 Jahren 0
"Zufallszahlen ohne Wiederholungen erzeugen" - dann ist es kein Zufall. radarbob vor 6 Jahren 0
@radarbob Ich hatte diese Diskussion schon mit Ruahk. Randomness muss nicht unabhängig sein. Dies bedeutet, dass eine sich nicht wiederholende Sequenz zufällig sein kann. Zum Beispiel: seien x1, y1 und y2 zufällig. x2 = x1 + y1. x3 = x2 + y2. x1, x2, x3 wäre eine nicht wiederholende Zufallssequenz. Die Art von Zufälligkeit, von der Sie sprechen, ist unabhängige Zufälligkeit. Bruno Costa vor 6 Jahren 0
Aber das Zufällige ist, dass man es nie sagen kann. radarbob vor 6 Jahren 0
@radarbob Bitte setzen Sie die Diskussion fort [im Chat] (http://chat.stackexchange.com/rooms/8595/the-2nd-monitor). (Und du irrst dich.) ANeves vor 6 Jahren 0
@ Kao Anscheinend haben Sie noch keine Antwort ausgewählt. Sollten Sie anfangen zu überlegen, welche Antwort Sie akzeptieren sollten? Bruno Costa vor 6 Jahren 0
@BrunoCosta Ich werde morgen nach dem Ende einer Prämie eine Antwort auswählen. Kao vor 6 Jahren 0
Es scheint, dass [dieser] (http://blog.demofox.org/2013/07/06/fast-lightweight-random-shuffle-functionality-fixed/) Kerl Ihr Problem auf sehr nette Weise gelöst hat. Das sagt er in der ersten Zeile des Beitrags: * In diesem Beitrag werde ich einen Weg zeigen, einen Iterator zu erstellen, der Elemente in einer Liste in einer zufälligen Reihenfolge aufruft, jeden Artikel nur einmal besucht und es erzählt Sie, wenn es alle Artikel besucht hat und fertig ist. Dies geschieht, ohne eine gemischte Liste zu speichern, und es muss auch nicht nachverfolgt werden, welche Elemente bereits besucht wurden. * NicolaSysnet vor 4 Jahren 2
Hat jemand diese Frage besucht, weil sie sie auf der Tour gesehen hat und wollte wissen, ob sie echt ist? Ich habe es wirklich getan CodingNinja vor 3 Jahren 0

16 Antworten auf die Frage

87
rolfl

Antwort auf Kopfgeld aktualisiert: Siehe Ist das Ihre endgültige Antwort? am Ende und andere Änderungen - im Grunde wird die Antwort wesentlich umgeschrieben.


Um Ihr Problem in die Anforderungen einzugliedern:

  • Sie benötigen eine Reihe von Zufallszahlen
  • Die Zahlen müssen eindeutig sein
  • Die Reihenfolge der zurückgegebenen Zahlen muss zufällig sein

Ihr aktueller Code zeigt an, dass der Bereich der Zufallszahlen durch angegeben ist Random.Next(), wodurch Werte im [0 .. Int32.MaxValue)Bereich zurückgegeben werden (Hinweis, ausgenommen Int32.MaxValue). Dies ist für die Frage dieser Frage von Bedeutung, da andere Antworten angenommen haben, dass der Bereich konfigurierbar und "klein" ist.

Wenn der Bereich konfigurierbar sein sollte, wäre der empfohlene Algorithmus möglicherweise viel größer.

Lassen Sie uns auf der Grundlage dieser Annahmen eine Codeüberprüfung durchführen ...

Code-Stil

mache ... während

Die eklatantesten Probleme sind hier die ungespannte do-whileSchleife. Sie wussten es bereits, aber dieser Code ist hässlich:

    do number = random.Next();
    while (randomNumbers.Contains(number));

Es sollte wirklich abgespannt sein :

    do
    {
        number = random.Next();
    } while (randomNumbers.Contains(number));

Dies macht die Aussage klar und verringert die Verwirrung erheblich. Verwenden Sie immer Klammern für 1-Liner.

List Konstruktion

Die List-Klasse ermöglicht die Verwendung einer Anfangskapazität . Da die Kapazität nur sein muss count, ist es sinnvoll, die Liste mit dieser Kapazität zu initialisieren:

List<int> randomNumbers = new List<int>(count);

Aktueller Algorithmus

Hier können die interessantesten Beobachtungen gemacht werden. Lassen Sie uns Ihren aktuellen Algorithmus analysieren:

  • Erstellen Sie einen Container für die Ergebnisse
  • Wiederholen Sie diesen Vorgang, bis Sie N Werte ausgewählt haben:
    • Wählen Sie einen zufälligen Wert
    • Überprüfen Sie, ob es zuvor ausgewählt wurde
    • Wenn es "neu" ist, fügen Sie es dem Container hinzu

Dieser Algorithmus erzeugt zufällige Werte in einer zufälligen Reihenfolge und mit guten zufälligen Eigenschaften (keine Schräglagen, Abweichungen, Lücken usw.).

Mit anderen Worten, Ihre Ergebnisse sind gut.

Das Problem ist mit der Leistung ....

Es gibt zwei Leistungsprobleme, das eine klein und das andere groß:

  1. die do-while-Schleife, um Kollisionen zu vermeiden
  2. den Listencontainer

Leistung während des Spiels

Das Tuning hat einen sehr geringen Einfluss auf die Leistung ... fast vernachlässigbar. Dies ist heiß umstritten, aber die Realität ist, dass Sie ein sehr, sehr großes benötigen würden, countbevor dies zu einem Problem wird. Die Begründung lautet wie folgt:

Kollisionen treten auf, wenn der Zufallswert zuvor ausgewählt wurde. Für den angegebenen Bereich von [0 .. Int32.MaxValue)benötigen Sie einen sehr großen countWert, bevor tatsächlich Kollisionen auftreten. Zum Beispiel countmüsste es ungefähr 65.000 sein, bevor die Chance, dass es nur eine einzige Kollision gab, besser als 50% ist.

Wählen Sie im Allgemeinen einen Bereich von \ $ N \ $ aus, und wählen Sie \ $ M \ $ numbers. Wenn \ $ M <\ sqrt {N} \ $, dann ist die Wahrscheinlichkeit einer einzelnen Kollision <50%. Da der Bereich sehr groß ist, ist die Wahrscheinlichkeit gering.

Wenn der Bereich klein wäre, wären die Wahrscheinlichkeiten natürlich erheblich beeinträchtigt. Aber der Bereich ist auf festgelegt Int32.MaxValue, also ist das OK.

Wenn der countWert groß war, wären auch die Wahrscheinlichkeiten betroffen. Wie groß wäre sehr groß? Nun, Sie würden in sehr großen Arrays laufen, bevor Sie sich mit erheblichen Problemen beschäftigen ... Ich würde mir sicher sein, dass Sie nahe an \ $ \ frac {Int32.MaxValue} {2} \ $ stoßen, bevor Sie sich aufmachen ein bedeutendes Problem mit der Leistung.

Leistung auflisten

Dies ist zweifellos Ihre größte Sorge. Sie benutzen dierandomNumbers.Contains(number) Aufruf bestimmen Sie, ob zuvor ein Wert ausgewählt wurde. Dies erfordert einen Scan aller zuvor ausgewählten Werte zur Bestimmung. Wie bereits erwähnt, wird dies fast immer false zurückgeben und muss daher die gesamte Liste durchsuchen.

Wenn der countWert ansteigt, erhöht sich die Zeitdauer für die Ausführung Containsmit einer quadratischen Rate, wobei \ $ O (n ^ 2) \ $ wo nist count.

Dieses Leistungsproblem wird viel früher als das Problem der zufälligen Kollisionen kritisch.

Etwas zusammensetzen

Das Problem, das Sie in Ihrem Code haben, ist, dass Sie versuchen, zu viel auf einmal zu tun, Sie verwenden eine Liste, da dies Ihr Rückgabewert ist, wenn ein HashSet besser wäre. Wenn Sie das Problem in Stufen unterteilen, können Sie die Dinge eleganter lösen.

Wenn Sie einem HashSet einen doppelten Wert hinzufügen, wächst er nicht, und die Operationsleistung hängt nicht von der Datenmenge im HashSet ab (dies ist \ $ O (1) \ $). Sie können das Countof the HashSet verwenden, um die Daten-Eindeutigkeit zu verwalten.

Sobald Sie einen eindeutigen Satz eindeutiger Zufallszahlen haben, können Sie sie in eine Liste ablegen und die Liste anschließend mit einem effizienten Shuffle neu mischen.

Die richtige Kombination dieser Datenstrukturen führt zu einer Gesamtlösung von $ O (n) \ $, die sich recht gut skalieren lässt.

Hier ist ein Code, der auch in Ideone funktioniert . Beachten Sie, mein C # ist schwach, also habe ich versucht, die Logik klar zu machen.

using System;
using System.Collections.Generic;

public class Test
{
    static Random random = new Random();

    public static List<int> GenerateRandom(int count)
    {
        // generate count random values.
        HashSet<int> candidates = new HashSet<int>();
        while (candidates.Count < count)
        {
            // May strike a duplicate.
            candidates.Add(random.Next());
        }

        // load them in to a list.
        List<int> result = new List<int>();
        result.AddRange(candidates);

        // shuffle the results:
        int i = result.Count;  
        while (i > 1)
        {  
            i--;  
            int k = random.Next(i + 1);  
            int value = result[k];  
            result[k] = result[i];  
            result[i] = value;  
        }  
        return result;
    }
    public static void Main()
    {
        List<int> vals = GenerateRandom(10);
        Console.WriteLine("Result: " + vals.Count);
        vals.ForEach(Console.WriteLine);
    }
}

Der obige Code ist meine erste Empfehlung. Er funktioniert gut und lässt sich gut skalieren, damit eine angemessene Anzahl von Werten zurückgegeben wird.

Zweiter alternativer Algorithmus

Das Problem mit dem obigen Algorithmus ist dreifach:

  1. Wenn die Anzahl sehr groß ist, erhöht sich die Wahrscheinlichkeit einer Kollision und die Leistung kann beeinträchtigt werden
  2. Die Daten müssen sich zu einem bestimmten Zeitpunkt sowohl im HashSet als auch in der Liste befinden, sodass die Speicherplatzbelegung verdoppelt wird.
  3. Die Shuffle am Ende ist erforderlich, um die Daten in einer zufälligen Reihenfolge zu halten (HashSet hält die Daten nicht in einer bestimmten Reihenfolge und der Hash-Algorithmus bewirkt, dass die Reihenfolge voreingenommen und verzerrt wird).

Dies sind nur Leistungsprobleme, wenn die Anzahl sehr groß ist. Beachten Sie, dass nur die Kollisionen bei großer Zählung werden die Skalierbarkeit der Lösung (bei großer Zählung auswirken es ist nicht mehr ganz \ O $ (n) \ $, und es wird noch schlimmer werden, kommt zunehmend bei Zählern Ansätze Int32.MaxValue. Beachten Sie, dass in dieser wirklichen Leben wird höchstwahrscheinlich niemals passieren .... und Speicher wird zu einem Problem, bevor Leistung auftritt.

@ JerryCoffin wies auf einen alternativen Algorithmus von Bob Floyd hin, bei dem ein Trick gespielt wird, um sicherzustellen, dass Kollisionen niemals passieren. Dies löst das Problem der Skalierbarkeit bei sehr großen Anzahlen. Es löst nicht die Notwendigkeit sowohl eines HashSets als auch einer Liste und es befriedigt nicht die Notwendigkeit des Shuffle.

Der vorgestellte Algorithmus:

initialize set S to empty
for J := N-M + 1 to N do
    T := RandInt(1, J)
    if T is not in S then
        insert T in S
    else
        insert J in S

geht davon aus, dass RandInt(1, J)die Werte einschließlich J zurückgegeben werden.

Um den obigen Algorithmus zu verstehen, müssen Sie erkennen, dass Sie einen Zufallswert aus einem Bereich auswählen, der kleiner als der gesamte Bereich ist. Nach jedem Wert erweitern Sie diesen um einen weiteren. Im Falle einer Kollision können Sie den Max sicher einfügen, da er nie zuvor aufgenommen werden konnte.

Die Wahrscheinlichkeit einer Kollision steigt mit der gleichen Rate, mit der die Anzahl der Werte abnimmt, so dass die Wahrscheinlichkeit, dass eine Zahl im Ergebnis enthalten ist, nicht verzerrt oder verzerrt ist.

Ist das schon fast eine endgültige Antwort? Nein

Die Verwendung der obigen Lösung in C # würde also (in Ideone) aussehen (Beachten Sie, der Code unterscheidet sich jetzt von Ideone):

public static List<int> GenerateRandom(int count)
{
    // generate count random values.
    HashSet<int> candidates = new HashSet<int>();
    for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++)
    {
        Console.WriteLine(top);
        // May strike a duplicate.
        if (!candidates.Add(random.Next(top + 1)))
        {
            candidates.Add(top);
        }
    }

    // load them in to a list.
    List<int> result = candidates.ToList();

    // shuffle the results:
    int i = result.Count;  
    while (i > 1)
    {  
        i--;  
        int k = random.Next(i + 1);  
        int value = result[k];  
        result[k] = result[i];  
        result[i] = value;  
    }  
    return result;
}    

Beachten Sie, dass Sie die Ergebnisse immer noch neu mischen müssen, damit das HashSet-Problem behoben wird. Beachten Sie auch die Notwendigkeit, die fantastische Schleifenbedingung auszuführen, top > 0da die Dinge beim Überlauf unübersichtlich werden.

Kannst du das Shuffle vermeiden?

Dies löst also die Notwendigkeit, die Kollisionsschleife auszuführen, aber was ist mit dem Shuffle. Kann das Problem gelöst werden, indem das HashSet und die Liste gleichzeitig verwaltet werden . Nein! Betrachten Sie diese Funktion (auch in Ideone) :

public static List<int> GenerateRandom(int count)
{
    List<int> result = new List<int>(count);

    // generate count random values.
    HashSet<int> candidates = new HashSet<int>();
    for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++)
    {
        // May strike a duplicate.
        int value = random.Next(top + 1);
        if (candidates.Add(value))
        {
            result.Add(value);
        }
        else
        {
            result.Add(top);
            candidates.Add(top);
        }
    }

    return result;
}

Die obige Antwort wird niemals zulassen, dass der erste Wert im Ergebnis über einen der Max - Countto- MaxWerte verfügt (da beim ersten Wert niemals eine Kollision auftritt und der Bereich an diesem Punkt nicht vollständig ist) gebrochener Zufallsgenerator.

Trotz dieses Kollisionsvermeidungsalgorithmus müssen Sie die Ergebnisse immer noch neu mischen, um eine saubere Neigung zu den Zahlen zu gewährleisten.


TL; DR

Ist das deine letzte Antwort? Ja!

Nachdem Sie viel mit diesem Code gespielt haben, ist es offensichtlich, dass es nützlich ist, eine bereichsbasierte Eingabe sowie ein Int32.MaxValue-System zu haben. Spieler mit großen Reichweiten führen auch im 32-Bit-Integer-Bereich zu potenziellen Überläufen.

Wenn Sie mit @mjolka arbeiten, wäre der folgende Code der beste von beiden Welten:

    static Random random = new Random();

    // Note, max is exclusive here!
    public static List<int> GenerateRandom(int count, int min, int max)
    {

        //  initialize set S to empty
        //  for J := N-M + 1 to N do
        //    T := RandInt(1, J)
        //    if T is not in S then
        //      insert T in S
        //    else
        //      insert J in S
        //
        // adapted for C# which does not have an inclusive Next(..)
        // and to make it from configurable range not just 1.

        if (max <= min || count < 0 || 
                // max - min > 0 required to avoid overflow
                (count > max - min && max - min > 0))
        {
            // need to use 64-bit to support big ranges (negative min, positive max)
            throw new ArgumentOutOfRangeException("Range " + min + " to " + max + 
                    " (" + ((Int64)max - (Int64)min) + " values), or count " + count + " is illegal");
        }

        // generate count random values.
        HashSet<int> candidates = new HashSet<int>();

        // start count values before max, and end at max
        for (int top = max - count; top < max; top++)
        {
            // May strike a duplicate.
            // Need to add +1 to make inclusive generator
            // +1 is safe even for MaxVal max value because top < max
            if (!candidates.Add(random.Next(min, top + 1))) {
                // collision, add inclusive max.
                // which could not possibly have been added before.
                candidates.Add(top);
            }
        }

        // load them in to a list, to sort
        List<int> result = candidates.ToList();

        // shuffle the results because HashSet has messed
        // with the order, and the algorithm does not produce
        // random-ordered results (e.g. max-1 will never be the first value)
        for (int i = result.Count - 1; i > 0; i--)
        {  
            int k = random.Next(i + 1);  
            int tmp = result[k];  
            result[k] = result[i];  
            result[i] = tmp;  
        }  
        return result;
    }

    public static List<int> GenerateRandom(int count)
    {
        return GenerateRandom(count, 0, Int32.MaxValue);
    }
Warum mischen Sie die Ergebnisse? Ich bin darüber verwirrt, da dies offenbar von allen in ihre Antworten einbezogen wird, was aber nicht in der OP-Frage steht IEatBagels vor 6 Jahren 0
@TopinFrassi: Weil Rolfi die Zahlen bestellt hat (um nach Duplikaten zu suchen), aber sie sollten nicht bestellt werden. Charles vor 6 Jahren 0
@ TopinFrassi hat recht, er sollte nur Kandidaten zurückgeben, und es wäre in Ordnung. Verschieben von Part entfernen Es ist nur ein wenig besser als die Antwort von op, da es Hash-Werte verwendet, die das Auffinden eines Duplikats weniger kosten. Ich sagte, dies sei ein Problem beim Mischen, aber natürlich gibt es viele Implementierungen, um die Anforderungen zu erfüllen. Bruno Costa vor 6 Jahren 0
@BrunoCosta - Das HashSet legt den Daten in der Liste eine nicht zufällige (jedoch unstrukturierte) Reihenfolge fest. Der Code des OP würde eine zufällige Reihenfolge des Ergebnisses erzeugen. Die Zufallswiedergabe ist erforderlich, um die zufällig geordnete Ausgabe beizubehalten. Was den "etwas besseren" Teil betrifft, so ist das HashSet etwa N / 4 mal schneller als die Liste (wobei N die Anzahl ist). Für großes N, sagen wir 10.000, wird das HashSet also etwa 2500 sein mal schneller .... was, denke ich, "leicht" sein könnte. rolfl vor 6 Jahren 4
@rolfl Gotcha. Ich vergesse immer, dass Hashs keine Bestellung garantieren. Ich meinte nicht schlank, um den Unterschied abzuschwächen, den er in einem echten Fall tatsächlich haben kann. Aber Sie haben vergessen, in Ihrem Punkt zu erwähnen, dass Sie eine weitere O (n) -Operation durchführen müssen, das Mischen. Aber offensichtlich macht die Verwendung des Hashs das schnell wieder wett. Bruno Costa vor 6 Jahren 0
Oh, aber warte, was ich gesagt habe, war im Grunde richtig. Du hast gerade gesagt, dass der OP mehr getan hat, als er tun müsste. Und Sie haben gerade eine bessere Version davon implementiert. Da Sie nur das tun sollten, was Sie brauchen, würde die Rückgabe des Sets (auch) die Anforderung erfüllen. Die @ TopinFrassi-Lösung ist also besser. Bruno Costa vor 6 Jahren 0
Schön, aber ich würde mit Jeroens Einzeiler `result = result.OrderBy (x => random.Next ());` anstelle der letzten `while`-Schleife gehen. CompuChip vor 6 Jahren 0
@CompuChip - Die While-Schleife, die ich habe, ist \ $ O (n) \ $, während der OrderBy bei \ $ O (n \ log {n}) \ $ langsamer ist. Diese Frage hat eine Menge [Chat im 2. Monitor erzeugt, und Sie können gerne teilnehmen] (http://chat.stackexchange.com/rooms/8595/the-2nd-monitor) rolfl vor 6 Jahren 0
@BrunoCosta - Sie haben scheinbar den Eindruck, ich stehe in einer Art Konkurrenz zu TompinFrassi oder Jeroen. Nun, da ist etwas Wahres. Jeroen und ich hatten viele gutmütige Diskussionen über dieses Problem [gestern im 2. Monitor (Transctipt)] (http://chat.stackexchange.com/transcript/message/17391853#17391853) und ich lade Sie (oder irgendjemanden) ein else) um [mit uns zu diskutieren, um mehr darüber zu erfahren] (http://chat.stackexchange.com/rooms/8595/the-2nd-monitor) rolfl vor 6 Jahren 0
Ich sollte auch darauf hinweisen, BrunoCosta, dass ich nicht vergessen habe, die Operation $ O (n) \ $ shuffle zu erwähnen, und Sie sollten wissen, dass zwei aufeinander folgende Operationen $ O (n) \ $ immer noch $ O (n.) Sind ) \ $. @TopinFrassi schlug eine ähnliche Lösung vor, lieferte jedoch keine Ergebnisse wie die OPs, und ich arbeitete an dieser Antwort, bevor er seine veröffentlichte. Ich stimme zu, dass, wenn Sie den Shuffle entfernen, unsere Antworten größtenteils gleich sind, der Shuffle jedoch nicht entfernt werden kann, während die Ergebnisse ähnlich wie bei den OPs bleiben. Darüber hinaus gebe ich verschiedene Gründe (Review), warum das HashSet verwendet werden soll. rolfl vor 6 Jahren 0
Ich verstehe nicht, warum es eine Debatte über diese Antwort gibt. Es ist eine sehr gute und niemand sollte sich darüber im Klaren sein, dass unsere Antworten gleich aussehen, zumindest stört es mich nicht. Seine Erklärungen sind anders (sollte ich besser sagen) als meine IEatBagels vor 6 Jahren 0
@rolfl Wenn sich die Anzahl der angeforderten Randoms dem maximalen Bereich nähert, in dem sich die Randoms befinden dürfen, dauert Ihre Schleife, die die Anzahl generiert, möglicherweise länger und länger (wenn 1.000.000 eindeutige Nummern im Bereich von 1-1.000.000 angefordert werden, gibt es einen In-1.000.000 Änderung der Generierung der letzten Zahl - im Durchschnitt werden für die letzte Zahl 1 mil Iterationen benötigt). Daher ist es am besten, wenn die angeforderte Anzahl größer als die Hälfte des gesamten Bereichs ist, um mit einem vollständigen Satz zu beginnen und zufällig zu entfernen, bis der Satz die richtige Größe hat. nhgrif vor 6 Jahren 0
Meine Antwort als Antwort auf die Kopfgeldanforderung aktualisiert. rolfl vor 6 Jahren 0
@rolfl Jerry Sarglösung ** fast ** beseitigt die Notwendigkeit von Shuffle, wenn die Anzahl der Elemente <<< als Bereichslänge ist. Nun, es gibt immer noch ein Problem, das letzte Element von rangeLength kann niemals an erster Stelle stehen. Anstelle eines vollständigen Shuffles können Sie also einen partiellen Shuffle durchführen. Bruno Costa vor 6 Jahren 0
@BrunoCosta - das hängt sehr stark von der spezifischen Implementierung ab, die von der Hash-Funktion in HashSet verwendet wird, die nicht Teil der Spezifikation ist. Sie können dem HashSet nicht für eine Auftragserhaltung vertrauen, und alles andere als eine perfekte oder völlig zufällige Aufbewahrung ist nicht gut genug. rolfl vor 6 Jahren 0
@rolfl Wie ich bereits in meiner Antwort festgestellt habe, funktioniert dieser Algorithmus nicht, wenn count = int32.MaxValue ist. Und Sie machen einen falschen Vergleich für Sie. Bruno Costa vor 6 Jahren 0
@rolfl Verzicht auf die Verwendung von Hash, siehe meine Lösung, um zu sehen, was ich meine. Bruno Costa vor 6 Jahren 0
Ich mag diese Antwort, viel Mühe, +1. Ich hatte Angst, das Finale nicht zu sehen und füllte die Liste auf dem Weg. Habe aber noch einen Einwand: Die * Zufälligkeit * der endgültigen Lösung ist nicht perfekt, würde zu Beginn niemals den höchsten Wert zulassen (der Shuffle hat geholfen, das zu vermeiden). Ich würde persönlich das mit HashSet gepatchte Original für den Test verwenden. Keine weiteren Änderungen (außer Codestyling). Ich gehe natürlich davon aus, dass es nicht erwünscht ist, den Speicher mit einer Liste von 2G-Ints zu essen -> 8 GB. firda vor 6 Jahren 2
@firda - das ist ein echtes Problem ... das habe ich nie bemerkt. Die Shuffle ist tatsächlich erforderlich, da *** keine der Max-Count-Werte jemals auf Position 0 sein wird. Die Shuffle ist erforderlich. Mein 'ist, dass deine endgültige Antwort' nicht gut genug ist. rolfl vor 6 Jahren 0
Ich stelle fest, dass jeder, der meinen letzten Kommentar liest, die Lösung für "nicht gut genug" hält. Die Antwort wurde nach diesem Kommentar (wieder) aktualisiert, und der Code ist, soweit ich weiß, vollständig. Das ist meine endgültige Antwort ;-) rolfl vor 5 Jahren 0
Warum ist ein HashSet?`besser als eine` Liste"? Der Hash-Code eines int ist ein int und wahrscheinlich selbst. Wenn Sie also HashSet.Add (int) `tun, wird intern nur _hashes.Contains (int)` ausgeführt und einige unnötige `GetHashCode 'hinzugefügt () `Gemeinkosten in die Abmachung? MrLore vor 4 Jahren 0
37
Jeroen Vannevel

Ja, das ist definitiv.

Sie generieren eine Sammlung von Elementen, mischen sie zusammen und beginnen, Elemente daraus zu ziehen. Ein schneller Oneliner wäre:

Enumerable.Range(0,100).OrderBy(x => Guid.NewGuid()).Take(20);

oder alternativ

Enumerable.Range(0,100).OrderBy(x => random.Next()).Take(20);

Dadurch erhalten Sie 20 eindeutige Zufallswerte zwischen 0 und 100.

Der Unterschied zu Ihrem Ansatz besteht darin, dass Sie ein Worst-Case-Szenario der Unendlichkeit haben: Was ist, wenn Sie wirklich unglücklich sind und ständig den gleichen Wert haben? Sie erhalten nie die erforderliche Menge an Zufallswerten.

Bei meinem Ansatz werden jedoch zunächst 100 Werte generiert und dann eine Untermenge daraus abgerufen, die Sie hinsichtlich der Auswirkungen auf das Gedächtnis kritisieren können. Wenn Sie bedenken random.Next(), dass Sie die Hälfte des ganzzahligen Bereichs verwenden, sollten Sie in der Tat vorsichtig sein, da dies einen großen Einfluss auf den Speicher haben wird.

Dies hängt auch von Ihrer spezifischen Situation ab: Wenn Sie über einen sehr großen Wertebereich (1.000.000) verfügen und 2 zufällige Werte benötigen, ist Ihr Ansatz viel besser. Wenn Sie jedoch 999.999 Werte aus demselben Pool benötigen, wird dies mein Ansatz seinviel besser sein noch umstritten sein.

Es dauert einige Zeit, um diese letzten Werte zu generieren. eine Menge, wie Sie sich selbst mit diesem Test können:

void Main()
{
    var random = new Random();
    var times = new TimeSpan[512];
    var values = new bool[512];
    var sw = new Stopwatch();

    for(int i = 0; i < times.Length; i++) 
    {   
        sw.Restart();
        while(true) {
            int rand = random.Next();

            if(rand > 7894500 && rand < 7894512) 
            {
                int index = rand - 7894500;
                if(!values[index])
                {
                    values[index] = true;
                    break;
                }
            }
        }
        sw.Stop();
        times[i] = sw.Elapsed;
        Console.WriteLine ("Elapsed time: " + sw.Elapsed);
    }

    var orderedTime = times.OrderBy(x => x);
    for(int i = 0; i < 512; i++)
    {
        Console.WriteLine (orderedTime.ElementAt(i));
    }
}

Es wird 512 Mal in zufälliger Reihenfolge durch Ihre Liste von Werten durchlaufen und das gefundene Element betrachten, sobald es die (von mir zufällig ausgewählten) Werte zwischen 7894500und gefunden hat 7894512. Danach wird dieser Wert als besucht betrachtet, um die Realität korrekt nachzuahmen (in einer früheren Version standen allen 512 Zügen 512 Werte zur Verfügung). Wenn Sie dies ausführen, werden Sie feststellen, dass es sehr lange dauert, die letzten Werte zu finden (manchmal ist es schnell und dauert 39 ms, manchmal dauert es mehr als eine Minute). Offensichtlich ist es am Anfang schnell und am Ende langsam.

Vergleichen Sie das mit dem Speicher-Overhead meines Ansatzes, der zuerst 32 Millionen Ganzzahlen, Hilfslinien, Füllungen, Objekt-Overhead usw. zuordnet, und Sie haben keinen großen Speicher mehr.

Sie können es möglicherweise verbessern, indem Sie einen "realeren" Mischalgorithmus verwenden, bei dem der Objekt- und Führungsaufwand nicht vorhanden ist.

In einer extremen Situation, in der Sie 32 Millionen eindeutige Werte in einer randomisierten Reihenfolge aus einer Gesamtbevölkerung von 32 Millionen +1 benötigen, müssen Sie entweder einen großen Speicher- oder Ausführungsaufwand in Kauf nehmen.


Eine letzte Bearbeitung, bevor dieses Thema von meinem Teil ruhen kann: Ich habe mit @rolfl im Chat darüber gesprochen, und wir sind zu dem Schluss gekommen, dass eine unserer Lösungen eine Verwendung hat, aber es hängt von Ihrer Situation ab. Zusammengefasst würde es dazu kommen:

Wenn Sie einen großen Wertebereich haben (wie 0 bis int.MaxValue), wird meine Lösung jeden Speicher Ihres PCs fressen . Sie betrachten zwei Sammlungen mit jeweils 2,1 Milliarden ganzen Zahlen, aus denen Sie ein Stück entnehmen.

In meiner Lösung ordnen Sie zuerst die gesamte Population zu, sortieren danach (andere Datenstruktur) und nehmen dann etwas davon. Wenn dieses "einige" nicht in der Nähe von 2,1 Milliarden liegt, haben Sie erhebliche Kosten für die Zuordnung von Daten ohne deren Verwendung aufgewendet.

Wie ist das mit der Antwort von @ rolfl zu vergleichen ? Er ordnet die Daten im Wesentlichen so zu, wie sie benötigt werden: Wenn er 32 Millionen Werte benötigt, weist er nur diese 32 Millionen (x2) zu und nicht mehr. Wenn er 2,1 Milliarden braucht, hat er einen Speicherfußabdruck wie ich, aber das ist ein ungewöhnliches Worst-Case-Szenario, während es für mich Standardverhalten ist.

Der Hauptnachteil seines Ansatzes besteht darin, dass es immer schwieriger wird, diese letzten Werte zu erhalten, wenn die gewünschte Anzahl von Werten die Gesamtbevölkerung erreicht, da viele Kollisionen auftreten. Auch dies wird nur dann ein Problem sein, wenn die Bevölkerung wirklich sehr groß ist.

Wann sollten Sie meine Lösung verwenden? Wie bei den meisten Dingen gibt es einen Kompromiss zwischen Lesbarkeit und Leistung. Wenn Sie eine relativ kleine Bevölkerungszahl und einen großen Datensatz haben, wirkt sich meiner Meinung nach die Lesbarkeit auf die Auswirkungen auf die Leistung aus. Und wenn die Bevölkerung relativ klein ist und die gewünschten Werte in der Nähe sind, hat meine Lösung ähnliche Auswirkungen auf das Gedächtnis wie der andere Ansatz, vermeidet aber auch viele Kollisionen.

Treffen Sie Ihre Wahl je nach Ihrer Situation.

Hervorragende Antwort. Wenn Sie eine Million Zahlen wünschen und 999 999 davon hinzugefügt haben, besteht die Chance, dass die nächste Zahl diejenige ist, die Sie wollen. Simon Forsberg vor 6 Jahren 0
Super Antwort! Ich hätte nie gedacht, dass dieses Problem mit Faulheit gelöst werden könnte. Bruno Costa vor 6 Jahren 0
Sehr ordentlich und unkompliziert. Wenn ich recht habe, wird dies für viele Zahlen gut sein, aber Sie könnten stecken bleiben, wenn Sie versuchen, 3 Zahlen aus 5 Milliarden zu ziehen. Daher habe ich einen alternativen Ansatz hinzugefügt, um dies zu ergänzen. Dennis Jaheruddin vor 6 Jahren 0
-1, da dieser Code nicht mit den Anforderungen des OP kompatibel ist und wahrscheinlich mit einem großen Bereich nicht erfolgreich abgeschlossen werden konnte (MIN- bis MAX-Wert für Int). rolfl vor 6 Jahren 3
Wie entspricht es nicht den Anforderungen? Ich habe eingeräumt, dass dieser Ansatz Nachteile hat und von der Situation abhängig ist. Jeroen Vannevel vor 6 Jahren 0
Wenn Sie 999.999 Werte von 1.000.000 benötigen, erfordert Ihr Code ... ungefähr 16 MB, um die GUIDs zu speichern (vorausgesetzt, sie werden in einem 16-Byte-Wert gespeichert, nicht als String oder etwas anderes) und weitere 4 MB für die int-Werte plus Objekt-Overheads und noch einiges mehr, da bin ich mir sicher. rolfl vor 6 Jahren 2
Ich habe gerade festgestellt, dass ** das OP keinen Parameter für random.Next () ** hat. @rolfl ist richtig. Simon Forsberg vor 6 Jahren 1
Darüber hinaus werden GUIDs nicht als zufällig festgelegt, und die Bestellung über eine GUID führt nicht zu den erwarteten Ergebnissen rolfl vor 6 Jahren 13
Ich bin mir dessen bewusst, ich habe ausdrücklich meine Antwort eingefügt, dass große Datensätze mit wenigen erforderlichen Werten eine große Auswirkung auf den Speicher haben. Es ist ein Kompromiss zwischen Arbeitsspeicher und Ausführungszeit, da das andere Szenario (viele benötigte Werte eines großen Datensatzes) für diesen Ansatz gut ist, aber schlecht für OPs. Jeroen Vannevel vor 6 Jahren 0
@ SimonAndré Forsberg, rolf: Jungs, ich bin damit einverstanden. Das ist eine ziemlich gute Antwort. Kao vor 6 Jahren 0
Sie können O (1) -Speicher erhalten und haben immer noch O (n) -Zeit (und "zufällige" Null-Duplikate), indem Sie eine implizite Pseudo-Zufalls-Permutation verwenden, anstatt den gesamten Satz explizit zu generieren und dann den größten Teil davon wegzuwerfen. Hier gibt es keine Kompromisse außer Faulheit (und die Wahl einer guten Permutation, aber dies ist auch bei nicht-Zwei-Größen-Größen einfach, wenn zum Beispiel eine Luby-Rackoff-Konstruktion verwendet wird, um eine Pseudozufallsfunktion in ein PRP zu verwandeln). Thomas vor 6 Jahren 0
Ich glaube nicht, dass Ihre Sorge, dass der Code des OP in einer Endlosschleife hängen bleibt, eine gültige ist. Das von C # verwendete PRNG hat eine Periode, in der AIUI garantiert für alle Seed-Werte> 2 ^ {56} ist. Das heißt, solange "count" ein vernünftiger Wert ist, sollte es immer ein gültiges Ergebnis liefern. In der Realität ist der Speicher zum Speichern der generierten Werte erschöpft, lange bevor dies ein Problem darstellt. Jules vor 6 Jahren 2
Eine Sortierfunktion ist keine Mischfunktion. Warum generiere ich O (N) neuen Speicher für den Schlüssel und brauche O (N log N) Zeit, um ihn zu sortieren, wenn Sie den Fischer-Yates-Shuffle verwenden können, der O (1) Speicher und O (N) Zeit benötigt? Andrew Piliser vor 6 Jahren 5
22
IEatBagels

Anstelle von a List<int>sollten Sie ein verwenden HashSet<int>. Das HashSet<>verbietet mehrere identische Werte. Die AddMethode gibt ein a zurück bool, das angibt, ob das Element der Liste hinzugefügt wurde. Auf diese Weise könnten Sie diesen Code ändern:

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

zu diesem:

public static IEnumerable<int> GetRandomNumbers(int count)
{
    HashSet<int> randomNumbers = new HashSet<int>();

    for (int i = 0; i < count; i++) 
        while (!randomNumbers.Add(random.Next()));

    return randomNumbers;
}

Beachten Sie, dass ich den Rückgabewert von List<int>in geändert habe. IEnumerable<int>Wenn Sie nicht beabsichtigen, Werte zu Ihrer Liste hinzuzufügen oder zu entfernen, sollten Sie zurückgeben IEnumerable<int>, wenn Sie dies planen, zurückgeben ICollection<int>. Sie sollten a nicht zurückgeben, List<int>da es sich um ein Implementierungsdetail handelt, das List<>nicht erweiterbar ist.

Das Problem bei der Verwendung eines `Sets` ist, dass es nicht bestellt wird. Es gibt keine Möglichkeit, die ganzen Zahlen in eine zufällige Reihenfolge zu bringen. Simon Forsberg vor 6 Jahren 1
@ SimonAndré Forsberg Das OP hat nicht angegeben, dass er es wollte, es sei denn, es fehlt etwas IEatBagels vor 6 Jahren 3
In der Tat sind Sie richtig. Ich habe das Problem völlig falsch verstanden. Simon Forsberg vor 6 Jahren 1
Passiert jedem! IEatBagels vor 6 Jahren 0
Sie sollten ToList dort nicht anrufen. Angenommen, es ist eine großartige Lösung Bruno Costa vor 6 Jahren 0
Sie haben recht, ich habe es angerufen, bevor ich das Ergebnis von List in IEnumerable geändert habe IEatBagels vor 6 Jahren 0
Das sieht nach etwas aus, was ich tun würde, außer ich würde die 'for'-Anweisung loswerden und so etwas wie' while (randomNumber.Count <count) randomNumber.Add (random.Next ()); "tun Clark Kent vor 6 Jahren 0
Ja, jetzt, wo ich die Antwort von Rolfl geprüft habe, ist mir klar, dass ich es so hätte tun können, aber ich habe nicht selbst daran gedacht. IEatBagels vor 6 Jahren 0
Ich fürchte, dass diese Lösung die * Zufälligkeit * der Sequenz erheblich beeinträchtigen wird. Es hängt von der * Hash-Funktion * ab, von der wir nichts wissen. Meine Vermutung ist, dass die Zufälligkeit in den wenigen signifikanten Bits am schlechtesten ist (vorausgesetzt, dass has-function das Argument einfach zurückgibt). Ich werde nicht wählen, keine schlechte Antwort, nicht so gut. firda vor 6 Jahren 0
Sie haben recht, zuerst wusste ich nicht, warum die Reihenfolge zufällig sein sollte. Ich nehme an, meine Antwort ist nicht so gut, aber ich habe sie hier gelassen, wenn man bedenkt, dass es einige nützliche Punkte enthält! IEatBagels vor 6 Jahren 0
HashSet hat keine Reihenfolge. Du könntest einfach an der Nummer zu HashSet, ohne auch nur zufällig zu verwenden. Das ist nicht richtig. paparazzo vor 3 Jahren 0
19
Olivier

Ich möchte meinen Kommentar erweitern. Dies wird als linearer Kongruenzgenerator bezeichnet. Ich habe allgemeine Parameter verwendet, die aus dem, was ich als Minimalstandard bezeichne, stammen. Andere Parameter können ausgewählt werden, aber das ist eine schwierige Aufgabe. Die Sequenz beginnt beim Startwert, erreicht alle anderen Zahlen zwischen 0 und M-1 und startet neu, sobald der Startwert wieder erreicht ist. Es ist pseudo-zufällig. 507111939 folgt immer 285719. Da die Sequenz alle M-Nummern erreicht, werden in M ​​aufeinanderfolgenden Ausgaben der Sequenz keine Duplikate angezeigt.

Code:

class RandomSequence {

  int actual;
  static final int M = (1<<31) -1;

  public RandomSequence(int seed) {
    this.actual = seed
  }

  public int next() {
    return this.actual = (16807 * this.actual) % RandomSequence.M
  }

}

Verwendungszweck :

//...
List<int> awesomeList = new List<int>();
RandomSequence sq = new RandomSequence( RandomUtil.getRandomPositiveIntSmallerThanM() );
for(int i = 0; i < n; i++) {
  awesomeList.add(sq.next());
}
Das ist eine schöne Lösung. Es sollte beachtet werden, dass eine ganze Menge davon aufgrund einer Reihe praktischer Übereinstimmungen in der Berechnungstheorie funktioniert, beispielsweise ist M $ 2 ^ {31} - 1 \ $, was ebenfalls Integer.Max_value ist, und es ist auch eine Primzahl . Primzahl zu sein ist von Bedeutung. 16807 ist auch Primzahl. rolfl vor 6 Jahren 5
kannst du erklären, wovon du redest Muhammad Umer vor 5 Jahren 0
Ich habe über @rolfl gesprochen Muhammad Umer vor 5 Jahren 0
13
ANeves

Der Algorithmus sieht gut aus für mich. Es zeigt keine offensichtlichen Mängel und funktioniert in normalen Anwendungsfällen einwandfrei.
In extremen Fällen der Auswahl der meisten Zahlen in einem sehr großen Intervall ist dies sehr ineffizient. Wenn dies nicht ein erwarteter Anwendungsfall ist, würde ich mich nicht darum kümmern, den Code in kompliziertere Ansätze zu ändern.

Ich schlage jedoch vor, dass Sie immer explizite Klammern um Blöcke verwenden, auch wenn sie eine einzige Anweisung haben:

do
{
    bar();
}
while (foo);

Ich würde die Methode auch umbenennen in GetNRandomNumbers, um den Methodennamen besser auf seinen Zweck abzustimmen.

+1. Normalerweise bin ich für Klammern in der Nähe von Blöcken nicht besonders anstrengend, aber ich denke, in einer "do ... while" -Schleife sind sie besonders wichtig. Ich habe den Code wegen fehlender Klammern zunächst falsch gelesen. Jules vor 6 Jahren 2
Stil war nicht die Frage, oder? Florian F vor 6 Jahren 0
@FlorianF Nein, das war es nicht. Aber der erste Satz in der Antwort besagt, dass der Algorithmus für mich gut aussieht, nicht wahr? Und dann habe ich einige Vorschläge gemacht, um die Widerstandsfähigkeit von Fehlern (mit Klammern) und die Klarheit (Umbenennen) zu verbessern. Könnten Sie versuchen, Ihnen klarer zu machen, was Sie meinen? ANeves vor 6 Jahren 1
@FlorianF Style ist * immer * ein gültiges Ziel für eine Codeüberprüfung. David Harkness vor 6 Jahren 5
Wenn die Frage nicht Stil ist, hilft der Gesprächsstil nicht. Florian F vor 6 Jahren 0
@FlorianF Dies ist *** Code Review ***, nicht Stack Overflow. Rezensenten können * jeden Aspekt des Codes * jederzeit kommentieren. Immer. Mathieu Guindon vor 6 Jahren 8
Gibt es eine Seite, auf der beschrieben wird, wofür jede Site gedacht ist? Florian F vor 6 Jahren 0
@FlorianF [Help Center> Asking] (http://codereview.stackexchange.com/help/on-topic) ist der nächstgelegene, um eine Antwort auf Ihre Frage zu finden * nur für diese Site *. Möglicherweise kennt ein Mod eine Seite, die den Unterschied zwischen den Seiten "Programmierer", "Stapelüberlauf" und "Code Review" beschreibt. Ich habe durch das Lesen der Websites gelernt. David Harkness vor 6 Jahren 0
9
BenGoldberg

Eine andere Lösung ist die Verwendung einer Verschlüsselung zur Verschlüsselung von Formaten (z. B. AES mit FFX-Modus), die so konfiguriert ist, dass 32-Bit-Ganzzahlen auf 32-Bit-Ganzzahlen abgebildet werden.

Zufällige Aussaat, dann verschlüsseln Sie einfach die ersten 'Count'-Ganzzahlen.

Diese verschlüsselten Zahlen sind so zufällig wie der Startwert und werden nicht wiederholt.

Interessante Idee und wahrscheinlich viel schneller als der Code von OPs und rolfl, da dies O (n) und nicht O (n ^ 2) oder O (nlnn) wäre, wie es bei diesen Lösungen der Fall ist. Die Lösung von Jeroen Vannevel ist ebenfalls O (n) und wäre wahrscheinlich noch schneller, kann jedoch nicht plausibel verwendet werden, wenn der erforderliche Bereich der Zufallszahlen zu groß ist. Diese Lösung hat wahrscheinlich den geringsten Speicherbedarf von allen, da die Anzahl auf Anforderung produziert werden kann, anstatt im Voraus berechnet zu werden. Jules vor 6 Jahren 0
8
Bruno Costa

Ich aktualisiere meine Antwort, um eine Analyse des BobFloyd-Algorithmus zu erstellen und alle Fehler zusammenzufassen, die ich dabei feststellen konnte. Einige davon waren in meiner vorherigen Antwort, sie werden auch in Kommentaren von Benutzern wie @rolfl und @firda erwähnt. Bitte folgen Sie der gesamten Antwort, da Sie am Ende eine Überraschung erleben werden.

Lassen Sie mich einige Begriffe definieren, die ich in meiner Antwort verwenden werde. Betrachten Sie die Methodendefinition:

static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)
  • Bereichslänge = max - min + 1
  • genommene Elemente = zählen

Erstes Problem: Die letzten range length - taken elementsElemente dürfen sich nicht immer im Index 0 des Ergebnisses befinden.

Zweite Frage: Die Ergebnisse näher an einer linearen Abfolge wie taken elementsnäher kommt range length. Dies ist leichter zu erkennen, wenn sie gleich sind, aber das Ergebnis ist nicht zufällig, wenn sie nahe sind.

Dritte Ausgabe: Es gibt auch eine dritte Ausgabe, aber ich werde sie am Ende meiner Antwort erwähnen.

Ich habe drei Algorithmen implementiert, um nicht wiederkehrende Zahlen zurückzugeben:

Ein reiner Shuffling-Algorithmus, ein reiner Bob Floyd-Algorithmus und ein Bob Floyd-Algorithmus mit Shuffling. Diese werden später angezeigt, wenn ich sie vergleiche und teste.

Ich habe auch einen Test implementiert, um die Zufälligkeit der ausgegebenen Liste durch einen beliebigen Algorithmus zu überprüfen. Obwohl es einige Einschränkungen hat, reicht es aus Gründen der Vollständigkeit / Richtigkeit der Antwort aus. Für viel falsch kann es sein, dass dies meine Definition des Zufalls sein wird. Hier zähle ich grundsätzlich die Zeiten, zu denen jede Kombination auftritt und ob der Durchschnitt in einem akzeptablen Bereich liegt.

public void TestRandomness(Func<List<int>> getRandomList, int rangeLength, int count)
{
    long combinations = (long)(rangeLength.Factorial(rangeLength - count + 1));
    long iterations = combinations * 100;
    var partitioner = Partitioner.Create(0, iterations, iterations / 4);
    ConcurrentDictionary<long, int> ocurrences = new ConcurrentDictionary<long, int>(Environment.ProcessorCount, (int)combinations);

    Parallel.ForEach(partitioner, new ParallelOptions() {MaxDegreeOfParallelism = Environment.ProcessorCount},
        range =>
        {
            //hopefully having a private dictionary will help concurrency
            Dictionary<long, int> privateOcurrences = new Dictionary<long, int>();
            for (long i = range.Item1; i < range.Item2; ++i)
            {
                var list = getRandomList();
                long acc = 0;
                //this will only work when numbers are between 0 and 88
                foreach (var value in list)
                {
                    acc = (value + 11) + acc*100;
                }
                privateOcurrences.AddOrUpdate(acc, 1, v => v + 1);
            }
            foreach (var privateOcurrence in privateOcurrences)
            {
                ocurrences.AddOrUpdate(privateOcurrence.Key, 
                    privateOcurrence.Value,
                    (k, v) => v + privateOcurrence.Value);
            }
        });

    double averageOcurrences = iterations / combinations;
    double currentAverage = ocurrences.Values.Average();
    Debug.WriteLine("The average ocurrences of this implementation is {0} comparing to {1} in the 'perfect' scenario", currentAverage, averageOcurrences);
    Assert.Less(currentAverage, averageOcurrences * 1.05);
    Assert.Greater(currentAverage, averageOcurrences * 0.95);
}

Beginnen wir mit dem Testen der Zufälligkeit unseres Misch-Algorithmus. Dies ist mein erster Algorithmus:

[Test]
public void TestShuffleRandomness()
{
    TestRandomness(() => Enumerable.Range(0, 16).ToList().Shuffle().Take(4).ToList(), 16, 4);    
}

Pass, Pass, Pass. Dieser Algorithmus respektiert meine Testdefinition der Zufälligkeit. Dies ist sehr nahe an dem, was @Jeroen Vannevel angedeutet hat, mit Ausnahme des Teils, für den dies kein Zufall erfordert, noch läuft es in O (n log n) -Zeit (ich muss auf @Andrew Piliser verweisen, da er der einzige war, der etwas kommentierte darüber).

Wie wir wissen, wird dieser Algorithmus Speicher benötigen, der der Länge O (Range Length) entspricht, und es ist sein größter Nachteil. Es erzeugt jedoch keine Kollisionen und garantiert Zufälligkeit.

Es ist jetzt an der Zeit, die ersten und zweiten Probleme mit dem Bob Floyd-Algorithmus zu beweisen:

public static IEnumerable<int> BobFloydNonRepeatingSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    return values;
}

[Test]
public void TestLastCountElementsAreNotInIndex0()
{
    for (int i = 0; i < 1000000; ++i)
    {
        var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList();
        Assert.IsFalse(new[] { 12, 13, 14, 15 }.Contains(list[0]));
        Assert.AreEqual(4, list.Count);
    }
}

[Test]
public void TestBobFloydBecomesLinear()
{
    var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 16).ToList();
    for (int i = 0; i < list.Count; ++i)
    {
        Assert.AreEqual(i, list[i]);
    }
}

Toll, jetzt haben wir bewiesen, dass der Bob-Floyd-Algorithmus allein dieses Problem nicht löst, und natürlich würde er meinen Zufallstest nicht bestehen.

[Test]
public void TestBobFloydRandomness()
{
    TestRandomness(() => Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList(), 16, 4);
}

Unsere einzige Möglichkeit ist, die Ergebnisse zu mischen und auf das Beste zu hoffen.

public static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    values.Shuffle();
    return values;
}

Mal sehen, was mein Zufallstest dazu sagt:

[Test]
public void TestBobFloydWithShuffleRandomness()
{
    TestRandomness(() => Sequence.NonRepeatingRandomSequence(0, 15, 4).ToList(), 16, 4);
}

Ich hoffe, du hast deine Hoffnungen nicht zu groß gemacht. Mein Zufallstest schlägt fehl, dies ist die dritte und letzte Ausgabe von Bob Floyd, da dies nicht zufällig sein wird. Oder es respektiert zumindest nicht die Definition von Zufall, die ich geliefert habe.

In diesem Abschnitt wird nur über die Implementierung des Bob Floyd-Algorithmus und des Rolfl-Algorithmus diskutiert

Nehmen wir also an, meine Definition von Zufall ist etwas streng oder der von Bob Floyd verwendete Algorithmus ist zufällig genug für Ihre Zwecke. Ich weiß nicht wirklich, was bei der Implementierung fehlt, so dass die Ergebnisse eher zufällig wären, also bleibt nur die Effizienz.

Wie Sie in meiner Implementierung gesehen haben, bekomme ich eine INonRepeatingList von der Methode NonRepeatingListFactory.GetNonRepeatingList.

public class NonRepeatingListFactory
{
    public static INonRepeatingList GetNonRepeatingList(int min, int max, int count)
    {
        long length = max - min + 1;
        if (length / 8 > count * 2 * sizeof(int))
        {
            //if the amount of bytes occupied by the array is greater then the dictionary
            return new RandomIndexNonRepeatingList();
        }
        return new NonRepeatingList(min, max);
    }
}

Diese Methode entscheidet anhand des belegten Speichers, welche Liste verwendet werden soll. Wenn Sie ein HashSet immer wie @rolfl verwenden, bedeutet dies, dass Sie zu viel Speicher beanspruchen, wenn die genommenen Elemente groß sind und die Bereichslänge ebenfalls groß ist. In dieser Situation können Sie den Wert einfach einem Bit zuordnen. Wie viel Unterschied kann es machen? Es ist nur etwa 1 KB Speicher für jede 8 KB-Bereichslänge. Auf der anderen Seite sollten wir ein HashSet verwenden, wenn wir nur wenige Elemente aus einem weiten Bereich verwenden.

public interface INonRepeatingList : IEnumerable<int>
{
    bool Add(int value);
}

internal class NonRepeatingListWithArray : List<int>, INonRepeatingList
{
    private readonly BitArray inList;
    private readonly int min;
    private readonly int max;

    public NonRepeatingListWithArray(int min, int max)
    {
        this.inList = new BitArray(max-min+1);
        this.min = min;
        this.max = max;
    }

    bool INonRepeatingList.Add(int value)
    {
        if (!this.inList[value - this.min])
        {
            this.Add(value);
            this.inList[value - this.min] = true;
            return true;
        }
        return false;
    }
}

internal class NonRepeatingListWithSet : List<int>, INonRepeatingList
{
    private readonly HashSet<int> mapValue = new HashSet<int>();
    private int currentIndex = 0;

    bool INonRepeatingList.Add(int value)
    {
        if (mapValue.Add(value))
        {
            base.Add(value);
            return true;
        }
        return false;
    }
}

Vollständiger Code auf Pastebin

Nach einem kurzen Überblick bemerkte ich, dass ich einen Zufalls-Thread nicht sicher verwendet hatte, aber trotzdem haben sich meine Testergebnisse nicht geändert. Bruno Costa vor 6 Jahren 0
In Ihrer Übersetzung des Bob Floyd-Algorithmus gibt es Fehler. versuchen Sie `Sequence.BobFloydNonRepeatingSequence (8, 14, 3, 7)` - es gibt eine ArgumentOutOfRangeException aus. mjolka vor 6 Jahren 0
@mjolka nochmals vielen Dank. Ich habe meine Antwort entsprechend aktualisiert. Bruno Costa vor 6 Jahren 0
Es gibt immer noch einen Fehler im Bob-Floyd-Algorithmus. `values.Add (i + min)` sollte `values.Add (i + min-1)` sein. mjolka vor 6 Jahren 0
@mjolka Nein, sollte es nicht. Bruno Costa vor 6 Jahren 0
Die Zeile "T: = RandInt (1, J)" im Pseudocode wählt eine Zahl im Bereich "[1, J]", nicht "[1, J)". Der `maxValue`-Parameter von Next ist * exklusiv *. Daher müssen Sie entweder if (! Values.Add (random.Next (min, i + min + 1))) {values.Add (i + min ); } `oder` if (! values.Add (random.Next (min, i + min))) {values.Add (i + min - 1); } `, abhängig davon, ob Sie" max "als inklusiv oder exklusiv behandeln. mjolka vor 6 Jahren 0
Lassen Sie uns [diese Diskussion im Chat fortsetzen] (http://chat.stackexchange.com/rooms/16998/discussion-between-mjolka-and-bruno-costa). mjolka vor 6 Jahren 0
6
Dennis Jaheruddin

Obwohl die Lösung von @Jeroen Vannevel recht einfach ist und für die meisten Zwecke und Zwecke geeignet ist, werden Sie eine besonders schlechte Leistung sehen, wenn Sie nur ein paar Zahlen aus einem sehr großen Bereich wünschen.

In diesem Fall empfehle ich den folgenden Algorithmus:

  1. Wählen Sie eine Zahl aus dem Bereich
  2. Wählen Sie eine Zahl aus dem verbleibenden Bereich
  3. und so weiter ...

Die Implementierung könnte so aussehen:

  1. Wählen Sie eine Zahl zwischen 0 und N
  2. Wählen Sie eine Zahl zwischen 0 und N-1
  3. Und so weiter
  4. Bestimmen Sie, welche Anzahl jede Ihrer Zeichnungen darstellt

Beispiel für 0 bis 10

  1. 4 zeichnen
  2. 7 ziehen
  3. ...
  4. Ergebnisse in: Die 4 steht für 4, die 7 für 8, da dies nun die siebte verfügbare Zahl ist.
Könnten Sie ein Codebeispiel Ihres Algo hinzufügen? IEatBagels vor 6 Jahren 0
Dies funktioniert zwar, führt jedoch zu zusätzlichem Aufwand, wenn Sie beispielsweise 5, 6 randomisiert haben und als nächste Zahl eine 7 erhalten. Ich gehe davon aus, dass Sie beabsichtigen, die 7 in eine 9 zu ändern? (weil 5 und 6 schon weg sind). Simon Forsberg vor 6 Jahren 0
@ SimonAndré Forsberg Genau, Sie müssten es versuchen, wenn der Aufwand den zusätzlichen Aufwand wert ist, aber wenn Sie die Reichweite erhöhen, sollte es einen Wendepunkt geben, an dem dies effizienter wird. Dennis Jaheruddin vor 6 Jahren 0
Dies führt zu deutlich verzerrten Ergebnissen von Zufallszahlen, mit einer spärlichen Verteilung am Anfang der Sequenz und einer zunehmend dichteren Verteilung. rolfl vor 6 Jahren 0
@rolfl Jedes Mal, wenn Sie gleichmäßig zufällig aus den verbleibenden verfügbaren Zahlen auswählen (nicht nur die höheren, als Sie bereits gezeichnet haben), sehe ich nicht, wie die Verteilung verzerrt wäre. - Ich denke, der Matlab-Befehl `RANDPERM (N, K)` ist ungefähr so ​​implementiert. Dennis Jaheruddin vor 6 Jahren 0
@rolfl Ich glaube nicht, dass es schief geht, ich bin mit Dennis dabei. Simon Forsberg vor 6 Jahren 0
Ich sehe die Implikation hier und dass ich den von Ihnen vorgeschlagenen Algorithmus falsch verstanden habe. Sie sind richtig, es gibt keine Schiefe, aber Ihre Antwort lässt einen sehr großen freien Platz bei der Verwaltung des Bereichs zu, insbesondere wenn der Bereich der gesamte gültige 32-Bit-Bereich ist. Sie müssen immer noch alle zuvor ausgewählten Werte durchlaufen, damit sie funktioniert. rolfl vor 6 Jahren 1
Dies muss besser erklärt werden. (Der Teil der zweiten Zahl wird um 1 erhöht, wenn er größer als der erste ist, und der dritte Teil um 2, wenn er größer als beide ist, oder 1, wenn er größer als eins ist, usw.). ANeves vor 6 Jahren 1
Habe das Beispiel etwas erweitert, hoffentlich ist es jetzt klar. Dennis Jaheruddin vor 4 Jahren 0
5
Alan King

Das, was Sie wollen, wird als (Pseudo-) Zufalls-Permutation aller int-Werte bezeichnet. Beachten Sie, dass Sie diese Werte nicht unbedingt in einem Array speichern und neu mischen müssen, um Speicherplatz zu beanspruchen. Sie können sie tatsächlich bei Bedarf über eine "perfekte" Hash-Funktion der Bits in der Variablen "count" generieren .

Beachten Sie, dass Pseudo-Random auch deterministisch bedeutet. Um unterschiedliche Werte für verschiedene Läufe zu erhalten, müssen Sie sicherstellen, dass Sie Ihre Sequenz jedes Mal mit einem anderen Wert "kern".

4
Charles

Sie haben zwei Parameter: die Anzahl N der ganzen Zahlen, die Sie wünschen, und ihre maximale Größe M> = N. Wenn N nahe bei M liegt, z. B. 500 Zahlen im Bereich von 1..1000, dann ist Ihre beste Wette ( mischen die Zahlen 1..M. Zum Beispiel können Sie die ersten N Schritte eines Fisher-Yates-Shuffles auf 1..M ausführen und die benötigten Nummern erhalten.

Andernfalls, wenn M viel größer als N ist, wäre es besser, alle Zufallszahlen auf einmal zu generieren (anstatt zu prüfen, ob sie einzeln in der Liste aufgeführt sind), zu sortieren, Duplikate zu entfernen und neue Elemente hinzuzufügen für den Ersatz benötigt und dann neu gemischt.

Möglicherweise möchten Sie mehr als N-Nummern generieren, um die erwartete Anzahl von Duplikationen zu verarbeiten. Die erwartete Anzahl von Duplikaten beträgt etwa N (N-1) / 2M, so dass Sie beispielsweise N + 1,1N (N-1) / 2M-Nummern in Ihrer Ausgangsliste generieren können.

Duplikate zu sortieren und zu entfernen ist Standard.

Wenn Sie nicht übermäßig generieren, oder wenn Sie es nicht getan haben, können Sie neue Elemente generieren, wie Sie es ursprünglich vorgeschlagen hatten: Generieren Sie eine neue Nummer, testen Sie, ob sie in der Liste enthalten ist, und fügen Sie sie gegebenenfalls hinzu.

Zum erneuten Umschalten können Sie entweder einen Standard-Shuffle verwenden (wie Fisher-Yates, wie oben erwähnt), oder Sie können die ursprüngliche Reihenfolge bei jedem Element speichern und danach sortieren. Wenn Sie dies tatsächlich tun und übergeneriert wurden, ignorieren Sie einfach zusätzliche Elemente am Ende.

Wenn Leistung wichtig ist, können Sie beide Methoden (und möglicherweise mehrere Varianten der zweiten, wie beschrieben) codieren und den Cutoff zwischen den Methoden testen. Ist dies nicht der Fall, funktioniert die zweite Methode in allen Fällen. Wenn Sie sie jedoch nicht benötigen, ist die erste Methode einfacher zu programmieren.

Das OP hat nur einen Parameter, N. Was Sie den zweiten Parameter M nennen, ist im Code als "random.Next ()" fest codiert, was ein M von "Integer.MAX_VALUE" ("2 ^ 31 - 1") impliziert ). rolfl vor 6 Jahren 0
@rolfl: Richtig. Ich wollte die Abhängigkeit von M explizit ausdrücken. Charles vor 6 Jahren 0