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

[xReaper]

Да… это да.

[Cancel]

Не очень хорошие примеры, если честно, слишком сложные, если стояла цель подтолкнуть к изучению Erlang.

[kvl]

Цель стояла не стимулировать изучение языка, а поискать подходы в нетривиальных случаях.

[seriyPS]

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

O_o
Как вы себе представляете запуск loop() перед spawn_link()???

Кстати, использовать ++ на больших списках не стоит, т.к. левый операнд целиком копируется за O(n)

[w495]

Про ++ — уверен? Я не очень.
+ Какая альтернатива?
--> Можно, конечно, вложенные списки, но без опыта функ про осознать не просто.

[seriyPS]

Про ++ вот тут подробно www.erlang.org/doc/efficiency_guide/myths.html#id58137
Для аккумуляторов стараются использовать либо [NewEl | Accumulator] и lists:reverse в конце, либо [List1, List2] и lists:flatten в конце

[w495]

gist.github.com/2924882

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

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

lists:flatten — убийство.
[List1, List2], в зависимоти от целей erlang:list_to_binary

[seriyPS]

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

[w495]

Пробовал. Картина не менялась. Но ждать было лениво.
Если получится что-то иное дай знать.
Но опять же, все может зависеть от версии.
Правда, на память особого внимания не обращал.

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


Так это просто тест конкатенации.
И меня более интересовало представление строк.
О каких алгоритмах речь?

[seriyPS]

алгоритмах?
Имею в виду, что, например такой map

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

( O(n^2) если не ошибаюсь)
На списке из 10 элементов может показывать сравнимую производительность с reverse реализацией, но на 10 000 элементов разница будет огромная.
Лично не проверял, но что-то подсказывает…

[w495]

O(n^2) по времени?
Ну как минимум операций больше.

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

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

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

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

То что lists:flatten — убийство, и использовать надо, только там где он действительно нужен, проверено многократно, на практике. Собственно из-за него я и сделал сравнение.

[glorybox]

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).

[w495]

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

Откуда это все?

[kvl]

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

[w495]

я как истинный нуб в Эрланге предположил и попробовал.

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

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

[nicolausYes]

Кстати, да, примеры довольно сложные для начинающих.

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

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([]) -> [].

[kachayev]

Факториал лучше хвостовкой

factorial(N) -> factorial(N, 1).
factorial(0, Acc) -> Acc;
factorial(N, Acc) -> factorial(N-1, Acc*N).

[w495]

Этот быстрее, но первый по определению.
Если заюзать мемоизацию, то лучше писать, по определению, имхо.

[kachayev]

Каким образом «факториал по определению» раскрывает особенности Erlang как языка программирования?

[w495]

Тем, что не надо думать о деталях.
Хотя бы на первых порах.
Декларативность, что ли.
Ну во общем это не к Erlang, а к функциональным языкам.

[Antiarchitect]

А правильно ли проводить бенчмарк с помощью timer:tc?
У меня нехвостовой вариант факториала от 20000 дает ~ 250 милисекунд, а хвостовой ~ 285.

[seriyPS]

tc(F) ->
    Before = os:timestamp(),
    Val = F(),
    After = os:timestamp(),
    {now_diff(After, Before), Val}.

github.com/erlang/otp/blob/OTP_R15B03-1/lib/stdlib/src/timer.erl#L177
По моему вполне правильно.

[kvl]

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

Спасибо, конечно, но это — для перстановок из N по N.
Из M по N (M<=N) чуть сложнее будет…

[kvl]

Wikipedia: "There is also a weaker meaning of the term «permutation»..."
А вот еще (а можно и еще): http://www.examples10.com/e/permutations-of-less-than-all/
Исходил из того что соответствующие функции как раз называются через «permutations»: Maple: combinat[permute](m,n), Ruby: Array#permutation(n).

[tenzink]

Что и говорить, 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;
}

[nicolausYes]

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

Код был какой-то такой pastebin.com/MhVwqaHT

[5HT]

Чувак тебе нельзя пускать к Эрлангу вообще. Помедитируй еще несколько лет. Играть можеш но код лучше не пиши вообще. Иначе хуже будет. Это угроза!

[kvl]

Очень конструктивно, thanks.
Уже боюсь…

[sumerman]

Статьи точно ещё рано писать :) Читайте книжки, пишите код (ни в коем случае не продакшн), просите попинать.

[sumerman]

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

Это не слишком близко к истине — Erlang действительно обладает уникальным сочетанием фичей, однако по-отдельности концепции проскакивают много где — от дизайна ОС до языков программирования.

[EvilBlueBeaver]

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, то лучше не стоит.

[EvilBlueBeaver]

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

Писать self()! R в вашем случае нельзя, потому что эта функция будет вызвана внутри нового процесса и self() для нее будет логично другим. Именно поэтому вы и замыкаете Supervisor.

[kvl]

Спасибо!
С loop() — наступил на грабли, все действительно просто.
self()! R — не понимал, что тут действует замыкание.
Пошел исправлять.
Предыдущий Ваш комментарий тоже очень полезный, спасибо за замечания.
Учить или агитировать никого не пытаюсь, просто хотелось поделиться впечатлениями (об опыте пока рано говорить) и послушать полезные советы.

[Disasm]

Спасибо за эту маленькую ссылку в середине статьи. Открыл для себя отличный источник знаний.

[sleepwalker]

Это кстати пожалуй самый лучший труд по эрлангу в интернете.