Optimierungsproblem: Sehr viele Permutationen testen
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? Irgendwelche Tipps? Vielleicht ein komplett anderer Ansatz (evtl. was mit numpy)? -- Schönen Gruß Hartmut Goebel Dipl.-Informatiker (univ), CISSP, CSSLP Information Security Management, Security Governance, Secure Software Development Goebel Consult, Landshut http://www.goebel-consult.de Blog: http://www.goebel-consult.de/blog/bewertung-pgp-verschlusselung-bei-web.de-u... Kolumne: http://www.cissp-gefluester.de/2010-07-passwoerter-lieben-lernen
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.
Hallo Peter, Am 17.11.2015 um 15:41 schrieb Peter Otten:
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.
Danke für Deinen Input. Ah, daran, innerhalb der Regeln zu sortieren, hatte ich noch gar nicht gedacht. Auch eine Idee - ich glaube aber nicht, dass der den großen Durchbruch bringt. Denn wenn ich trotzdem über die Eigenschaften E1 bis E23 iteriere, und Farbe und Element in den innersten Schleife iteriert werden. bringt das wenig. Ich habe also drei Optimierungs-Stellen: 1. Reihenfolge, in der über die Eigenschaften iteriert wird. Hier anzusetzen halte ich für das interessanteste. Ich würde dann, ehe ich auf die nächste Eigenschaft gehe, prüfen ob die aktuelle Kombination (E1 bis En) überhaupt zulässig ist. Wenn nicht, kann ich es mir sie inneren Schleifen sparen. 2. Reihenfolge der Regeln. Nachdem ich momentan nur "VERBOTEN" habe, kann ich die auch sortieren. 3. Reihenfolge der Prüfungen innerhalb einer Regel. Das ist das, was Du vorgeschlagen hast. 3. ist klar. Wenn ich das noch mit 2. kombiniere, kann ich einiges Sparen. 1. und 2. muss man wohl in Kombination sehen. Stellt sich halt die Frage: was ist die beste Sortierreihenfolge? -- Schönen Gruß Hartmut Goebel Dipl.-Informatiker (univ), CISSP, CSSLP Information Security Management, Security Governance, Secure Software Development Goebel Consult, Landshut http://www.goebel-consult.de Blog: http://www.goebel-consult.de/blog/digitale-burgerrechte-in-der-ara-snowden Kolumne: http://www.cissp-gefluester.de/2011-10-aus-der-schublade-in-die-koepfe
Hartmut Goebel wrote:
Hallo Peter,
Am 17.11.2015 um 15:41 schrieb Peter Otten:
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.
Danke für Deinen Input.
Ah, daran, innerhalb der Regeln zu sortieren, hatte ich noch gar nicht gedacht. Auch eine Idee - ich glaube aber nicht, dass der den großen Durchbruch bringt. Denn wenn ich trotzdem über die Eigenschaften E1 bis E23 iteriere, und Farbe und Element in den innersten Schleife iteriert werden. bringt das wenig.
Ich habe also drei Optimierungs-Stellen:
1.
Reihenfolge, in der über die Eigenschaften iteriert wird. Hier anzusetzen halte ich für das interessanteste. Ich würde dann, ehe ich auf die nächste Eigenschaft gehe, prüfen ob die aktuelle Kombination (E1 bis En) überhaupt zulässig ist. Wenn nicht, kann ich es mir sie inneren Schleifen sparen.
Ob du eine Schleife vorher wegoptimierst oder sie nur nie ausgeführt wird sollte keinen großen Unterschied machen.
2.
Reihenfolge der Regeln. Nachdem ich momentan nur "VERBOTEN" habe, kann ich die auch sortieren.
3.
Reihenfolge der Prüfungen innerhalb einer Regel. Das ist das, was Du vorgeschlagen hast.
3. ist klar. Wenn ich das noch mit 2. kombiniere, kann ich einiges Sparen.
1. und 2. muss man wohl in Kombination sehen. Stellt sich halt die Frage: was ist die beste Sortierreihenfolge?
Pseudo-code: rules = [rule1, rule2, rule3, ...] N = 10000 SAMPLE = get_random_sample(sample_size=N) def selectivity(rule): return N - len(rule.apply(SAMPLE)) rules.sort(key=selectivity, reverse=True) for rule in rules: if rule.is_and() or rule.is_or(): # optimise only # a==A and b==B and ... # or # a==A or b==B or ... rule.subrules.sort(key=selectivity, reverse=rule.is_and()) else: pass # TBD Dieser Ansatz ist natürlich suboptimal, wenn die Regeln nicht unabhängig sind, z. B. im Extremfall die selektivste Regel doppelt vorhanden ist, so dass die zweite Anwendung niemals einen Datensatz ausfiltert.
Hallo, ich sehe hier eigentlich zwei getrennt zu testende Konzepte: - funktioniert mein Regelinterpreter im allgemeinen - habe ich alle meine Regeln korrekt spezifiziert. Sollte der eigentliche Regelinterpreter generisch sein, so kannst Du diesen ja anhand künstlicher Beispiele mit viel weniger Kombinationen testen, damit wäre das Testen dieses Schrittes schon mal effizient möglich. Beim zweiten Schritt hängt es dann davon ab, wie einfach Du Deine Regeln für den generischen Interpreter spezifizieren kannst, dann sollte eine visuelle Inspektion ja schon reichen. Solltest Du Dir allerdings nicht sicher sein ob Dein Regelwerk an sich sinnvoll und korrekt ist, musst Du schon über alle Kombinationen iterieren. Bei 21e12 Kombinationen innerhalb eines Tages müsste brute force ein einzelner Check im Schnitt innerhalb von ca 4 ns auszuführen sein. Wieviele Kombinationen sollen denn am Ende als erlaubt noch übrig bleiben ? Du testest ja über ziemlich viele theoretische Kombinationen und willst dann am Ende schauen ob Dein Regelinterpreter funktioniert. Manuelle Inspektion ist ja nur möglich wenn die Ergebnismenge überschaubar ist. Oder habe ich was falsch verstanden ? Gruss Uwe Am 17.11.15 15:07 schrieb "Hartmut Goebel" unter <h.goebel@goebel-consult.de>:
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?
Irgendwelche Tipps? Vielleicht ein komplett anderer Ansatz (evtl. was mit numpy)?
-- Schönen Gruß Hartmut Goebel Dipl.-Informatiker (univ), CISSP, CSSLP Information Security Management, Security Governance, Secure Software Development
Goebel Consult, Landshut http://www.goebel-consult.de
Blog: http://www.goebel-consult.de/blog/bewertung-pgp-verschlusselung-bei-web.de -und-gmx
Kolumne: http://www.cissp-gefluester.de/2010-07-passwoerter-lieben-lernen
_______________________________________________ python-de maillist - python-de@python.org https://mail.python.org/mailman/listinfo/python-de
Hallo Uwe, Am 17.11.2015 um 17:02 schrieb Schmitt Uwe (ID SIS):
- funktioniert mein Regelinterpreter im allgemeinen
Das verursacht mir keine Kopfschmerzen :-) denn das habe ich mit einem kleinen Regelset und wenigen Eigenschaften schon getestet.
- habe ich alle meine Regeln korrekt spezifiziert. [...] wie einfach Du Deine Regeln für den generischen Interpreter spezifizieren kannst, dann sollte eine visuelle Inspektion ja schon reichen.
Solltest Du Dir allerdings nicht sicher sein ob Dein Regelwerk an sich sinnvoll und korrekt ist, musst Du schon über alle Kombinationen iterieren. [...] Wieviele Kombinationen sollen denn am Ende als erlaubt noch übrig bleiben ? Du testest ja über ziemlich viele theoretische Kombinationen und willst dann am Ende schauen ob Dein Regelinterpreter funktioniert. Manuelle Inspektion ist ja nur möglich wenn die Ergebnismenge überschaubar ist.
Da hast Du des Pudels Kern erwischt. Diejenige, die die Regeln spezifiziert haben, sind komplett unsicher, ob das Regelset überhaupt "vollständig" ist - wobei sie selbst nicht wissen, was "vollständig" sein soll. Wenn ich Deine Antwort so lese, glaube ich, dass das beste ist, wenn die Deine Frage einfach mal weitergebe :-) Vielleicht kommen sie dann von der Idee ab -- ich allerdings um ein nettes Knobelthema.
ein einzelner Check im Schnitt innerhalb von ca 4 ns auszuführen sein.
Oh, das wird knapp :-) Klar, das es so nicht gehen kann. Darum wollte ich ja optimieren.
Oder habe ich was falsch verstanden ?
Du hast es genau richtig verstanden. -- Schönen Gruß Hartmut Goebel Dipl.-Informatiker (univ), CISSP, CSSLP Information Security Management, Security Governance, Secure Software Development Goebel Consult, Landshut http://www.goebel-consult.de Blog: http://www.goebel-consult.de/blog/openstreetmap-karten-in-typo3-einbinden Kolumne: http://www.cissp-gefluester.de/2010-09-mut-zur-beschraenkung
participants (3)
-
Hartmut Goebel -
Peter Otten -
Schmitt Uwe (ID SIS)