[Из песочницы] Формулы и ленивые комбинаторы
Библиотека для работы с формулами
Нам в финтехе часто нужно проверять выполнение простых арифметических условий, например, будет ли курс обмена валют больше, чем ожидаемое значение, или нет. Эти условия очень часто меняются, и нам нужно было изобрести какой-нибудь велосипед, чтобы в режиме реального времени добавлять новые проверки и выполнять существующие. Представьте себе, что несколько тысяч клиентов ожидают получить уведомления когда курс обмена по некоторым валютным парам достигнет коэффициента два к одному. Это было бы очень просто, если бы мы только могли сделать условия статичными:
def notify?(rate) when rate > 2.0, do: true
def notify?(_), do: false
Мы позволяем клиентам добавлять такие проверки динамически. А значит, нам нужен более или менее надежный механизм для проверки условий, добавленных только что.
Да, Code.eval_string/3 как-то работает, но оно компилирует условие каждый чертов раз перед собственно проверкой. Очевидно, что это напрасная трата ресурсов без всякой причины. Которая усугубляется тем, что мы получаем и обрабатываем примерно 10000 курсов для разных валютных пар ежесекундно.
Так мы придумали прекомпилированные формулы. Крошечная библиотека formulae создает модуль для каждого заданного условия и компилирует формулу, введенную пользователем, в код, — единожды.
NB библиотеку следует использовать с осторожностью, потому что имена модулей хранятся в виде атомов и слепое безусловное их создание для всего, что клиент хочет проверить, может привести к атомной DoS-атаке на виртуальную машину эрланга при более-менее долгом времени исполнения. Мы используем максимально допустимый шаг значения в 0.01, который дает максимум 200 тысяч атомов при худшем сценарии развития событий.
Ленивые Комбинаторы
Но главная цель этой заметки — не рассказать о прекомпилированных формулах. Для некоторых пограничных случаев анализа курсов валют нам нужно было рассчитать перестановки довольно длинного списка. Внезапно, стандартная библиотека Elixir не предоставляет готовое решение. Ну, я решил скопировать сигнатуры комбинаторов из Ruby (Array#combination и родственничков). К сожалению, это оказалось не так просто для длинных списков. Комбинации глохли в районе тридцати элементов в списке, пермутации — и того раньше.
Ну, ожидаемо, что уж тут; поэтому я стал играться в ленивую реализацию с использованием Stream. Оказалось, и это не так просто, как я думал. Я придумал что-то вроде кода ниже
list = ~w[a b c d e]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)
Это работает, но только для известного заранее количества комбинаций. Ну, это уже легко преодолимо: на такой случай у нас есть макросы, да?
В коде выше просматриваются три различных шаблона. Успешная ветка, из которой мы выбрасываем список. Быстрый выброс пустого списка. И трансформация потока с индексом. Похоже, что мы могли бы попытаться создать AST для вышеуказанного.
Это тот редкий случай, когда использование Kernel.SpecialForms.quote/2, вероятно, все только усложнит, так что я пошел по пути наименьшего сопротивления: мы будем лепить старый добрый голый AST.
Я начал с того, что в консоли вызвал quote do: на этом коде, и до рези в глазах изучил результат. Да, есть закономерности. Ну, поехали.
Итак, начинать надо с создания общего каркаса.
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
Теперь нам нужно начать мыслить в категориях не кода, но AST, чтобы увидеть повторяющиеся шаблонные части. Это весело!
Начнем с вспомогательных макросов для упрощения кода:
def var(i), do: {:"i_#{i}", [], Elixir}
def idx(i), do: {:"idx_#{i}", [], Elixir}
Внутренний кусок AST, выдранный из общего представления:
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
Все внутренние куски вместе:
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
И, наконец, внешняя обертка вокруг всего этого.
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
Все перестановки выполняются практически одинаково, единственное изменение — это условие во внутренних вызовах. Это было несложно, да? Весь код можно посмотреть в репозитории.
Приложение
Хорошо, так как мы можем эту красоту использовать-то? Ну, как-то так:
l = for c <- ?a..?z, do: <> # letters list
with {stream, :ok} <- Formulae.Combinators.Stream.permutations(l, 12),
do: stream |> Stream.take_every(26) |> Enum.take(2)
#⇒ [["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"],
# ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "l", "w"]]
Мы теперь даже можем накормить Flow прямо из этого потока, чтобы распараллелить вычисления. Да, все равно это будет медленно и печально, но, к счастью, такая задача стоит перед нами не в реальном времени, а для аналитики, которую можно запустить ночью, и которая будет неторопливо проходить через все комбинации и куда-нибудь записывать получившиеся результаты.
Если есть вопросы по AST в Elixir — задавайте, я на нем собаку съел.
