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?

    Gefällt mir

  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.

    Gefällt mir

  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.

    Gefällt mir

  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

  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.