Hartmut Goebel wrote:
Hallo zusammen,
ich habe einen kleinen Regelinterpreter (siehe unten) geschrieben - also eine DSL, bei dem ich nun testen möchte, wie groß der Abdeckungsgrad ist. dazu permutiere ich über alle möglichen Kombinationen der Eingabe-Werte. Dummerweise habe ich 25 Parameter, mit bis zu 6 oder 7 Werten, sodass ich auf 21*(10**12) Kombinationen komme. Ich habe den Regelinterpreter schon so umgebaut, dass er Cython-Code erzeugt, nur Integer-Werte verwendet der Kern komplett in C umgesetzt wird. Trotzdem komme ich auf eine Laufzeit von geschätzt 200 Tagen :-\
Daher suche ich nun einen Weg, den Algorithmus wesentlich zu Beschleunigen. Momentan habe ich 25 geschachtelte, dumme Schleifen über alle Werte.
Regeln sind etwas wie (hier frei erfunden): VERBOTEN(Farbe == Grün and Material == Wasser) VERBOTEN(Typ == Zug and Zeit == nachts and Berechtigung == Tagschein)
Wie Ihr seht, prüfen einzelne Regeln nur sehr wenige Parameter, trifft aber eine Aussage für einen riesiger Bereich., den ich dann gar nicht mehr prüfen muss, Einige der Parameter kommen auch nur in einer oder zwei Regeln vor. Insgesamt habe ich ca. 50 Regeln
Meine Idee ist nun, die Schleifen so zu sortieren, dass die Regeln, die häufig zutreffen, schon in äußeren Schleifen geprüft werden. Nur: nach was sortiere ich? Anzahl der geprüften Parameter? Anzahl möglicher Werte eines Parameters?
Selektivität der Regel. VERBOTEN(Farbe==Rot und Element=Feuer) Unter der Annahme, dass du 1. 100 Farben und vier Elemente unterscheidest, dass 2. sich die getesteten Eingaben gleichmäßig über Elemente und Farben verteilen, und dass 3. jeder Test gleich lange dauert solltest du natürlich zuerst die Farbe testen -- der Test des Elements entfällt dann in 99 von 100 Fällen. Hättest du zuerst das Element überprüft, wäre der zweite Test nur in 75% entfallen. Genauso kannst du die komplette Regel behandeln, die im Beispiel in 1-1/99*1/4 = 99.75% der Fälle den Test auf weitere Verbote erübrigt.