Хабрахабр

[Из песочницы] Формулы и ленивые комбинаторы

Библиотека для работы с формулами

Нам в финтехе часто нужно проверять выполнение простых арифметических условий, например, будет ли курс обмена валют больше, чем ожидаемое значение, или нет. Эти условия очень часто меняются, и нам нужно было изобрести какой-нибудь велосипед, чтобы в режиме реального времени добавлять новые проверки и выполнять существующие. Представьте себе, что несколько тысяч клиентов ожидают получить уведомления когда курс обмена по некоторым валютным парам достигнет коэффициента два к одному. Это было бы очень просто, если бы мы только могли сделать условия статичными:

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 — задавайте, я на нем собаку съел.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть