Random Int ohne duplicates

  • C#
  • .NET (FX) 1.0–2.0

Es gibt 28 Antworten in diesem Thema. Der letzte Beitrag () ist von Niko Ortner.

    Random Int ohne duplicates

    Hey,
    Also, ich möchte folgendes optimieren :
    Ich generiere viele random integer werte.
    Allerdings möchte ich das kein Wert doppelt ausgespuckt wird.
    Die banale (ineffiziente) methode hierfür wäre:

    1) int generieren.
    2) Prüfen ob List<int> contains random int
    3) wenn nicht enthalten add zur list und returne wert. Andernfalls, neuen int generieren und check wiederholen.

    Das problem ist wenn man bspw millionen von werten generieren möchte, müsste man jedes mal die ganze liste prüfen (mit contains()).
    Und da diese stetig wächst müssten immer mehr werte geprüft werden, nach einer weile wäre das sehr zeitintensiv, man prüft 1000000 elemente, dann 1000001 dann 1000002 usw....

    Was wäre eine effizientere methode die kein redundantes prüfen der liste erfordert?
    C# Developer
    Learning C++
    Ich sehe hier zwei mögliche Ansätze:
    1. Direkt verhindern, dass Dopplungen überhaupt entstehen. Dies könnte durch geschicktes Teilen des Ergebnisraums erreicht werden, was aber die Verteilung der berechneten Pseudozufallszahlen beeinflusst. Wenn sich ein Workaround finden ließe oder dieser Umstand kein Problem darstellt, ist das die beste Möglichkeit.
    2. Das Prüfen auf Dopplungen beschleunigen. Die direkteste Umsetzung dafür wäre die Wahl einer geeigneteren Datenstruktur, mir kommen da spontan BinaryTree oder HashTable in den Sinn, müsste man dann gegebenenfalls untersuchen, ob eine HashTable unter diesen Bedingungen tatsächlich schneller ist, als der Baum.
    Vielleicht lässt sich für dieses spezielle Problem aber auch eine spezifische, besser geeignete Datenstruktur entwerfen (wenn man z.B. mal an Bucket Sort denkt, das für zufällige gleichverteilte Zahlen in Linearzeit läuft). Das wird aber wohl eher noch schwerer als Punkt 1.
    Gut, dann hab ne Liste von ... bis ..., und initialisiere sie überall mit dem Wert n. Dann generierst du deinen Random Int, checkst die Zahl am Index des Randoms, und zeihst einen ab. Es sei denn der Wert da ist schon 0.
    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais
    Hallo Rikudo

    Den Vorschlag von @Plexian finde ich gut.

    Was spricht dagegen, wenn du eine Array oder List of Integer nimms mit deinem Randombereich.

    VB.NET-Quellcode

    1. Sub Main()
    2. 'Den Random Bereich
    3. Dim lst As New List(Of Integer)
    4. For i As Integer = 0 To 1000000000 'Deinen Bereich
    5. lst.Add(i)
    6. Next
    7. 'Dann gut durchmischen
    8. '>> Lass dir da was einfallen
    9. End Sub


    Von dieser List of nimmst du dann per random irgend einen Index und markierst den Wert oder führst eine zweite List of mit den Indexwerten damit du weist welche schon benutzt sind.

    So hast du wunderbar einen Möglichkeit die dir gewährleistet das eine Zahl nie doppelt vorkommt

    Freundliche Grüsse

    exc-jdbi
    Erstell einen Array wie z.B.

    VB.NET-Quellcode

    1. Dim d(99) As Integer
    2. For i As Integer = 0 To 99
    3. d(i) = (i * 2) ' Zuweisung muss eine Zahl sein, die nicht vorkommt.
    4. Next


    Dann nimmst du eine gewisse Anzahl der Indices erzeugt mit dem SwappingRandomIndexGenerator

    Die Benutzung sollte kein großes Problem darstellen.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „3Angle“ ()

    Kannst du ein bisschen mehr über eventuelle Beschränkungen erzählen? Also z.B.:
    - müssen die Zufallszahlen aus einem bestimmten Intervall kommen? Oder dachtest du an [0, Int32.MaxValue)
    - ist "guter Zufall" wichtig oder reicht es, wenn es dem Anwender zufällig erscheint?
    - wie viele Zahlen willst du ca. ziehen?
    - ...
    also standardmäßig löst man das mittm Fisher-Yales-Shuffle-Algo.
    Dabei wird zunächst eine sortiert Lister erzeugt, und der Shuffle würfelt die anschließend durcheinander.

    ah - hier isser:

    VB.NET-Quellcode

    1. Private _Rnc As New Random
    2. <Extension(), DebuggerStepThrough()> _
    3. Public Sub Swap(items As IList, I1 As Integer, I2 As Integer)
    4. Dim Tmp = items(I1)
    5. items(I1) = items(I2)
    6. items(I2) = Tmp
    7. End Sub
    8. ''' <summary> Fisher-Yates-Mixing up the itms. On seed&lt;0 the random seed is used </summary>
    9. <Extension(), DebuggerStepThrough()> _
    10. Public Sub Shuffle(itms As IList, Optional seed As Integer = -1)
    11. If seed >= 0 Then _Rnc = New Random(seed)
    12. For i = itms.Count - 1 To 1 Step -1
    13. itms.Swap(i, _Rnc.Next(i + 1))
    14. Next
    15. End Sub

    *Unnötiges Zitat entfernt*

    Dann wäre aber von Anfang an die Anzahl fest vordefiniert (Listengrößer) und nicht bei bedarf erweitert oder?

    @3daycliff :

    - Sagen wir ein "Zufall" mit der Randomklasse reicht aus, keine Crypto-Random notwendig.
    - Ein meinem Fall sinds nicht so viele, ca 500-1000, - ich möchte jedoch trotzdem die List.Contains() methode vermeiden, auch wenn es vermutlich "ausreichend schnell" wäre.
    Schließlich hab ich als Programmierer ja die Ambition einen effizienten weg zu coden, und nicht nur einen der zwar irgendwie funzt, aber halt nicht so elegant ist.
    - Die Liste mit den Zufälligen zahlen soll bei Bedarf zu jedem Zeitpunkt um x beliebige elemente erweiterbar sein, d.h. es läuft NICHT zu beginn eine schleife die bei jeder iteration ne
    random Zahl reinpackt, sondern, kann zu jeder Zeit einen neuen random int bekommen, der eben noch nicht geadded worden sein darf.
    - Elemente aus der Liste/Array dürfen nicht nach der Verwendung entfernt werden!
    - Als Intervall dachte ich an 0 bis Int32.MaxValue
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Marcus Gräfe“ ()

    Rikudo schrieb:

    Dann wäre aber von Anfang an die Anzahl fest vordefiniert (Listengrößer) und nicht bei bedarf erweitert oder?
    jo.
    Sonst musste halt mit Hashset arbeiten, was sich merkt, welche schon drangewesen sind. Das ist aber glaub viel langsamer als der Fisher-Yates, der nur zweimal drüber laufen muss (1. Generieren, 2. Vertauschen).
    Auch braucht ein Hashset mehr Speicher - das muss sich ja genau so groß aufblähen, wie du Items generierst.

    Also eine unendliche Zufalls-Zahlenfolge ohne Wiederholungen ist technisch - nein, bereits konzeptionell - nicht machbar.
    @ErfinderDesRades : Idee ist wie folgt :

    Ich analysiere daten und nach einer bestimmten condition möchte ich einen random integer generieren und diesen zu der Liste adden in der ich alle
    random ints sammel. Und wie ebreits gesagt soll der gewählte random integer nicht bereits vorhanden sein.
    D.h. es wird nicht am Anfang eine Liste mit x random zahlen initalisiert sondern zur laufzeit, und es sollen jederzeit neue ints generiert und geadded werden können.
    Da funzt dein Fisher Yates ansatz leider nicht so elegant ;}
    Wie würdest du es denn mit einem hashset lösen?
    Was schwebt dir da vor?
    C# Developer
    Learning C++
    nö - hashset heißt hashset

    VB.NET-Quellcode

    1. Private _Rnd As New Random
    2. Private _AlreadyUsed As New HashSet(Of Integer)
    3. ''' <summary> returns non-negative Integers without repetitions </summary>
    4. Private Function GetNextInt() As Integer
    5. Do
    6. Dim i = _Rnd.Next()
    7. If _AlreadyUsed.Add(i) Then Return i
    8. Loop
    9. End Function
    ansonsten ja- es ist das Vorgehen aus post#1

    (Bei Fragen zur Funktion: Bitte schaut euch die Hashset-Klasse erstma im ObjectBrowser an)

    Rikudo schrieb:

    bei bedarf erweitert
    Mach Dir ne separate Klasse, die Dir eine Liste unärer Mischwerte für eine vorgegebene Anzahl erzeugt, da hast Du genau einen Aufruf pro neuer Anzahl, und die Erstellung geht auch recht fix.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Eine Liste mit noch verfügbaren / schon gezogenen Zufallszahlen ist die einfachste Möglichkeit. Mathematisch schicker geht es z.B. mit einem LCG. Im Prinzip nutzen das auch die meisten Bibliotheken für einen schnellen "normalen" Zufallsgenerator. Hier mal Quick&Dirty implementiert:

    C#-Quellcode

    1. class UniqueRandom {
    2. private int m;
    3. private int a;
    4. private int b;
    5. private int x;
    6. private int seed;
    7. public UniqueRandom(int seed) : this(2<<30, 1103515245, 12345, seed) {
    8. }
    9. protected UniqueRandom(int m, int a, int b, int seed) {
    10. // conditions: 0<m, 0<a<m, 0<=b<m, 0<=seed<m
    11. // full period iff
    12. // - gcd(m,b) = 1
    13. // - a-1 is divisible by all prime factors of m
    14. // - m is divisible by 4 ==> a-1 is divisible by 4
    15. if(seed < 0 || seed > m) {
    16. throw new ArgumentException();
    17. }
    18. this.m = m;
    19. this.a = a;
    20. this.b = b;
    21. this.seed = this.x = seed;
    22. }
    23. public int Next() {
    24. x = (int)(((long)a * (long)x + (long)b) % m);
    25. if(x == seed) {
    26. throw new InvalidOperationException();
    27. }
    28. return x;
    29. }
    30. }


    Habe das mangels Compiler aber nicht getestet, daher bitte mit entsprechender Vorsicht genießen und ggf. selbst noch mal recherchieren. Hoffe die Werte für m, a und b passen, damit eine volle Periode herauskommt. Damit solltest du "Zufallszahlen" aus dem Intervall[0, 2^31) bekommen, ohne das eine doppelt vorkommt. Es sei dann natürlich du ziehst 2^31 Stück...

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „3daycliff“ () aus folgendem Grund: Typo...