Учимся думать и писать на Erlang (на примере двух комбинаторных задач)

— … Тут я даю ему по морд… Нет, бить нельзя!
— В том-то и дело, что бить нельзя, — лицемерно вздохнул Паниковский. — Бендер не позволяет.
И.Ильф, Е.Петров. Золотой теленок.

Мозголомная Брага жила в прозрачном сосуде и была такая
крепкая, что даже ужас. Она не то что из живота — прямо изо рта
бросилась в голову и стала кидаться там из стороны в сторону,
ломая умственные подпорки и укрепы.
М.Успенский. Там, где нас нет.

Пожалуй каждый, кто впервые приступает к изучению Erlang, ощущает себя в положении Шуры Балаганова, которому запрещено было применение единственного доступного и понятного метода: «бить нельзя...». В Erlang отсутствуют такие привычные для большинства современных языков понятия, как повторное присвоение переменной и, соответственно, накопление результата в одной переменной. (Справедливости ради следует отметить, что поведение типа «глобальная многократно меняющаяся переменная» в Erlang все же можно реализовать. Для этого в каждом процессе имеется словарь хешей, хранящий определяемые программистом пары ключ — значение. Имеются встроенные функции put(Key, Value), get(Key) и еще несколько вспомогательных функций. Но использование такого словаря в приложениях считается плохим стилем и рекомендуется только в исключительных случаях (http://www.erlang.org/doc/man/erlang.html\#put-2)). Как следствие, итерации в цикле невозможно реализовать с помощью привычного наращивания значений итерационной переменной. Накопление результата осуществляется только через рекурсию, а организация циклов — через хвостовую рекурсию. (Конечно, и итерации, и накопление результата в цикле можно реализовать через библиотечные функции для списков lists:foreach(Function, List), lists:foldl(Function, StartValue, List), lists:foldr(Function, StartValue, List) (http://www.erlang.org/doc/man/lists.html) и их аналоги для наборов (http://www.erlang.org/doc/man/sets.html, http://www.erlang.org/doc/man/ordsets.html, http://www.erlang.org/doc/man/gb_sets.html) и массивов (http://www.erlang.org/doc/man/array.html). Но наша цель — научиться писать циклы, а не использовать готовые решения, поэтому здесь мы воздержимся от употребления подобных библиотек).

Таким образом, в Erlang приходится ломать привычные шаблоны мышления и заменять их новыми паттернами, характерными только для этого языка программирования. Конечно, идеальное средство — мозголомная брага, способная ломать все «умственные подпорки и укрепы». Но для нас это, пожалуй, слишком радикальное средство, и мы пойдем другим путем.

В житии святого Антония Великого есть рассказ об одном из его учеников. Ученик стоял в храме и слушал, как святой Антоний читал Псалтырь. Как только прозвучал первый стих первого псалма:
Блажен муж, который не ходит на совет нечестивых...
ученик вышел из храма. С тех пор его никто не видел почти 30 лет, а когда он вновь появился в храме, Антоний Великий спросил, почему он оставил их так надолго и куда исчез. Ученик ответил: «отче, я услышал слова псалма, и удалился в пустыню, чтобы постараться выполнить то, о чем говорится в этих словах, т.е. не ходить на совет нечестивых мыслей». Другими словами, он усвоил практический урок этих слов, и теперь пришел чтобы читать дальше. К сожалению, у нас нет такого резерва времени, да и цели наши не столь возвышенны. Но основной концепт можно перенять.
Мы рассмотрим две стандартные комбинаторные задачи:
  1. поиск всех возможных перестановок (permutations) из данного множества по N элементов
  2. поиск всех возможных сочетаний (combinations) из данного множества по N элементов

и разберем различные подходы и способы их решения средствами языка программирования Erlang, чтобы на конкретных примерах понять и освоить некоторые особенности программирования на этом языке.

Все примеры собраны в модуле combinat.erl и доступны по адресу: https://github.com/raven29/combinat_erl.git

Две цели — две рекурсии


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

Другими словами, процедура заключает в себе два этапа: циклический перебор на данном уровне рекурсии и переход на следующий уровень. Соответственно, эти две цели требуют двойного рекурсивного вызова. (Алгоритм основан на наивном переборе и, соответственно, требует оптимизации. Однако он вполне подходит для наших целей, потому что, во-первых, в силу простоты и наглядности позволяет легко иллюстрировать используемые методы и приемы, во-вторых, применяется к обеим рассматриваемым задачам с минимальными различиями, что дает возможность проводить соответствующие сравнения и параллели).

Базовая реализация


Базовый функционал реализован в функциях combinat:permuts_out(List, Number) и combinat:combs_out(List, Number), которые выводят на печать соответственно все перестановки и все сочетания длиной Number из элементов списка List. Ниже приводится функция permuts_out(List, Number), выводящая на печать перестановки. Эта функция дважды вызывается рекурсивно: в 6 строке — для циклического перебора, в 7 строке — для перехода на следующий уровень рекурсии. Именно в этом последнем вызове происходит наращивание результата в переменной [RemainH|Result], а также исключение элементов, содержащихся в этом результате, из общего списка, передаваемого на следующий уровень рекурсии. В четвертом аргументе List хранится исходный список элементов, который требуется для корректного вычисления остатка только в случае перестановок.

permuts_out(List, Number) -> permuts_out(List, [], Number, List).
permuts_out(_Remain, Result, Number, _List) when length(Result) == Number ->
    io:format("~w~n", [Result]);
permuts_out([], _Result, _Number, _List) -> ok;
permuts_out([RemainH|RemainT], Result, Number, List) ->
    permuts_out(RemainT, Result, Number, List),
    permuts_out(List -- [RemainH|Result], [RemainH|Result], Number, List).


Аналогичная функция для сочетаний отличается от предыдущей функции лишь более простым правилом вычисления передаваемого остатка и отсутствием четвертого аргумента List.

combs_out(List, Number) -> combs_out(List, [], Number).
combs_out(_Remain, Result, Number) when length(Result) == Number ->
    io:format("~w~n", [Result]);
combs_out([], _Result, _Number) -> ok;
combs_out([RemainH|RemainT], Result, Number) ->
    combs_out(RemainT, Result, Number),
    combs_out(RemainT, [RemainH|Result], Number).


Две рекурсии — две функции


Для большей наглядности два рекурсивных вызова можно представить двумя разными функциями. Окончания в названиях функций соответствуют их назначениям: *_iteration — для итераций по списку остатка на данном уровне рекурсии, *_recursion — для перехода на следующий уровень рекурсии.

permuts_out_2(List, Number) -> permuts_out_iteration(List, [], Number, List).
permuts_out_iteration([], _Result, _Number, _List) -> ok;
permuts_out_iteration([RemainH|RemainT], Result, Number, List) ->
    permuts_out_iteration(RemainT, Result, Number, List),
    permuts_out_recursion(List -- [RemainH|Result], [RemainH|Result], Number, List).
permuts_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number ->
    io:format("~w~n", [Result]);
permuts_out_recursion(Remain, Result, Number, List) ->
    permuts_out_iteration(Remain, Result, Number, List).

combs_out_2(List, Number) -> combs_out_iteration(List, [], Number, List).
combs_out_iteration([], _Result, _Number, _List) -> ok;
combs_out_iteration([RemainH|RemainT], Result, Number, List) ->
    combs_out_iteration(RemainT, Result, Number, List),
    combs_out_recursion(RemainT, [RemainH|Result], Number, List).
combs_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number ->
    io:format("~w~n", [Result]);
combs_out_recursion(Remain, Result, Number, List) ->
    combs_out_iteration(Remain, Result, Number, List).


Пожалуй, этот вариант можно считать антипаттерном, ввиду излишней громоздкости.

Предъявите результат!



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

  1. возврат значений в восходящей рекурсии
  2. функция обратного вызова (callback)
  3. поток-исполнитель и поток-накопитель

Рассмотрим каждый вариант подробно.

Медведь туда — медведь обратно

До сих пор мы делали что-то полезное (если вывод результата на экран компьютера можно считать полезным делом) в теле функции, спускаясь вглубь по нисходящей рекурсии. При обратном движении результат, возвращаемый функцией, никак не использовался. Другими словами, восходящее движение по рекурсии шло «порожняком». При таком подходе невозможно собрать воедино все выводимые значения, т.к. они никак не связаны между собой. Более продуктивным является использование результата, возвращаемого функцией при выходе из рекурсии. В этом случае первый вызов рекурсивной функции может вернуть весь совокупный результат. Модификация базовых функций приведена ниже и включает три момента:

  1. возвращение результата [Result] вместо вывода в стандартный поток (строка 3, 11)
  2. на «дне» рекурсии возвращается начальное значение — пустой список [ ] вместо атома «ok» (строка 4, 12)
  3. накопление результата с помощью суммирования списков "++" вместо последовательного вызова (строка 6, 14)

Функции permuts_res(List, Number) и combs_res(List, Number) возвращают список списков, содержащий соответственно все перестановки и сочетания длиной Number.

permuts_res(List, Number) -> permuts_res(List, [], Number, List).
permuts_res(_Remain, Result, Number, _List) when length(Result) == Number ->
    [Result];
permuts_res([], _Result, _Number, _List) -> [];
permuts_res([RemainH|RemainT], Result, Number, List) ->
    permuts_res(RemainT, Result, Number, List) ++
    permuts_res(List -- [RemainH|Result], [RemainH|Result], Number, List).

combs_res(List, Number) -> combs_res(List, [], Number).
combs_res(_Remain, Result, Number) when length(Result) == Number ->
    [Result];
combs_res([], _Result, _Number) -> [];
combs_res([RemainH|RemainT], Result, Number) ->
    combs_res(RemainT, Result, Number) ++
    combs_res(RemainT, [RemainH|Result], Number).


И делай с ним что хошь!


Иногда бывает удобно не накапливать результат в одной переменной-коллекции, а делать что-нибудь полезное с каждым элементом сразу после его создания. Такой подход позволяет увеличить производительность и значительно уменьшить потребление оперативной памяти. Реализовать можно с помощью функции обратного вызова (callback), которая передается в качестве дополнительного аргумента. Соответствующие варианты приведены ниже.

permuts_clb(List, Number, Callback) -> permuts_clb(List, [], Number, List, Callback).
permuts_clb(_Remain, Result, Number, _List, Callback) when length(Result) == Number ->
    Callback(Result);
permuts_clb([], _Result, _Number, _List, _Callback) -> ok;
permuts_clb([RemainH|RemainT], Result, Number, List, Callback) ->
    permuts_clb(RemainT, Result, Number, List, Callback),
    permuts_clb(List -- [RemainH|Result], [RemainH|Result], Number, List, Callback).

combs_clb(List, Number, Callback) -> combs_clb(List, [], Number, Callback).
combs_clb(_Remain, Result, Number, Callback) when length(Result) == Number ->
    Callback(Result);
combs_clb([], _Result, _Number, _Callback) -> ok;
combs_clb([RemainH|RemainT], Result, Number, Callback) ->
    combs_clb(RemainT, Result, Number, Callback),
    combs_clb(RemainT, [RemainH|Result], Number, Callback).


В переменной Callback может быть передано имя любой функции от одного аргумента (с арностью единица — согласно терминологии Erlang). Так, например, можно вызвать вывод на печать всех перестановок из элементов [1,2,3] по 2:
combinat:permuts_clb([1,2,3], 2, fun(X)->io:format("~w~n",[X]) end).

Более содержательное применение функции обратного вызова рассматривается в следующем разделе.

Big Brother is watching you


Другой способ реализовать накопление результата ветвящейся рекурсии в Erlang — использовать два потока. Один поток — исполнитель, в нем запускается наша программа. Другой поток — наблюдатель, в него рекурсивная функция передает полученные результаты. Когда поток-исполнитель завершает свою работу, поток-наблюдатель выводит суммарный результат. Важно: в качестве потока-исполнителя нельзя использовать основной поток (supervisor), в котором запущена оболочка erl, т.к. этот поток не уничтожается после выполнения программы. Он продолжает существовать до выгрузки приложения erl.

Ниже приведена соответствующая реализация. В строке 3 устанавливается «выход по трапу», что обеспечивает передачу сообщения от связанного процесса даже в случае его нормального завершения. По умолчанию, флаг trap_exit установлен в false, что означает получение сообщения от связанного процесса только в случае аварийного завершения. В строке 5 запускается (и одновременно связывается) поток-исполнитель. В этом потоке запускается функция permuts_clb (или combs_clb), которой передаются аргументы List, Number, а также функция обратного вызова Callback, которая передает каждый единичный результат в процесс-наблюдатель:
fun(R)->Supervisor!R end

В строке 6 запускается функция loop([]) с пустым начальным значением суммарного результата. Эта функция «слушает» сообщения от потока-исполнителя. При получении очередного результата происходит рекурсивный вызов loop(Total ++ [Result]) (строка 14) с аргументом, дополненным вновь пришедшим результатом из потока-исполнителя. По завершении работы потока-исполнителя происходит «выход по трапу»: в loop() передается кортеж специального вида (строка 10), по которому в результате патерн-матчинга выводится общий результат (строка 11) и разрывается связь с потоком-исполнителем (строка 12). Supervisor — pid потока-наблюдателя, Worker — pid потока-исполнителя.

%% Function = permuts_clb | combs_clb
proc(Function, List, Number) ->
    process_flag(trap_exit, true),
    Supervisor = self(),
    spawn_link(combinat, Function, [List, Number, fun(R)->Supervisor!R end]),
    loop([]).

loop(Total) ->
    receive
    {'EXIT', Worker, normal} ->
        io:format("~w~n", [Total]),
        unlink(Worker);
    Result ->
        loop(Total ++ [Result])
    end.


Функция вызывается с permuts_clb или combs_clb в качестве первого аргумента, в зависимости от решаемой задачи. Например, вывод на печать всех перестановок из элементов [1,2,3] по 2 осуществляется через вызов:
combinat:proc(permuts_clb, [1,2,3], 2).

Тут возможны ошибки, характерные для новичка. Во-первых, нельзя запустить loop() перед spawn_link(). Казалось бы, так будет более надежно, так как функция-слушатель, запущенная до запуска потока-исполнителя, наверняка не пропустит ни одного сообщения от этого потока. Но в результате процесс «зависнет» на loop(), а вызов следующей строки никогда не произойдет. Во-вторых, использование переменной Supervisor для передачи сообщения в поток-наблюдатель обязательно: конструкция
self()!R

не работает, так как функция self() выполнится при вызове в потоке-исполнителе и, соответственно, примет pid потока-исполнителя. Спасибо w495 и EvilBlueBeaver за конструктивную критику по этим замечаниям (и просто за то что помогли разобраться).

И еще одно небольшое замечание: при экспериментах с функцией proc() могут случаться разные странности, например функция может начать выдавать результат с «запаздыванием», т.е. при каждом вызове выдавать результат предыдущего вызова. Это может происходить от того, что мы запускаем в качестве потока-наблюдателя главный поток. Поэтому после какого-либо сбоя следующий вызов loop() в первую очередь обработает все сообщения от прошлого вызова, если таковые оставались. В этом смысле более надежной будет реализация потока-слушателя также в отдельном потоке, порождаемом функцией spawn() или spawn_link().

Понять — значит включить



В некоторых языках программирования имеется синтаксическая конструкция, называемая "list comprehension". Она позволяет в компактной и изящной форме задать итерационный обход списка, в результате которого генерируется новый список, каждый элемент которого получен из исходного списка применением некоторой функции к каждому элементу исходного списка. Конструкция основана на системе обозначений математической теории множеств. Вот так, например, выглядит в конструкции list comprehension вывод квадратов всех целых чисел от 1 до 9:
[X*X || X <- [1,2,3,4,5,6,7,8,9]].

В list comprehension возможна также передача нескольких списков и наложение условий. В качестве примера рассмотрим вывод таблицы умножения от 1 до 9:
[io:format("~w * ~w = ~w~n", [I, J, I*J]) || 
    I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9]].

а также таблицы умножения, в которой исключены повторные результаты с перестановкой сомножителей:
[io:format("~w * ~w = ~w~n", [I, J, I*J]) || 
    I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9], I < J].


В русскоязычной литературе «list comprehension» переводится как «включение списков», «генерация списков». Основное значение перевода «comprehension» — «постичь», «понять». Так что, в английском языке понять — значит включить.

Следует отметить, что конструкция comprehension существует не только для списков, но и для коллекций других типов. В Erlang имеется list comprehension и binary comprehension.

Самая изящная в своем роде


В конструкции list comprehension можно задать итерационный обход по списку, в результате базовая функция приобретет вид:

permuts_comp(List, Number) -> permuts_comp(List, [], Number).
permuts_comp(_Remain, Result, Number) when length(Result) == Number ->
    io:format("~w~n", [Result]);
permuts_comp(Remain, Result, Number) ->
    [permuts_comp(Remain -- [R], [R] ++ Result, Number) || R <- Remain].

Функция permuts_comp вызывает себя рекурсивно из list comprehension.
Это, пожалуй, самая изящная функция перестановок из всех возможных.

Если нельзя, но очень хочется...


Обобщение предыдущего результата на функцию сочетаний, к сожалению, не столь очевидно. Дело в том, что в list comprehension в данном случае нужно передавать не весь список, а лишь остаток, определяемый номером из предыдущего вызова. Если бы вместо списков был массив — можно было бы без труда вычислить нужный индекс. Но массивов нет в базовых типах Erlang. Нужно либо использовать библиотеку array, либо организовать массив «вручную».
Это оказывается довольно просто, и соответствующая реализация представлена ниже. Из исходного списка List строим список кортежей ListIndexed, каждый элемент которого содержит элементы исходного списка и целочисленный индекс (строка 2). Для такого преобразования подойдет функция lists:zip(List1, List2) из стандартного модуля lists. При выводе результата используем функцию lists:unzip(ListIndexed), возвращающую индексированному списку исходный вид без индексов (строка 5). И самое главное — в list comprehension теперь можно легко указать требуемое ограничение на индексы, включаемые в итерации (строка 11).

combs_comp(List, Number) ->
    ListIndexed = lists:zip(List, lists:seq(1, length(List))),
    combs_comp(ListIndexed, [], Number).
combs_comp(_Remain, Result, Number) when length(Result) == Number ->
    {ResultValue, _I} = lists:unzip(Result),
    io:format("~w~n", [ResultValue]);
combs_comp(Remain, [], Number) ->
    [combs_comp(Remain -- [R], [R], Number) || R <- Remain];
combs_comp(Remain, [{HValue,HIndex}|T], Number) ->
    [combs_comp(Remain -- [{R,I}], [{R,I}] ++ [{HValue,HIndex}|T], Number) ||
    {R,I} <- Remain, I > HIndex].

Выглядит несколько неуклюже, и это — единственная программа среди наших примеров, в которой пришлось прибегнуть к библиотечным функциям lists:zip(List1, List2), lists:unzip(ListTuple), lists:seq(StartValue, Length). Эту попытку также можно считать образчиком антипаттерна, т.к. для поставленной задачи было бы более последовательно воспользоваться модулем array, но это уже будет другая история…
Поделиться публикацией

Комментарии 37

    +5
    Да… это да.
      +9
      Не очень хорошие примеры, если честно, слишком сложные, если стояла цель подтолкнуть к изучению Erlang.
        0
        Цель стояла не стимулировать изучение языка, а поискать подходы в нетривиальных случаях.
        +3
        Во-первых, нельзя запустить loop() перед spawn_link(). Казалось бы, так будет более надежно, т.к. функция-слушатель, запущенная до запуска потока-исполнителя, наверняка не пропустит ни одного сообщения от этого потока.
        O_o
        Как вы себе представляете запуск loop() перед spawn_link()???

        Кстати, использовать ++ на больших списках не стоит, т.к. левый операнд целиком копируется за O(n)
          0
          Про ++ — уверен? Я не очень.
          + Какая альтернатива?
          --> Можно, конечно, вложенные списки, но без опыта функ про осознать не просто.
            +2
            Про ++ вот тут подробно www.erlang.org/doc/efficiency_guide/myths.html#id58137
            Для аккумуляторов стараются использовать либо [NewEl | Accumulator] и lists:reverse в конце, либо [List1, List2] и lists:flatten в конце
              0
              gist.github.com/2924882

              lists:reverse — раньше брезговал, но

              > erlang:is_builtin(lists, reverse, 2).
              true
              


              lists:flatten — убийство.
              [List1, List2], в зависимоти от целей erlang:list_to_binary
                +1
                Интересный бенчмарк, спасибо.
                Но смущает что списки очень маленькие и влияние сложности алгоритмов небольшое. Попробуйте запустить такие же тесты на списках подлиннее чем 8 элементов, мне кажется результаты могу измениться.
                  0
                  Пробовал. Картина не менялась. Но ждать было лениво.
                  Если получится что-то иное дай знать.
                  Но опять же, все может зависеть от версии.
                  Правда, на память особого внимания не обращал.

                  влияние сложности алгоритмов небольшое


                  Так это просто тест конкатенации.
                  И меня более интересовало представление строк.
                  О каких алгоритмах речь?
                    0
                    алгоритмах?
                    Имею в виду, что, например такой map
                    map([], Acc, _) ->
                        Acc;
                    map([Element | Elements], Acc, F) ->
                        map(Elements, Acc ++ [F(Element)], F).
                    
                    ( O(n^2) если не ошибаюсь)
                    На списке из 10 элементов может показывать сравнимую производительность с reverse реализацией, но на 10 000 элементов разница будет огромная.
                    Лично не проверял, но что-то подсказывает…
                      0
                      O(n^2) по времени?
                      Ну как минимум операций больше.

                      Сложность весьма очевидна в C, и то не всегда (компиляторы умнеют быстро).
                      Тут мы имеем компилятор, который потенциально может разгуливать подобные ситуации,
                      и оптимизировать. Для конкретного случая надо проверять. Константа может перекрыть сложность.

                      Если позволяет логика приложения я бы сделал так:

                      map([], Acc, _) ->
                          Acc;
                      map([Element | Elements], Acc, F) ->
                          map(Elements, [F(Element)|Acc], F).
                      

                      А развернул бы в другом месте со сходной семантикой.
                      Иногда это влечет трудно находимые ошибки.

                      То что lists:flatten — убийство, и использовать надо, только там где он действительно нужен, проверено многократно, на практике. Собственно из-за него я и сделал сравнение.
                        0
                        T: «concat 10000» — 34.600007 s
                        T: «concat2 10000» — 1.208402 s

                        concat() ->
                           lists:foldl(fun(I, A) -> A ++ [I] end, [], lists:seq(1,1000)).
                        
                        concat2() ->
                           R = lists:foldl(fun(I, A) -> [I|A] end, [], lists:seq(1,1000)),
                           lists:reverse(R).
                        


            0
            Отметим два неочевидных обстоятельства. Во-первых, нельзя запустить loop() перед spawn_link(). Казалось бы, так будет более надежно, т.к. функция-слушатель, запущенная до запуска потока-исполнителя, наверняка не пропустит ни одного сообщения от этого потока. Но опыт показывает, что в этом случае функция-слушатель вообще не получает сообщения от потока-исполнителя. По-видимому, это связано с тем, что статус отношения потоков не обновляется.


            Откуда это все?
              0
              Откуда что? Предположение, или результат?
              Преположение — мое, я как истинный нуб в Эрланге предположил и попробовал.
              В предположении ничего запрещенного не вижу, результат — просто факт, так не получается
                +1
                я как истинный нуб в Эрланге предположил и попробовал.


                Так нельзя. Лучше сначала разобраться в вопросе, и потом уже строить предположения.
                Есть много чего, о чем мне хочется тут рассказать,
                но пока я не буду уверен в правильности и полезности,
                делать это бессмысленно. Просто потрачу время, и свое и чужое.

                Если это Ваши предположения, то не плохо бы это как-то пометить.
                Выглядит как категоричное утверждение.
                А неверное предположение, выданное за истину, вызывает негатив.
              +5
              Кстати, да, примеры довольно сложные для начинающих.

              К слову, чтоб не пугать людей, вот так выглядит функция для получения всех перестановок элементов списка.

              perms([]) -> [[]];
              perms(L)  -> [[H|T] || H <- L, T <- perms(L--[H])].
              


              Просто и элегантно. H — голова, T — хвост, L — список. Увидев функцию первый раз, можно даже разобраться что она делает, не зная языка.

              По поводу производительности. Задача: есть множество из 10 элементов. Получить список со всеми возможными перестановками.

              Erlang.
              Время выполнения — 3980 мс.
              Потребляемая память — 713 Мб (это примерно. Во время выполнения занимало больше, очевидно, из-за рекурсии).

              С++ list
              Время выполнения — 3000 мс.
              Потребляемая память — 1053 Мб.

              С++ vector
              Время выполнения — 700 мс.
              Потребляемая память — 228 Мб.

              P.S.

              Факториал
              factorial(0) -> 1;
              factorial(N) ->N * factorial(N-1).
              


              Quick Sort
              sort([Pivot|T]) ->
                  sort([ X || X <- T, X < Pivot]) ++
                  [Pivot] ++
                  sort([ X || X <- T, X >= Pivot]);
              sort([]) -> [].
              

                +1
                Факториал лучше хвостовкой
                factorial(N) -> factorial(N, 1).
                factorial(0, Acc) -> Acc;
                factorial(N, Acc) -> factorial(N-1, Acc*N).
                
                  +1
                  Этот быстрее, но первый по определению.
                  Если заюзать мемоизацию, то лучше писать, по определению, имхо.
                    0
                    Каким образом «факториал по определению» раскрывает особенности Erlang как языка программирования?
                      +2
                      Тем, что не надо думать о деталях.
                      Хотя бы на первых порах.
                      Декларативность, что ли.
                      Ну во общем это не к Erlang, а к функциональным языкам.
                    0
                    А правильно ли проводить бенчмарк с помощью timer:tc?
                    У меня нехвостовой вариант факториала от 20000 дает ~ 250 милисекунд, а хвостовой ~ 285.
                  0
                  >> perms([]) -> [[]];
                  >> perms(L) -> [[H|T] || H < — L, T < — perms(L--[H])].

                  Спасибо, конечно, но это — для перстановок из N по N.
                  Из M по N (M<=N) чуть сложнее будет…
                • НЛО прилетело и опубликовало эту надпись здесь
                    +1
                    Что и говорить, list comprehensions — чрезвычайно полезная и мощная вещь!

                    К слову, для данной конкретной задачи аналогичный код на C++ тоже получается достаточно компактным (C++11, чтобы можно было эффективно возвращать по значению)
                    std::vector<std::vector<int>> all_permutations( std::vector<int> v )
                    {
                      std::vector<std::vector<int>> ret;
                      do {
                        ret.push_back(v);
                      } while( std::next_permutation( begin(v), end(v)) );
                      return ret;
                    }
                    

                    Можно ускорить процентов на 30-40, если позвать ret.reserve(1*2*...*10), но немного потерять в читабельности. Но лучше всего, конечно просто итерировать, что даёт выигрыш в 10-15 раз.
                    {
                      std::vector<int> v{0,1,2,3,4,5,6,7,8,9};
                      do {
                        // do something useful
                      } while( std::next_permutation( begin(v), end(v)) );
                      return ret;
                    }
                    

                      +1
                      Да, я использовал именно next_permutation.

                      Код был какой-то такой pastebin.com/MhVwqaHT
                    +4
                    Чувак тебе нельзя пускать к Эрлангу вообще. Помедитируй еще несколько лет. Играть можеш но код лучше не пиши вообще. Иначе хуже будет. Это угроза!
                      0
                      Очень конструктивно, thanks.
                      Уже боюсь…
                        +2
                        Статьи точно ещё рано писать :) Читайте книжки, пишите код (ни в коем случае не продакшн), просите попинать.
                      +3
                      «Таким образом, в Erlang приходится ломать привычные шаблоны мышления и заменять их новыми паттернами, характерными только для этого языка программирования.»

                      Это не слишком близко к истине — Erlang действительно обладает уникальным сочетанием фичей, однако по-отдельности концепции проскакивают много где — от дизайна ОС до языков программирования.
                        +7
                        1. Выглядит абсолютно нечитаемо.
                        2. Видно, что с общением процессов толком не разобрались.
                        3. В случае some_fun(...) -> some_fun(...) ++ some_fun(...). о хвостовой рекурсии можно забыть, вкупе с "++" получаем дикий расход памяти и проца на больших массивах данных. Спорить по поводу как быстрее сложить 2 списка не стану, но складывать списки на каждом шаге рекурсии явно быстро не будет
                        4. when length(Result) == Number лучше не использовать, почему — читать в доке.
                        5. Remain — [R] я не буду говорить, насколько это медленно на больших объемах
                        6. [R] ++ Result это вообще неприятно видеть, надо [R | Result]
                        7. some_fun(..) -> [some_fun(..) || Some < — Whatever]. — это кстати тоже не хвостовая рекурсия


                        Если вы нам рассказываете о своем опыте изучения erlang, то это похвально и на вашем месте я бы прислушался к комментариям. Если пытаете учить или подсадить кого-то на erlang, то лучше не стоит.
                          +3
                          Кстати loop перед spawn_link запускать не имеет смысла. loop будет крутиться в рекурсии(в вашем случае блокироваться, потому что сообщений нет), а spawn_link так и не вызовется. И никакие «взаимоотношения потоков» тут ни при чем.

                          Писать self()! R в вашем случае нельзя, потому что эта функция будет вызвана внутри нового процесса и self() для нее будет логично другим. Именно поэтому вы и замыкаете Supervisor.
                            0
                            Спасибо!
                            С loop() — наступил на грабли, все действительно просто.
                            self()! R — не понимал, что тут действует замыкание.
                            Пошел исправлять.
                            Предыдущий Ваш комментарий тоже очень полезный, спасибо за замечания.
                            Учить или агитировать никого не пытаюсь, просто хотелось поделиться впечатлениями (об опыте пока рано говорить) и послушать полезные советы.
                            +3
                            Спасибо за эту маленькую ссылку в середине статьи. Открыл для себя отличный источник знаний.
                              +2
                              Это кстати пожалуй самый лучший труд по эрлангу в интернете.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое