Formelbibliothek
In der Fintech-Branche müssen wir häufig überprüfen, ob einfache arithmetische Bedingungen erfüllt sind, beispielsweise ob der Wechselkurs über dem erwarteten Wert liegt oder nicht. Diese Bedingungen ändern sich sehr oft, und wir mussten eine Art Fahrrad erfinden, um neue Prüfungen hinzuzufügen und bestehende in Echtzeit durchzuführen. Stellen Sie sich vor, mehrere tausend Kunden erwarten Benachrichtigungen, wenn der Wechselkurs für einige Währungspaare ein Verhältnis von zwei zu eins erreicht. Es wäre sehr einfach, wenn wir nur die Bedingungen statisch machen könnten:
def notify?(rate) when rate > 2.0, do: true def notify?(_), do: false
Kunden können solche Prüfungen dynamisch hinzufügen. Wir brauchen also einen mehr oder weniger zuverlässigen Mechanismus, um die gerade hinzugefügten Bedingungen zu überprüfen.
Ja,
Code.eval_string/3 funktioniert irgendwie, aber es kompiliert die Bedingung jedes verdammte Mal, bevor es tatsächlich überprüft wird. Offensichtlich ist dies ohne Grund eine Verschwendung von Ressourcen. Hinzu kommt, dass wir pro Sekunde rund 10.000 Kurse für verschiedene Währungspaare erhalten und abwickeln.
Also haben wir uns vorkompilierte Formeln ausgedacht. Die winzige
formulae erstellt für jede gegebene Bedingung ein Modul und kompiliert die vom Benutzer eingegebene Formel einmal im Code.
Die NB- Bibliothek sollte mit Vorsicht verwendet werden, da die Modulnamen in Form von Atomen gespeichert werden und ihre blinde, bedingungslose Erstellung für alles, was der Client überprüfen möchte, zu einem atomaren DoS-Angriff auf die virtuelle Erlang-Maschine mit einer mehr oder weniger langen Ausführungszeit führen kann. Wir verwenden die maximal zulässige Schrittweite von
0.01 , was im schlimmsten Fall maximal 200.000 Atome ergibt.
Faule Kombinatoren
Der Hauptzweck dieses Artikels ist es jedoch nicht, über vorkompilierte Formeln zu sprechen. Für einige Grenzfälle der Wechselkursanalyse mussten wir die Permutationen einer ziemlich langen Liste berechnen. Plötzlich bietet die Elixir-Standardbibliothek keine schlüsselfertige Lösung. Nun, ich habe mich entschlossen, die kombinatorischen Signaturen von Ruby (
Array#combination und Cousins) zu kopieren. Bei langen Listen war das leider nicht so einfach. Die Kombinationen blieben im Bereich von dreißig Elementen in der Liste stehen, Permutation - noch früher.
Nun, es wird erwartet, dass schon hier; Also habe ich angefangen, Lazy Implementation mit Stream zu spielen. Es stellte sich heraus, und es ist nicht so einfach, wie ich dachte. Ich habe mir so etwas wie den folgenden Code ausgedacht
list = ~w[abcde]a combinations = Stream.transform(Stream.with_index(list), :ok, fn {i1, idx1}, :ok -> {Stream.transform(Stream.with_index(list), :ok, fn {_, idx2}, :ok when idx2 <= idx1 -> {[], :ok} {i2, idx2}, :ok -> {Stream.transform(Stream.with_index(list), :ok, fn {_, idx3}, :ok when idx3 <= idx2 -> {[], :ok} {i3, idx3}, :ok -> {Stream.transform(Stream.with_index(list), :ok, fn {_, idx4}, :ok when idx4 <= idx3 -> {[], :ok} {i4, _idx4}, :ok -> {[[i1, i2, i3, i4]], :ok} end), :ok} end), :ok} end), :ok} end)
Dies funktioniert jedoch nur für eine bekannte Anzahl von Kombinationen. Nun, das ist leicht zu überwinden: Für einen solchen Fall haben wir doch Makros, oder?
Im obigen Code werden drei verschiedene Muster angezeigt. Ein erfolgreicher Zweig, aus dem wir die Liste streichen. Schnelles Auswerfen einer leeren Liste. Und die Transformation des Flusses mit dem Index. Es sieht so aus, als könnten wir versuchen, einen AST für das oben Gesagte zu erstellen.
Dies ist der seltene Fall, wenn
Kernel.SpecialForms.quote/2 wird, was wahrscheinlich nur zu Komplikationen führt.
Kernel.SpecialForms.quote/2 bin ich den Weg des geringsten Widerstands
Kernel.SpecialForms.quote/2 : Wir werden den guten alten nackten AST formen.
Zunächst habe ich
quote do: in der Konsole für diesen Code aufgerufen und das Ergebnis auf den Punkt gebracht. Ja, es gibt Muster. Nun, lass uns gehen.
Sie müssen also zunächst ein gemeinsames Framework erstellen.
defmacrop mapper(from, to, fun), do: quote(do: Enum.map(Range.new(unquote(from), unquote(to)), unquote(fun))) @spec combinations(list :: list(), count :: non_neg_integer()) :: {Stream.t(), :ok} defmacro combinations(l, n) do Enum.reduce(n..1, {[mapper(1, n, &var/1)], :ok}, fn i, body -> stream_combination_transform_clause(i, l, body) end) end
Jetzt müssen wir anfangen, nicht in Code, sondern in AST zu denken, um zu sehen, wie sich Schablonenteile wiederholen. Das ist lustig!
Beginnen wir mit Hilfsmakros, um den Code zu vereinfachen:
def var(i), do: {:"i_#{i}", [], Elixir} def idx(i), do: {:"idx_#{i}", [], Elixir}
AST-Innenteil aus einer Gesamtansicht gerissen:
def sink_combination_clause(i) when i > 1 do {:->, [], [ [ {:when, [], [ {{:_, [], Elixir}, idx(i)}, :ok, {:<=, [context: Elixir, import: Kernel], [idx(i), idx(i - 1)]} ]} ], {[], :ok} ]} end
Alle inneren Teile zusammen:
def sink_combination_clauses(1, body) do [{:->, [], [[{var(1), idx(1)}, :ok], body]}] end def sink_combination_clauses(i, body) when i > 1 do Enum.reverse([ {:->, [], [[{var(i), idx(i)}, :ok], body]} | Enum.map(2..i, &sink_combination_clause/1) ]) end
Und schließlich die äußere Hülle um alles.
def stream_combination_transform_clause(i, l, body) do clauses = sink_combination_clauses(i, body) {{{:., [], [{:__aliases__, [alias: false], [:Stream]}, :transform]}, [], [ {{:., [], [{:__aliases__, [alias: false], [:Stream]}, :with_index]}, [], [l]}, :ok, {:fn, [], clauses} ]}, :ok} end
Alle Permutationen werden fast identisch durchgeführt, die einzige Änderung ist die Bedingung in internen Aufrufen. Es war einfach, richtig? Der gesamte Code kann
im Repository angezeigt werden.
App
Gut, wie können wir diese Schönheit nutzen? So etwas in der Art:
l = for c <- ?a..?z, do: <<c>>
Wir können jetzt sogar
Flow direkt aus diesem Stream einspeisen, um die Berechnungen zu parallelisieren. Ja, es wird immer noch langsam und traurig sein, aber glücklicherweise erfolgt diese Aufgabe nicht in Echtzeit, sondern für Analysen, die nachts ausgeführt werden können und die alle Kombinationen langsam durchlaufen und die Ergebnisse irgendwo aufschreiben.
Wenn Sie Fragen zu AST in Elixier haben - fragen Sie, ich habe einen Hund darauf gegessen.