Die folgenden Fragen
und ihre jeweiligen Antworten ließen mich darüber nachdenken, wie ich einen einzigen mathematischen Ausdruck parsen konnte (im Allgemeinen in Anlehnung an diese Antwort Ссылка ) von einem (mehr oder weniger vertrauenswürdigen) Benutzer effizient für 20k bis 30k Eingabewerte aus einer Datenbank gegeben. Ich habe einen schnellen und schmutzigen Benchmark implementiert, damit ich verschiedene Lösungen vergleichen konnte.
%Vor%# Lösung # 1: eval [ja, total unsicher]
%Vor%# Lösung # 2a: sympy - evalf ( Ссылка )
%Vor%# Lösung # 2b: sympy - lambdify ( Ссылка )
%Vor%# Lösung # 2c: sympy - lambdify mit numexpr [und numpy] ( Ссылка )
%Vor%# Lösung # 3a: asteval [basierend auf ast] - mit String-Magie ( Ссылка )
%Vor%# Lösung # 3b (M Newville): asteval [basierend auf ast] - parse & amp; run ( Ссылка )
%Vor%# Lösung # 3c (M Newville): asteval [basierend auf ast] - parse & amp; renne mit numpy ( Ссылка )
%Vor%# Lösung # 4: simpleeval [basierend auf ast] ( Ссылка )
%Vor%# Lösung # 5 numexpr [und numpy] ( Ссылка )
%Vor%Auf meiner alten Testmaschine (Python 3.4, Linux 3.11 x86_64, zwei Kerne, 1.8GHz) bekomme ich folgende Ergebnisse:
%Vor%Was heraussticht, ist die unglaubliche Geschwindigkeit von eval , obwohl ich das im wirklichen Leben nicht benutzen möchte. Die zweitbeste Lösung scheint numexpr zu sein, was von numpy abhängt - eine Abhängigkeit, die ich vermeiden möchte, obwohl dies keine schwierige Anforderung ist. Die nächstbeste Sache ist simpleeval , die um ast herum aufgebaut ist. aeval , eine weitere astbasierte Lösung, leidet darunter, dass ich jeden einzelnen Float-Input-Wert zuerst in einen String umwandeln muss, um den ich keinen Weg finden konnte. sympy war anfangs mein Favorit, weil es die flexibelste und scheinbar sicherste Lösung bietet, aber letztendlich mit einer beeindruckenden Distanz zur vorletzten Lösung.
Update 1 : Es gibt einen viel schnelleren Ansatz mit sympy . Siehe Lösung 2b. Es ist fast so gut wie numexpr , obwohl ich nicht sicher bin, ob sympy es tatsächlich intern verwendet.
Update 2 : Die sympy Implementierungen verwenden jetzt sympify anstelle von simply (wie vom führenden Entwickler empfohlen) , asmeurer - danke). Es wird numexpr nicht verwendet, es sei denn, es wird explizit dazu aufgefordert (siehe Lösung 2c). Ich fügte auch zwei wesentlich schnellere Lösungen basierend auf asteval hinzu (danke an M Newville).
Welche Möglichkeiten habe ich, um die relativ sichereren Lösungen noch weiter zu beschleunigen? Gibt es andere, sichere (-ish) Ansätze, die zum Beispiel direkt verwenden?
Da Sie nach asteval gefragt haben, ist eine Möglichkeit, es zu verwenden und schnellere Ergebnisse zu erzielen:
%Vor% Das heißt, Sie können zuerst die Benutzereingabefunktion parsen ("vorkompilieren") und dann jeden neuen Wert von x in die Symboltabelle einfügen und den Interpreter.run() verwenden, um den kompilierten Ausdruck für diesen Wert auszuwerten . Auf Ihrer Skala glaube ich, dass Sie damit in die Nähe von 0,5 Sekunden kommen.
Wenn Sie numpy verwenden möchten, eine Hybridlösung:
sollte viel schneller sein und in der Laufzeit mit numexpr vergleichbar sein.
CPython (und pypy) verwenden eine sehr einfache Stapelsprache zum Ausführen von Funktionen, und es ist ziemlich einfach, den Bytecode selbst zu schreiben, indem man das ast-Modul verwendet.
%Vor% Dies hat den entscheidenden Vorteil, dass im Wesentlichen die gleiche Funktion wie eval erzeugt wird, und es skaliert fast genau so wie compile + eval (der Schritt compile ist etwas langsamer als eval , und eval berechnet alles vorberechnen ( 1+1+x wird als 2+x kompiliert).
Zum Vergleich beendet eval Ihren 20k-Test in 0,0125 Sekunden und makefunction endet in 0,014 Sekunden. Erhöhen der Anzahl der Iterationen auf 2.000.000, eval endet in 1.23 Sekunden und makefunction endet in 1.32 Sekunden.
Interessant ist, dass pypy erkennt, dass eval und makefunction im Wesentlichen die gleiche Funktion erzeugen, so dass die JIT-Aufwärmung für die erste die Sekunde beschleunigt.
Ich bin kein Python-Codierer, daher kann ich keinen Python-Code liefern. Aber ich denke, ich kann ein einfaches Schema zur Verfügung stellen, das Ihre Abhängigkeiten minimiert und trotzdem ziemlich schnell läuft.
Der Schlüssel hier ist, etwas zu bauen, das nah an eval ist, ohne eval zu sein. Also, was Sie tun wollen, ist "kompilieren" Sie die Benutzer-Gleichung in etwas, das schnell ausgewertet werden kann. OP hat eine Reihe von Lösungen gezeigt.
Hier ist ein weiterer basierend auf der Auswertung der Gleichung als Reverse Polnisch .
Nehmen wir an, dass Sie die Gleichung in RPN (umgekehrte polnische Notation) umwandeln können. Dies bedeutet, dass Operanden vor Operatoren stehen, z. B. für die Benutzerformel:
%Vor%Sie erhalten RPN-Äquivalent von links nach rechts:
%Vor%Tatsächlich können wir "Operanden" (z. B. Variablen und Konstanten) als Operatoren behandeln, die Nulloperanden verwenden. Jetzt ist in RPN immer ein Operator.
Wenn wir jedes Operatorelement als ein Token behandeln (nehmen Sie für jedes eine eindeutige kleine ganze Zahl an, die als " RPNelement " geschrieben ist) und speichern Sie sie in einem Array "RPN", können wir eine solche Formel auswerten einen Pushdown-Stack ziemlich schnell verwenden:
%Vor%Sie können die Operationen für Push und Pop inline ausführen, um das Bit zu beschleunigen. Wenn das mitgelieferte RPN gut gebildet ist, ist dieser Code vollkommen sicher.
Nun, wie bekommt man das RPN? Antwort: Erstellen Sie einen kleinen rekursiven Descent-Parser, dessen Aktionen RPN-Operatoren an das RPN-Array anhängen. Siehe meine SO-Antwort, wie man leicht einen rekursiven Descent-Parser baut für typische Gleichungen.
Sie müssen organisieren, um die Konstanten beim Analysieren in K1, K2, ... zu setzen, wenn sie keine speziellen, häufig vorkommenden Werte sind (wie ich für "0" und "1" gezeigt habe; Sie können hinzufügen mehr wenn hilfreich).
Diese Lösung sollte höchstens einige hundert Zeilen umfassen und hat keine Abhängigkeiten von anderen Paketen.
(Python-Experten: Fühlen Sie sich frei, den Code zu bearbeiten, um ihn zu einem Pythonschen zu machen).
Ich habe die C ++ ExprTK -Bibliothek in der Vergangenheit mit großem Erfolg genutzt. Hier ist ein Benchmark-Geschwindigkeitstest unter anderen C ++ - Parsern (zB Muparser, MathExpr, ATMSP usw.) und ExprTK kommt an die Spitze.
Es gibt einen Python-Wrapper für ExprTK namens cexprtk , den ich benutzt habe und der sehr schnell ist. Sie können den mathematischen Ausdruck nur einmal kompilieren und dann diesen serialisierten Ausdruck so oft wie erforderlich auswerten. Hier ist ein einfacher Beispielcode, der cexprtk mit userinput_function verwendet:
Auf meinem Rechner (Linux, Dual Core, 2.5GHz) ist dies bei einer Demolänge von 20000 in 0,0202 Sekunden abgeschlossen.
Bei einer Demolänge von 2.000.000% endet co_de% in 1.23 Sekunden.
Tags und Links python eval abstract-syntax-tree sympy numexpr