Bedingung mit einigen Verzweigungen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
Orioner
Beiträge: 102
Registriert: Mo Dez 10, 2012 10:52 am

Bedingung mit einigen Verzweigungen

Beitrag von Orioner » Sa Apr 29, 2023 6:26 pm

Hallo, erneut.

Ich möchte einer Weltraumkarte, welche aus Sektoren besteht, verschiedene Anomalien zuordnen und die Karte dann anzeigen. Einige Sektoren sollen leer sein. Mein Ansatz ist folgender:

Code: Alles auswählen

for (var i = 0; i < 21 * 21; i++) {
    var rnd = Math.floor(Math.random() * 1000);
    if (rnd < 15) map[i] = "anomaly10.webp";
    else if (rnd < 30) map[i] = "anomaly02.webp";
    else if (rnd < 45) map[i] = "anomaly03.webp";
    else if (rnd < 60) map[i] = "anomaly04.webp";
    else if (rnd < 75) map[i] = "anomaly05.webp";
    else if (rnd < 90) map[i] = "anomaly06.webp";
    else if (rnd < 105) map[i] = "anomaly07.webp";
    else if (rnd < 120) map[i] = "anomaly08.webp";
    else if (rnd < 135) map[i] = "anomaly09.webp";
    else map[i] = "space.webp";
}
Meine Frage: Gibt es eine elegantere Lösung? Wenn ja, würde ich diese gerne erfahren. :)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Bedingung mit einigen Verzweigungen

Beitrag von Xin » Mo Mai 01, 2023 11:22 am

Es kommt ein bisschen darauf an, was Du repräsentieren möchtest...

Hier hast Du offenbar Felder in der Größenordnung von 15. Du nimmst eine Zufallszahl von 0 bis 1000. Die Werte bis 135 zeichnen Besonderheiten aus.
Also statistisch 13,5% sind besonders. In Deiner Implementierung können aber auch überall Besonderheiten sein oder nirgendwo, ist ja zufällig.
Wenn man exakt 13,5% haben wollte, könnte man 13,5%*21*21 also 60 zufällige Felder nehmen und dort eine zufällige Anomalie positionieren. Das reduziert den Aufwand von 421 Schleifendurchläufen auf 60. Aber das macht halt auch was anderes.

Ansonsten hast Du in 86,5% der Fälle keine Anomalie, der Fall ist also hochwahrscheinlich - den würde ich also bevorzugt abfangen, das erspart Dir nämlich die folgenden 9 Abfragen. Die erste Abfrage passt nämlich nur in 1,5% der Fälle, ist also hochwahrscheinlich nicht zielführend, weswegen die Frage möglichst zuletzt gestellt werden sollte.

Du hast 9 Anomalien. 9 entspricht also 13,5%. 100% entspricht dann 66,666. Die Zahl ist nicht schön, aber damit umgehen wir die 15er Schritte. Anders ausgedrückt 1000/15 = 66,666.

Code: Alles auswählen

for (var i = 0; i < 21 * 21; i++) {
    var rnd = Math.floor(Math.random() * 66,666);
    if( rnd >= 10 ) map[i] = "space.webp";

    else if (rnd < 1) map[i] = "anomaly10.webp";
    else if (rnd < 2) map[i] = "anomaly02.webp";
    else if (rnd < 3) map[i] = "anomaly03.webp";
    else if (rnd < 4) map[i] = "anomaly04.webp";
    else if (rnd < 5) map[i] = "anomaly05.webp";
    else if (rnd < 6) map[i] = "anomaly06.webp";
    else if (rnd < 7) map[i] = "anomaly07.webp";
    else if (rnd < 8) map[i] = "anomaly08.webp";
    else if (rnd < 9) map[i] = "anomaly09.webp";
}
Jetzt sieht man noch 9 Abfragen. Das könnt man als binäre Suche aufziehen:

Code: Alles auswählen

    if (rnd < 5) 
    { 
      if( rnd <2 )
      {
        if (rnd == 0) map[i] = "anomaly10.webp";
        else map[i] = "anomaly02.webp";
      }
      else
      {
        if (rnd == 2) map[i] = "anomaly03.webp";
        else if (rnd == 3) map[i] = "anomaly04.webp";
        else map[i] = "anomaly05.webp";
      }
    }
    else if (rnd < 7) 
    {
      if (rnd == 5) map[i] = "anomaly06.webp";
      else map[i] = "anomaly07.webp";
    }
    else 
    {
      if (rnd == 7) map[i] = "anomaly08.webp";
      else map[i] = "anomaly09.webp";
    }
  }
Während Du in Deinem Code also 9 Abfragen in 86,5% der Fälle hast, hat so ein Code maximal 5 Abfragen in 13,5% der Fälle.

Je nach Compilerimplementation macht der Compiler das für einen per Switch. Es kann aber auch eine if-elseif Geschichte draus werden.

Code: Alles auswählen

switch( rnd )
{    
    case 0: map[i] = "anomaly10.webp"; break;
    case 1: map[i] = "anomaly02.webp"; break;
    case 2: map[i] = "anomaly03.webp"; break;
    case 3: map[i] = "anomaly04.webp"; break;
    case 4: map[i] = "anomaly05.webp"; break;
    case 5: map[i] = "anomaly06.webp"; break;
    case 6: map[i] = "anomaly07.webp"; break;
    case 7: map[i] = "anomaly08.webp"; break;
    case 8: map[i] = "anomaly09.webp"; break;
}
[/quote]

Aber man erkennt im ursprünglichen Code auch eine gewisse Redundanz, sobald man die 15er-Schritte rausgenommen hat. Die kann man ausnutzen:

[code]
char const * anomaly[] = { "anomaly10.webp", "anomaly02.webp", "anomaly03.webp", 
   "anomaly04.webp", "anomaly05.webp", "anomaly06.webp", "anomaly07.webp", 
   "anomaly08.webp", "anomaly09.webp" };

for (var i = 0; i < 21 * 21; i++) 
{
    var rnd = Math.floor(Math.random() * 66,666);

    if( rnd >= 10 ) map[i] = "space.webp";
    else map[i] = anomay[rnd];
}
[/quote]

Das reduziert die Abfragen auf genau eine pro Feld.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Bedingung mit einigen Verzweigungen

Beitrag von cloidnerux » Di Mai 02, 2023 5:21 pm

Ein wichtiger Aspekt beim Programmieren ist die Trennung zwischen Daten und Code/Algorithmen.

Dein Algorithmus soll basierend auf einem Zufallswert einen von N Verschiedenen Scenarien auswählen, das ist der Code Teil.
Welche Scenarien das genau sind und wie viele es gibt, ist der Datenteil. Diese musst du voneinander trennen(Pseudocode):

Code: Alles auswählen

List<AnomalyWrapper> Anomalies = {anomaly0, anomaly1,...anomalyN};

//With 10 entries and 13.5% equal chance we can get a random number between 0 and 10*13.5
//Divide that by 10 and we get one of the 10 indices 
int GetRndAnomalyIndex(int count, float percentage){
    //Check that count is > 0 and percentage is either between 0 and 1 or 0 and 100
    int maxCount = count * percentage;
    int rnd = random() % maxCount;
    return floor(rnd / percentage);
}
//....
PlayAnomaly(Anomalies[GetRndAnomalyIndex(Anomalies.Count, 13.5)]);
In diesem Ansatz ist der Algorithmus komplett Agnostisch bezüglich deiner Daten(Anzahl Anomalien und Verteilung).
Jetzt kann man das noch weiter auf die Spitze treiben und jeder Anomlie einen eigenen Häufungswert geben.

Code: Alles auswählen

Anomalies[0].occurence = 100;
Anomalies[1].occurence = 10;
...
Dann muss der Algorithmus etwas angepasst werden:

Code: Alles auswählen

int GetRndAnomalyIndex(List<AnomalyWrapper> * anomalies, float percentage){
    //Check that count is > 0 and percentage is either between 0 and 1 or 0 and 100
    int maxCount = anomalies->count * percentage;
    int rnd = random() % maxCount;
    for(int i = 0; i < anomalies->count; i++){
    	if(rnd < anomalies[i].occurence) return i;
    	rnd -= anomalies[i].occurence;
    }
    return anomalies->count - 1;
}
Man würde dann diese Parameter aus einer Datei Laden und den Code agnostisch halten.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Bedingung mit einigen Verzweigungen

Beitrag von Xin » Di Mai 02, 2023 6:52 pm

cloidnerux hat geschrieben:
Di Mai 02, 2023 5:21 pm
//With 10 entries and 13.5% equal chance we can get a random number between 0 and 10*13.5
Die 13,5% ist die statistische Wahrscheinlich in dem Algorithmus, keine Vorgabe.
cloidnerux hat geschrieben:
Di Mai 02, 2023 5:21 pm
Man würde dann diese Parameter aus einer Datei Laden und den Code agnostisch halten.
Das kann man machen, aber auch das ist keine Anforderung an den ursprünglichen Algorithmus.

Die Frage ist hier, ob das für Orioner hilfreich ist, den Algorithmus mit Möglichkeiten vollzustopfen, wenn er sich erstmal darüber informieren möchte, wie man die if-Abfragen optimieren kann.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten