Comments 37
Да… это да.
Не очень хорошие примеры, если честно, слишком сложные, если стояла цель подтолкнуть к изучению Erlang.
Во-первых, нельзя запустить loop() перед spawn_link(). Казалось бы, так будет более надежно, т.к. функция-слушатель, запущенная до запуска потока-исполнителя, наверняка не пропустит ни одного сообщения от этого потока.O_o
Как вы себе представляете запуск
loop() перед spawn_link()???Кстати, использовать
++ на больших списках не стоит, т.к. левый операнд целиком копируется за O(n)
Про ++ — уверен? Я не очень.
+ Какая альтернатива?
--> Можно, конечно, вложенные списки, но без опыта функ про осознать не просто.
+ Какая альтернатива?
--> Можно, конечно, вложенные списки, но без опыта функ про осознать не просто.
Про ++ вот тут подробно www.erlang.org/doc/efficiency_guide/myths.html#id58137
Для аккумуляторов стараются использовать либо
Для аккумуляторов стараются использовать либо
[NewEl | Accumulator] и lists:reverse в конце, либо [List1, List2] и lists:flatten в концеgist.github.com/2924882
lists:reverse — раньше брезговал, но
lists:flatten — убийство.
[List1, List2], в зависимоти от целей erlang:list_to_binary
lists:reverse — раньше брезговал, но
> erlang:is_builtin(lists, reverse, 2).
true
lists:flatten — убийство.
[List1, List2], в зависимоти от целей erlang:list_to_binary
Интересный бенчмарк, спасибо.
Но смущает что списки очень маленькие и влияние сложности алгоритмов небольшое. Попробуйте запустить такие же тесты на списках подлиннее чем 8 элементов, мне кажется результаты могу измениться.
Но смущает что списки очень маленькие и влияние сложности алгоритмов небольшое. Попробуйте запустить такие же тесты на списках подлиннее чем 8 элементов, мне кажется результаты могу измениться.
Пробовал. Картина не менялась. Но ждать было лениво.
Если получится что-то иное дай знать.
Но опять же, все может зависеть от версии.
Правда, на память особого внимания не обращал.
влияние сложности алгоритмов небольшое
Так это просто тест конкатенации.
И меня более интересовало представление строк.
О каких алгоритмах речь?
Если получится что-то иное дай знать.
Но опять же, все может зависеть от версии.
Правда, на память особого внимания не обращал.
влияние сложности алгоритмов небольшое
Так это просто тест конкатенации.
И меня более интересовало представление строк.
О каких алгоритмах речь?
алгоритмах?
Имею в виду, что, например такой map
На списке из 10 элементов может показывать сравнимую производительность с reverse реализацией, но на 10 000 элементов разница будет огромная.
Лично не проверял, но что-то подсказывает…
Имею в виду, что, например такой map
map([], Acc, _) ->
Acc;
map([Element | Elements], Acc, F) ->
map(Elements, Acc ++ [F(Element)], F).
На списке из 10 элементов может показывать сравнимую производительность с reverse реализацией, но на 10 000 элементов разница будет огромная.
Лично не проверял, но что-то подсказывает…
O(n^2) по времени?
Ну как минимум операций больше.
Сложность весьма очевидна в C, и то не всегда (компиляторы умнеют быстро).
Тут мы имеем компилятор, который потенциально может разгуливать подобные ситуации,
и оптимизировать. Для конкретного случая надо проверять. Константа может перекрыть сложность.
Если позволяет логика приложения я бы сделал так:
А развернул бы в другом месте со сходной семантикой.
Иногда это влечет трудно находимые ошибки.
То что lists:flatten — убийство, и использовать надо, только там где он действительно нужен, проверено многократно, на практике. Собственно из-за него я и сделал сравнение.
Ну как минимум операций больше.
Сложность весьма очевидна в C, и то не всегда (компиляторы умнеют быстро).
Тут мы имеем компилятор, который потенциально может разгуливать подобные ситуации,
и оптимизировать. Для конкретного случая надо проверять. Константа может перекрыть сложность.
Если позволяет логика приложения я бы сделал так:
map([], Acc, _) ->
Acc;
map([Element | Elements], Acc, F) ->
map(Elements, [F(Element)|Acc], F).
А развернул бы в другом месте со сходной семантикой.
Иногда это влечет трудно находимые ошибки.
То что lists:flatten — убийство, и использовать надо, только там где он действительно нужен, проверено многократно, на практике. Собственно из-за него я и сделал сравнение.
T: «concat 10000» — 34.600007 s
T: «concat2 10000» — 1.208402 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).
Отметим два неочевидных обстоятельства. Во-первых, нельзя запустить loop() перед spawn_link(). Казалось бы, так будет более надежно, т.к. функция-слушатель, запущенная до запуска потока-исполнителя, наверняка не пропустит ни одного сообщения от этого потока. Но опыт показывает, что в этом случае функция-слушатель вообще не получает сообщения от потока-исполнителя. По-видимому, это связано с тем, что статус отношения потоков не обновляется.
Откуда это все?
Откуда что? Предположение, или результат?
Преположение — мое, я как истинный нуб в Эрланге предположил и попробовал.
В предположении ничего запрещенного не вижу, результат — просто факт, так не получается
Преположение — мое, я как истинный нуб в Эрланге предположил и попробовал.
В предположении ничего запрещенного не вижу, результат — просто факт, так не получается
я как истинный нуб в Эрланге предположил и попробовал.
Так нельзя. Лучше сначала разобраться в вопросе, и потом уже строить предположения.
Есть много чего, о чем мне хочется тут рассказать,
но пока я не буду уверен в правильности и полезности,
делать это бессмысленно. Просто потрачу время, и свое и чужое.
Если это Ваши предположения, то не плохо бы это как-то пометить.
Выглядит как категоричное утверждение.
А неверное предположение, выданное за истину, вызывает негатив.
Кстати, да, примеры довольно сложные для начинающих.
К слову, чтоб не пугать людей, вот так выглядит функция для получения всех перестановок элементов списка.
Просто и элегантно. H — голова, T — хвост, L — список. Увидев функцию первый раз, можно даже разобраться что она делает, не зная языка.
По поводу производительности. Задача: есть множество из 10 элементов. Получить список со всеми возможными перестановками.
Erlang.
Время выполнения — 3980 мс.
Потребляемая память — 713 Мб (это примерно. Во время выполнения занимало больше, очевидно, из-за рекурсии).
С++ list
Время выполнения — 3000 мс.
Потребляемая память — 1053 Мб.
С++ vector
Время выполнения — 700 мс.
Потребляемая память — 228 Мб.
P.S.
Факториал
Quick Sort
К слову, чтоб не пугать людей, вот так выглядит функция для получения всех перестановок элементов списка.
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([]) -> [].
Факториал лучше хвостовкой
factorial(N) -> factorial(N, 1).
factorial(0, Acc) -> Acc;
factorial(N, Acc) -> factorial(N-1, Acc*N).
Этот быстрее, но первый по определению.
Если заюзать мемоизацию, то лучше писать, по определению, имхо.
Если заюзать мемоизацию, то лучше писать, по определению, имхо.
А правильно ли проводить бенчмарк с помощью timer:tc?
У меня нехвостовой вариант факториала от 20000 дает ~ 250 милисекунд, а хвостовой ~ 285.
У меня нехвостовой вариант факториала от 20000 дает ~ 250 милисекунд, а хвостовой ~ 285.
tc(F) ->
Before = os:timestamp(),
Val = F(),
After = os:timestamp(),
{now_diff(After, Before), Val}.
По моему вполне правильно.
>> perms([]) -> [[]];
>> perms(L) -> [[H|T] || H < — L, T < — perms(L--[H])].
Спасибо, конечно, но это — для перстановок из N по N.
Из M по N (M<=N) чуть сложнее будет…
>> perms(L) -> [[H|T] || H < — L, T < — perms(L--[H])].
Спасибо, конечно, но это — для перстановок из N по N.
Из M по N (M<=N) чуть сложнее будет…
UFO just landed and posted this here
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).
А вот еще (а можно и еще): http://www.examples10.com/e/permutations-of-less-than-all/
Исходил из того что соответствующие функции как раз называются через «permutations»: Maple: combinat[permute](m,n), Ruby: Array#permutation(n).
UFO just landed and posted this here
Что и говорить, list comprehensions — чрезвычайно полезная и мощная вещь!
К слову, для данной конкретной задачи аналогичный код на C++ тоже получается достаточно компактным (C++11, чтобы можно было эффективно возвращать по значению)
Можно ускорить процентов на 30-40, если позвать ret.reserve(1*2*...*10), но немного потерять в читабельности. Но лучше всего, конечно просто итерировать, что даёт выигрыш в 10-15 раз.
К слову, для данной конкретной задачи аналогичный код на 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;
}
Чувак тебе нельзя пускать к Эрлангу вообще. Помедитируй еще несколько лет. Играть можеш но код лучше не пиши вообще. Иначе хуже будет. Это угроза!
«Таким образом, в Erlang приходится ломать привычные шаблоны мышления и заменять их новыми паттернами, характерными только для этого языка программирования.»
Это не слишком близко к истине — Erlang действительно обладает уникальным сочетанием фичей, однако по-отдельности концепции проскакивают много где — от дизайна ОС до языков программирования.
Это не слишком близко к истине — Erlang действительно обладает уникальным сочетанием фичей, однако по-отдельности концепции проскакивают много где — от дизайна ОС до языков программирования.
- Выглядит абсолютно нечитаемо.
- Видно, что с общением процессов толком не разобрались.
- В случае some_fun(...) -> some_fun(...) ++ some_fun(...). о хвостовой рекурсии можно забыть, вкупе с "++" получаем дикий расход памяти и проца на больших массивах данных. Спорить по поводу как быстрее сложить 2 списка не стану, но складывать списки на каждом шаге рекурсии явно быстро не будет
- when length(Result) == Number лучше не использовать, почему — читать в доке.
- Remain — [R] я не буду говорить, насколько это медленно на больших объемах
- [R] ++ Result это вообще неприятно видеть, надо [R | Result]
- some_fun(..) -> [some_fun(..) || Some < — Whatever]. — это кстати тоже не хвостовая рекурсия
Если вы нам рассказываете о своем опыте изучения erlang, то это похвально и на вашем месте я бы прислушался к комментариям. Если пытаете учить или подсадить кого-то на erlang, то лучше не стоит.
Кстати loop перед spawn_link запускать не имеет смысла. loop будет крутиться в рекурсии(в вашем случае блокироваться, потому что сообщений нет), а spawn_link так и не вызовется. И никакие «взаимоотношения потоков» тут ни при чем.
Писать self()! R в вашем случае нельзя, потому что эта функция будет вызвана внутри нового процесса и self() для нее будет логично другим. Именно поэтому вы и замыкаете Supervisor.
Писать self()! R в вашем случае нельзя, потому что эта функция будет вызвана внутри нового процесса и self() для нее будет логично другим. Именно поэтому вы и замыкаете Supervisor.
Спасибо!
С loop() — наступил на грабли, все действительно просто.
self()! R — не понимал, что тут действует замыкание.
Пошел исправлять.
Предыдущий Ваш комментарий тоже очень полезный, спасибо за замечания.
Учить или агитировать никого не пытаюсь, просто хотелось поделиться впечатлениями (об опыте пока рано говорить) и послушать полезные советы.
С loop() — наступил на грабли, все действительно просто.
self()! R — не понимал, что тут действует замыкание.
Пошел исправлять.
Предыдущий Ваш комментарий тоже очень полезный, спасибо за замечания.
Учить или агитировать никого не пытаюсь, просто хотелось поделиться впечатлениями (об опыте пока рано говорить) и послушать полезные советы.
Спасибо за эту маленькую ссылку в середине статьи. Открыл для себя отличный источник знаний.
Sign up to leave a comment.
Учимся думать и писать на Erlang (на примере двух комбинаторных задач)