[Из песочницы] Формулы и ленивые комбинаторы
Библиотека для работы с формулами
Нам в финтехе часто нужно проверять выполнение простых арифметических условий, например, будет ли курс обмена валют больше, чем ожидаемое значение, или нет. Эти условия очень часто меняются, и нам нужно было изобрести какой-нибудь велосипед, чтобы в режиме реального времени добавлять новые проверки и выполнять существующие. Представьте себе, что несколько тысяч клиентов ожидают получить уведомления когда курс обмена по некоторым валютным парам достигнет коэффициента два к одному. Это было бы очень просто, если бы мы только могли сделать условия статичными:
def notify?(rate) when rate > 2.0, do: true
def notify?(_), do: false
Мы позволяем клиентам добавлять такие проверки динамически. А значит, нам нужен более или менее надежный механизм для проверки условий, добавленных только что.
Да, Code.eval_string/3
как-то работает, но оно компилирует условие каждый чертов раз перед собственно проверкой. Очевидно, что это напрасная трата ресурсов без всякой причины. Которая усугубляется тем, что мы получаем и обрабатываем примерно 10000 курсов для разных валютных пар ежесекундно.
Крошечная библиотека formulae
создает модуль для каждого заданного условия и компилирует формулу, введенную пользователем, в код, — единожды. Так мы придумали прекомпилированные формулы.
Мы используем максимально допустимый шаг значения в 0. NB библиотеку следует использовать с осторожностью, потому что имена модулей хранятся в виде атомов и слепое безусловное их создание для всего, что клиент хочет проверить, может привести к атомной DoS-атаке на виртуальную машину эрланга при более-менее долгом времени исполнения. 01
, который дает максимум 200 тысяч атомов при худшем сценарии развития событий.
Ленивые Комбинаторы
Но главная цель этой заметки — не рассказать о прекомпилированных формулах. Для некоторых пограничных случаев анализа курсов валют нам нужно было рассчитать перестановки довольно длинного списка. Внезапно, стандартная библиотека Elixir не предоставляет готовое решение. Ну, я решил скопировать сигнатуры комбинаторов из Ruby (Array#combination
и родственничков). К сожалению, это оказалось не так просто для длинных списков. Комбинации глохли в районе тридцати элементов в списке, пермутации — и того раньше.
Оказалось, и это не так просто, как я думал. Ну, ожидаемо, что уж тут; поэтому я стал играться в ленивую реализацию с использованием Stream. Я придумал что-то вроде кода ниже
list = ~w[a b c d e]a combinations = Stream.transform(Stream.with_index(list), :ok, fn , :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 для вышеуказанного.
SpecialForms.quote/2, вероятно, все только усложнит, так что я пошел по пути наименьшего сопротивления: мы будем лепить старый добрый голый AST. Это тот редкий случай, когда использование Kernel.
Да, есть закономерности. Я начал с того, что в консоли вызвал 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: <<c>> # 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 — задавайте, я на нем собаку съел.