Biblioteca de fórmulas
En fintech, a menudo necesitamos verificar que se cumplan las condiciones aritméticas simples, por ejemplo, si el tipo de cambio será mayor que el valor esperado o no. Estas condiciones cambian muy a menudo, y necesitábamos inventar algún tipo de bicicleta para agregar nuevos controles y realizar los existentes en tiempo real. Imagine que varios miles de clientes esperan recibir notificaciones cuando el tipo de cambio de algunos pares de divisas alcance una proporción de dos a uno. Sería muy simple si solo pudiéramos hacer que las condiciones sean estáticas:
def notify?(rate) when rate > 2.0, do: true def notify?(_), do: false
Permitimos a los clientes agregar dichos controles dinámicamente. Por lo tanto, necesitamos un mecanismo más o menos confiable para verificar las condiciones que se acaban de agregar.
Sí,
Code.eval_string/3 alguna manera funciona, pero compila la condición cada maldita vez antes de comprobarlo. Obviamente, esto es un desperdicio de recursos sin ninguna razón. Lo cual se agrava por el hecho de que recibimos y procesamos alrededor de 10,000 cursos para diferentes pares de divisas cada segundo.
Entonces se nos ocurrieron fórmulas precompiladas. La pequeña biblioteca de
formulae crea un módulo para cada condición dada y compila la fórmula ingresada por el usuario en el código, una vez.
La biblioteca
NB debe usarse con precaución, porque los nombres de los módulos se almacenan en forma de átomos y su creación incondicional ciega para todo lo que el cliente quiere verificar puede conducir a un ataque DoS atómico en la máquina virtual Erlang con un tiempo de ejecución más o menos largo. Usamos el paso máximo permitido de un valor de
0.01 , que da un máximo de 200 mil átomos en el peor de los casos.
Combinadores perezosos
Pero el objetivo principal de este artículo no es hablar sobre fórmulas precompiladas. Para algunos casos límite de análisis de tipo de cambio, necesitábamos calcular las permutaciones de una lista bastante larga. De repente, la biblioteca estándar de Elixir no proporciona una solución llave en mano. Bueno, decidí copiar las firmas combinatorias de Ruby (
Array#combination y primos). Desafortunadamente, esto no fue tan fácil para largas listas. Las combinaciones se estancaron en la región de treinta elementos en la lista, permutación, incluso antes.
Bueno, se espera que ya esté aquí; así que comencé a jugar una implementación perezosa usando Stream. Resultó, y no es tan fácil como pensaba. Se me ocurrió algo como el código a continuación
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)
Esto funciona, pero solo para un número conocido de combinaciones. Bueno, esto es fácilmente superable: para tal caso tenemos macros, ¿verdad?
En el código anterior, se ven tres patrones diferentes. Una rama exitosa de la que soltamos la lista. Expulsión rápida de una lista vacía. Y la transformación del flujo con el índice. Parece que podríamos intentar crear un AST para lo anterior.
Este es el caso raro cuando se usa
Kernel.SpecialForms.quote/2 probablemente solo complicará las cosas, así que tomé el camino de menor resistencia: esculpiremos el viejo AST desnudo.
Comencé invocando
quote do: en la consola en este código y, hasta el punto, examiné el resultado. Sí, hay patrones. Pues vamos.
Por lo tanto, debe comenzar creando un marco común.
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
Ahora tenemos que empezar a pensar en términos de no código, sino AST, para ver las partes repetidas de la plantilla. ¡Esto es divertido!
Comencemos con macros de ayuda para simplificar el código:
def var(i), do: {:"i_#{i}", [], Elixir} def idx(i), do: {:"idx_#{i}", [], Elixir}
Pieza interior AST arrancada de una vista general:
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
Todas las piezas internas juntas:
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
Y finalmente, el envoltorio exterior a su alrededor.
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
Todas las permutaciones se realizan de forma casi idéntica, el único cambio es la condición en las llamadas internas. Fue fácil, ¿verdad? Todo el código se puede ver
en el repositorio .
App
Bien, entonces, ¿cómo podemos usar esta belleza? Bueno, algo como esto:
l = for c <- ?a..?z, do: <<c>>
Ahora podemos incluso alimentar a
Flow directamente desde esta secuencia para paralelizar los cálculos. Sí, seguirá siendo lento y triste, pero, afortunadamente, esta tarea no es en tiempo real, sino para análisis que se pueden ejecutar por la noche y que pasarán lentamente por todas las combinaciones y anotarán los resultados en alguna parte.
Si tiene preguntas sobre AST en Elixir, pregunte, me comí un perro.