Theorie und Praxis des Zufalls //2306

Nur mal wieder ein kleiner Gedankengang.
Die Aufgabe beruht auf einem realen Programmierprojekt. Ich habe sie aber etwas abgewandelt und vereinfacht, um die Angelegenheit verständlicher zu machen.

Gegeben ist eine indizierte Liste mit – sagen wir – 25 unterschiedlichen Optionen.
Aus diversen Gründen können davon aber fünf Optionen nicht wahrgenommen werden. Welche das sind, ergibt sich erst zur Laufzeit. (Strenggenommen können es auch weniger als fünf sein, da die entsprechenden Optionen eventuell aus mehreren Gründen ausfallen, und dann teilweise identisch sind. Wir bleiben bei unserem Beispiel beim festen Wert 5.)
Ich möchte jetzt also – zufallsgesteuert – aus den verbleibenden Optionen eine auswählen.
Also werfe ich den Zufallsgenerator an, und lasse mir eine ganze Zahl zwischen 0 und 24 ausgeben. Dann prüfe ich nach, ob die Option mit diesem Index zulässig ist. In 80 Prozent der Fälle habe ich die endgültige Option bereits gefunden. Ansonsten mache ich einen weiteren Durchlauf, so lange, bis ich eine zulässige Option erhalte.
Das „Problem“ ist, dass ich rein theoretisch mit diesem Algorithmus in eine Endlosschleife geraten könnte.

Gehen wir mal davon aus, dass das Programm 1000 mal läuft. In 800 Fällen wird das Ergebnis (rein statistisch) auf Anhieb geschafft. In 160 weiteren beim zweiten Durchlauf. 32 Fälle brauchen drei Versuche. Bei nur 8 Fällen sind 4 oder mehr Durchläufe nötig.
Selbst wenn es 1000 Durchläufe wären, ginge das bei einem modernen Rechner ohne merkliche Zeitverzögerung. Aber rein mathematisch betrachtet, geht halt die Wahrscheinlichkeit, dass die Schleife (ohne zusätzliches Abbruchkriterium) endlos weiterläuft, nur asymptotisch gegen 0.
In der Praxis ist das jedoch kein Thema, und ich bin da einfach pragmatisch. Wie sollte das Programm auch reagieren, falls es tatsächlich mal nach tausend oder meinetwegen einer Million Durchläufen immer noch kein passendes Ergebnis gefunden hat?
Sofern man das Programm nur oft genug laufen lässt, wird allerdings auch das irgendwann mal passieren.

Während die genauen Zahlenwerte für den betrachteten Use Case eigentlich unerheblich sind, kann sich das Blatt durchaus wenden, wenn nur wenige erlaubte Optionen einer großen Zahl von ausgeschlossenen Werten gegenüberstehen.
Nehmen wir mal den umgekehrten Fall an: 20 unbrauchbaren Optionen stehen nur 5 akzeptable gegenüber. Bei insgesamt 1000 Läufen schaffen es auf Anhieb nur 200, beim zweiten Versuch 160, beim dritten 128, .. Wie man sieht, konvergiert die Sache wesentlich schlechter.
In diesem Fall wäre es wohl zweckmäßiger, von Anfang an einen anderen Algorithmus zu nutzen – z.B. sämtliche Optionen zufällig durchzumischen, und dann die Liste durchiterieren, um die erste gefundene erlaubte Option zu nehmen. Oder die verbotenen Optionen aus der Liste zu entfernen, um danach eine zufällige aus den verbliebenen zu nehmen. Oder .. Die beste Wahl hängt von der konkreten Ausgestaltung sowie weiteren Parametern und Zusatzbedingungen der Aufgabe ab.
Dass nicht schon von vornherein ein anderer Algorithmus benutzt wurde, hat historische Gründe. Ursprünglich stellte sich die Aufgabe einfacher dar, und die Notwendigkeit des Ausschlusses einzelner Optionen war noch nicht abzusehen gewesen. Flickwerk wie so vieles.

Über Anne Nühm (breakpoint)

Die Programmierschlampe.
Dieser Beitrag wurde unter Uncategorized abgelegt und mit , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.

17 Antworten zu Theorie und Praxis des Zufalls //2306

  1. keloph schreibt:

    Ein entfernen der getroffenen nicht erlaubten Optionen vermute ich ist nicht erlaubt, da falsches Problem?

    Liken

  2. noch1glaswein schreibt:

    Sie könnten am Anfang eine Default Option bestimmen (eine der erlaubten) und nach einer definierten Anzahl von erfolglosen Versuchen, diese nehmen. Wobei – ich denke, die Lösung haben Sie bereits geprüft und Sie schreiben das hier nur als interessantes Problem.

    Liken

  3. Leser schreibt:

    Ich hätte auch gesagt: Sowie zur Laufzeit eine Option als nicht erlaubt bekannt wird, diese aus dem Pool der zufällig zu wählenden Optionen entfernen, den Zufallsgenerator entsprechend anpassen.

    Liken

    • Nein, auch Optionen, die an dieser Stelle nicht in Frage kommen, werden an anderer Stelle noch gebraucht.
      Aus bestimmten Gründen ist es auch nötig, dass der gesetzte Index erhalten bleibt.

      Liken

      • Leser schreibt:

        Dann die Liste der Optionen (bzw. der Indize) kopieren, und damit die Zufallsauswahl teffen, so dass man in der Kopie frei Werte entfernen kann, ohne die ursprüngliche Liste zu beeinflussen?

        Gefällt 1 Person

        • Ja, wäre eine Möglichkeit. Hätte ich vielleicht auch so gemacht, wenn von Anfang an klar gewesen wäre, dass nicht alle Optionen gewählt werden dürfen.
          Eigentlich wollte ich mit diesem Eintrag nur rechtfertigen, dass eine nachträgliche Umstellung des benutzten Algorithmus nicht notwendig und zu aufwendig ist, solange der Anteil der „verbotenen“ Optionen relativ gering ist.

          Liken

  4. HansG schreibt:

    Da es sich ja bereits um Flickwerk handelt, würde ich ganz simpel eine Zufallszahl ziehen und im Falle einer unzulässigen Option um 1 erhöhen bis eine zulässige Option gefunden wurde. Falls der Index 25 erreichen sollte, wird er schlicht auf 0 zurücksetzt.

    So würde bei garantiert endlicher Laufzeit die Liste der Optionen weder in Umfang noch Reihenfolge manipuliert.

    Gefällt 2 Personen

    • Ja, so etwas ähnliches hatte ich mir auch überlegt. Aber solange nur ziemlich wenige Optionen nicht zulässig sind, werde ich mir die Mühe der Änderung sparen.
      Falls doch noch mehr Optionen wegfallen sollten, wäre das aber dann wohl die zweckmäßigste Implementation.

      Gefällt 1 Person

    • db schreibt:

      Das könnte den Nachteil einer Ungleichverteilung haben, falls bestimmte Optionen häufiger ausfallen als andere: Deren Teil-Wahrscheinlichkeit wird dann ja jeweils an die Folgende weitergereicht. Beispiel: Die „9“ ist besonders oft nicht erlaubt, dann wird die „10“ wohl überdurchschnittlich oft ausgewählt.
      Etwas anderer Ansatz: Eine zufällige Ganzzahl in [1… Anzahl gültiger Optionen] wählen und dann die Liste abgehen, aber nur gültige Optionen zählen.

      Gefällt 1 Person

      • Das stimmt.
        Optionen unmittelbar hinter einer (oder gar mehreren) verbotenen Optionen kämen öfter dran.
        Das wäre in dem kleinen Projektchen, das den Anlass für diesen Post gab, allerdings zu verschmerzen.

        Es ist immer wieder faszinierend, wie auf den ersten Blick simple Aufgaben doch nicht ganz so trivial sind, wenn man sie genauer betrachtet.

        Liken

  5. Pingback: Tweets und Twittereien //2424 | breakpoint

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google Foto

Du kommentierst mit Deinem Google-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.