Bibliothèque de formules
En fintech, nous devons souvent vérifier que les conditions arithmétiques simples sont remplies, par exemple, si le taux de change sera supérieur ou non à la valeur attendue. Ces conditions changent très souvent, et nous devions inventer une sorte de vélo afin d'ajouter de nouveaux contrôles et de réaliser ceux qui existent en temps réel. Imaginez que plusieurs milliers de clients s'attendent à recevoir des notifications lorsque le taux de change de certaines paires de devises atteint un ratio de deux pour un. Ce serait très simple si nous ne pouvions que rendre les conditions statiques:
def notify?(rate) when rate > 2.0, do: true def notify?(_), do: false
Nous permettons aux clients d'ajouter de tels contrôles de manière dynamique. Nous avons donc besoin d'un mécanisme plus ou moins fiable pour vérifier les conditions qui viennent d'être ajoutées.
Oui,
Code.eval_string/3 fonctionne d'une manière ou d'une autre, mais il compile la condition à chaque fois avant de vérifier. De toute évidence, c'est un gaspillage de ressources sans raison. Ce qui est aggravé par le fait que nous recevons et traitons environ 10 000 cours pour différentes paires de devises chaque seconde.
Nous avons donc trouvé des formules précompilées. La petite bibliothèque de
formulae crée un module pour chaque condition donnée et compile la formule entrée par l'utilisateur en code - une fois.
La bibliothèque
NB doit être utilisée avec prudence, car les noms de modules sont stockés sous forme d'atomes et leur création aveugle inconditionnelle pour tout ce que le client veut vérifier peut conduire à une attaque atomique DoS sur la machine virtuelle Erlang avec un temps d'exécution plus ou moins long. Nous utilisons le pas maximum autorisé d'une valeur de
0.01 , ce qui donne un maximum de 200 000 atomes dans le pire des cas.
Combinateurs paresseux
Mais le but principal de cet article n'est pas de parler de formules précompilées. Pour certains cas limites d'analyse des taux de change, nous avons dû calculer les permutations d'une liste assez longue. Du coup, la bibliothèque standard Elixir ne propose pas de solution clé en main. Eh bien, j'ai décidé de copier les signatures combinatoires de Ruby (
Array#combination et cousins). Malheureusement, ce n'était pas si facile pour les longues listes. Les combinaisons ont calé dans la région de trente éléments de la liste, permutation - encore plus tôt.
Eh bien, il est prévu que déjà ici; j'ai donc commencé à jouer l'implémentation paresseuse en utilisant Stream. Cela s'est avéré, et ce n'est pas aussi facile que je le pensais. J'ai trouvé quelque chose comme le code ci-dessous
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)
Cela fonctionne, mais uniquement pour un nombre connu de combinaisons. Eh bien, cela est facilement surmontable: pour un tel cas, nous avons des macros, non?
Dans le code ci-dessus, trois modèles différents sont affichés. Une branche réussie dont nous supprimons la liste. Éjection rapide d'une liste vide. Et la transformation du flux avec l'indice. Il semble que nous pourrions essayer de créer un AST pour ce qui précède.
C'est le cas rare lorsque l'utilisation de
Kernel.SpecialForms.quote/2 ne fera probablement que compliquer les choses, j'ai donc pris le chemin de la moindre résistance: nous allons sculpter le bon vieux AST nu.
J'ai commencé par invoquer
quote do: dans la console sur ce code, et, au point, j'ai examiné le résultat. Oui, il y a des modèles. Eh bien, allons-y.
Vous devez donc commencer par créer un cadre commun.
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
Maintenant, nous devons commencer à penser en termes non pas de code, mais d'AST, pour voir des parties de modèle répétitives. C'est amusant!
Commençons par les macros d'assistance pour simplifier le code:
def var(i), do: {:"i_#{i}", [], Elixir} def idx(i), do: {:"idx_#{i}", [], Elixir}
Pièce intérieure AST arrachée d'une vue générale:
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
Toutes les pièces intérieures ensemble:
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
Et enfin, l'enveloppe extérieure autour de tout cela.
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
Toutes les permutations sont effectuées presque à l'identique, le seul changement est la condition dans les appels internes. C'était facile, non? Tout le code peut être consulté
dans le référentiel .
App
Bon, alors comment utiliser cette beauté? Eh bien, quelque chose comme ça:
l = for c <- ?a..?z, do: <<c>>
Nous pouvons maintenant même alimenter
Flow directement à partir de ce flux pour paralléliser les calculs. Oui, ce sera toujours lent et triste, mais, heureusement, cette tâche n'est pas en temps réel, mais pour des analyses qui peuvent être exécutées la nuit et qui passeront lentement par toutes les combinaisons et noteront les résultats quelque part.
Si vous avez des questions sur l'AST dans Elixir - demandez, j'ai mangé un chien dessus.