[Python-de] Optimierungsproblem: Sehr viele Permutationen testen

[Hartmut Goebel]

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