Часть 2
Иногда программисты на С++ просят привести пример задачи, которая не может быть решена без использования монад. Начнём с того, что этот вопрос неверен сам по себе — это всё-равно, что спрашивать, существует ли задача, которая не может быть решена без циклов. Очевидно, если в вашем языке есть поддержка оператора goto, вы можете обойтись без использования операторов цикла. Что монады (и циклы) могут сделать для вас, это упростить ваш код и помочь лучше его структурировать. Как использование циклов превращает спагетти-код в нормальный, так и использование монад может превратить ваш код в императивном стиле в декларативный. Эта трансформация может помочь легче писать, понимать, поддерживать и расширять ваш код.
Ну и вот вам задачка, которая может попасться на собеседовании. Она не совсем тривиальна, возможно несколько подходов к решению и лучший из них не сразу очевиден — как-раз то, над чем стоит подумать.
Вам предлагается следующий пазл:
s e n d
+ m o r e
---------
m o n e y
Каждая буква соответствует цифре от 0 до 9. Нужно написать программу, которая подберёт такие соответствия, чтобы написанная операция сложения была верной. Перед тем, как продолжить чтение статьи — подумайте минутку, как бы вы решили эту задачу?
Анализ
Никогда не помешает впечатлить интервьюера своими знаниями, корректно классифицировав проблему. Данная задача относится к классу "задач удовлетворения ограничений". Очевидное ограничение состоит в том, что числа, полученные подстановковй цифр вместо букв, при сложении должны дать число, соответствующее заданному. Есть и менее очевидные ограничения, к примеру, слагаемые числа не должны начинаться с нуля.
Если вы попробуете решить эту задачу с помощью ручки и бумаги, вы быстро найдёте несколько эвристик. К примеру, сразу понятно, что m должно быть равно 1, потому что нет двух таких четырёхзначных чисел, которые бы при сложении дали бы число большее 19998. Затем вы выясните, что s должно быть равно 8 или 9, потому что иначе мы не получим переноса разряда для получения пятизначного числа и т.д. Имея достаточное количество времени вы, возможно, напишите экспертную систему, с достаточно большим количеством правил, способную решить эту проблему (а может и другие подобные). Кстати, упоминание экспертной системы может дать вам пару лишних очков на собеседовании.
Есть и другой подход — стоит отметить, что задача имеет достаточно небольшую размерность — мы работаем с 4-5 значными целыми числами, которых не так уж много. Интервьювер может попросить вас попросить количество перестановок, которые нужно будет перебрать — их 10!/(10-8)! = 1814400 штук. Совсем немного для современного компьютера. Таким образом решение задачи сводится к генерации этих перестановок и проверке их на соответствие ограничениям исходной задачи.
Решение «в лоб»
Классический императивный подход сразу порождает код с 8-ю вложенными циклами (у нас есть 8 уникальных букв s, e, n, d, m, o, r, y). Получится что-то типа такого:
for (int s = 0; s < 10; ++s)
for (int e = 0; e < 10; ++e)
for (int n = 0; n < 10; ++n)
for (int d = 0; d < 10; ++d)
...
и так до последней буквы
И тут нам нужно проверить условие. Но не то условие суммы, из исходной задачи — первым делом нам нужно проверить, что все цифры в нашей перестановке разные, а иначе в ней и смысла нет.
e != s
n != s && n != e
d != s && d != e && d != n
…
и так далее, в последней строке будет 7 сравнений, а всего их будет 28 штук. И только после этого можно собрать из цифр числа "send", "more" и проверить, получилось ли в сумму "money".
В общем-то, задача решена и интервьювер не сможет сказать, что неверно. Но минуточку — разве мы не можем придумать что-нибудь получше?
Умное решение
Перед тем, как продолжить, я должен сказать, что всё, что будет написано дальше будет почти прямым переводом с Хаскеля программы, написанной в блоге Justin Le. Я настоятельно советую всем изучить Хаскель и читать подобные статьи в оригинале, а в данном случае я поработаю переводчиком.
Проблема в нашем «лобовом» решении в тех самых 28-и проверках. Да, наша программа заработала, но случилось это из-за её небольшой размерности. Бывают задачи с огромными размерностями и значительно большим количеством условий, так что имеет смысл придумать какой-нибудь общий подход к их решению.
Проблема может быть сформулирована как совокупность двух проблем меньшего размера. Одна из них касается глубины, а вторая — ширины поиска решения.
Давайте сначала посмотрим на проблему глубины. Представим себе задачу создания всего-лишь одной подстановки цифр вместо букв исходного пазла. Это может быть описано как выбор 8 цифр из списка 0, 1, …9, по одной цифре за раз. Как только цифра выбрана — мы убираем её из списка. Мы не хотим жестко забивать список в наш код, так что мы сделаем его параметром нашего алгоритма. Заметьте, что с этим подходом алгоритм будет работать даже для списка с дубликатами или для списка, в котором для элементов не могут быть определены операторы сравнения и равенства (к примеру, список из std::future).
Теперь давайте рассмотрим проблему ширины: нам нужно повторить вышеуказанный процесс для всех возможных перестановок. Это как раз то, что делают 8 вложенных циклов в коде выше. Есть одна проблемка: каждый шаг по выборке очередного элемента из списка деструктивен — он изменяет список. Это известная проблема при переборе пространства решений и её стандартное решение — откат (backtracking). Как только вы обработали некоторого кандидата, вы помещаете элемент обратно в список и пробуете следующий. Это означает, что вам нужно отслеживать своё текущее состояние, либо неявно, сохраняя его в стеке вызовов функции, либо явно — в некоторой структуре данных.
Секундочку! Мы разве не собрались говорить о функциональном программировании? Так к чему же все эти разговоры о модификациях и состоянии? Ну, а кто же сказал, что у нас не может быть состояния в функциональном программировании? Программисты на функциональных языках использовали монаду состояния ещё со времён, когда по Земле ходили динозавры. И модификации — не проблема, если вы используете персистентные структуры данных. Так что пристегните ремни и приведите спинку кресла в вертикальное положение, мы взлетаем.
Монада списка
Мы начнём с небольшой отсылки к квантовой механике. Как вы можете помнить со школы, квантовые процессы не детерминистичны. Вы можете проделать один и тот же эксперимент несколько раз и получить разные результаты в каждом случае. Есть очень интересная точка зрения на квантовую механику, называемая "Многомировой интерпретацией", в которой каждый эксперимент порождает несколько альтернативных исторических линий, в каждой из которых он даёт свой результат, а мы просто попадаем в одну из этих «вселенных» и наблюдаем один конкретный (неизвестный заранее) исход эксперимента.
Мы используем тот же подход к решению нашего пазла. Мы создадим «альтернативные вселенные» для каждой перестановки цифр, соответствующей нашим буквам. Таким образом, мы начнём с 10 вселенных для буквы s: в первой она будет иметь значение 0, во второй — 1 и т.д. Далее каждую из этих вселенных мы разделим ещё на 10 по букве e и т.д. Большинство из этих вселенных не будут удовлетворять наши условия, так что мы будем вынуждены их уничтожить. Такой простой подход к уничтожению вселенных может показаться расточительным и ресурсоёмким, но в функциональном программировании это не проблема: быстренько создали альтернативную реальность и так же быстро уничтожили. Так происходит потому, что новые вселенные не так уж отличаются от тех, на базе которых они были порождены и они могут использовать большинство данных совместно со своими «родителями». Это и есть идея персистентных структур данных. У нас есть неизменяемая структура данных, которая может породить новую путём клонирования. Новая структура данных разделяет большинство данных с родителем, кроме небольшой «дельты». Мы будем использовать персистентные списки, описанные вот в этом посте.
Как только вы осознаете этот подход с «множественными вселенными», реализация становится достаточно простой. Во-первых, нам нужна функция, которая будет создавать новые вселенные. Поскольку мы договорились, что она должна быть «дешевой», генерировать мы будем только те части, которые будут отличаться. Чем отличаются все порождённые по переменной s вселенные? Только значением переменной s. Всего есть 10 таких вселенных, соответствующих значениям s от 0 до 9 (тот факт, что s не может быть равно 0 мы рассмотрим позже). Таким образом, всё, что нам нужно, это функция, которая генерирует список из 10 цифр. Ну и вот они — наши 10 вселенных во всей своей чистой первозданной красоте.
И вот мы оказываемся в одной из этих альтернативной вселенных (вообще-то во всех сразу, но конкретно сейчас рассматриваем попадание в одну из них). Надо как-то жить дальше. В функциональном программировании вся ваша оставшаяся жизнь — это вызов функции, которая называется "продолжение". Я знаю, что это звучит как страшное упрощение. Все ваши действия, эмоции и надежды сводятся к всего-лишь вызову одной функции. Ну, давайте думать, что «продолжение» описывает лишь какую-то часть вашей жизни в этой вселенной, её «вычислительную» составляющую, а всё остальное происходит где-то отдельно.
Итак, к чему же сводится наша жизнь в этой вселенной и что она порождает? Входом является сама вселенная, в которой мы находимся, в частности для нашего примера — одно из значений s, которое мы выбрали при порождении данной вселенной. Но поскольку мы живём в пространстве квантовых экспериментов, на выходе у нас будет набор новых вселенных. Таким образом «продолжение» получает на вход число, а порождает список. Это не обязательно список чисел, а список чего-то, что описывает отличия порождённых вселенных друг от друга.
Ну и в чём же смысл этого нового подхода? Это привязка выбора вселенной к «продолжению». Это то место, где и происходят все действия. Эта привязка, опять таки, может быть выражена в виде функции. Это функция, которая получает на вход список вселенных и «продолжение», которое порождает новый список вселенных (большего размера). Мы назовём эту функцию for_each и мы постараемся написать её настолько обобщённо, насколько это возможно. Мы ничего не будем предполагать о типы переданных или порождаемых вселенных. Мы также сделаем тип «продолжения» параметром шаблона и определим тип возвращаемого значения с помощью auto и decltype:
template<class A, class F>
auto for_each(List<A> lst, F k) -> decltype(k(lst.front()))
{
using B = decltype(k(lst.front()).front());
// ограничения, налагаемые на тип F должны были бы быть выражены с помощью концептов,
// если бы их наконец включили в стандарт языка С++
static_assert(std::is_convertible<
F, std::function<List<B>(A)>>::value,
"for_each requires a function type List<B>(A)");
List<List<B>> lstLst = fmap(k, lst);
return concatAll(lstLst);
}
Функция fmap аналогична стандартной std::transform — она применяет «продолжение» k к каждому элементу списка lst. Поскольку k само по себе возвращает список, результатом будет список списков, lstLst. Функция concatAll объединяет все элементы всех этих списков в один большой список.
Мои поздравления! Вы только что посмотрели на монаду. Она называется монадой списка и может быть использована, в частности, для моделирования недетерминистических процессов. Монада на самом деле определена двумя функциями. Одна из них это вышеуказанная for_each, а вот и вторая:
template<class A>
List<A> yield(A a)
{
return List<A> (a);
}
Это функция yield, которая возвращает список из одного элемента. Мы используем yield на том этапе, когда уже закончим «размножение вселенных» и дойдём до момента, когда мы хотим вернуть одно значение. Мы используем её, чтобы создать «продолжение» содержащеё всего одно значение. Оно представляет собой одинокую скучную жизнь, полностью предопределённую и лишенную любого выбора.
Позже я переименую эти функции в mbind и mreturn, поскольку они определяют монаду в общем, а не только монаду списка.
Имена вроде for_each и yield имеют достаточно «императивное» звучание. Это, конечно, потому, что в функциональном программировании монады в некотором смысле слова выполняют роль императивного кода. Но ни for_each ни yield не являются структурами данных — они являются функциями. Точнее, for_each, которая звучит и работает как цикл, является функцией высшего порядка, как и fmap, которая используется в её реализации. Конечно, на каком-то уровне код станет императивным — тот же fmap может быть написан рекурсивно или с использование цикла, но на верхнем уровне мы имеем лишь декларации функций. Ну и вот оно — декларативное программирование!
Есть существенное отличие между циклом и функцией, вроде for_each: for_each принимает в качестве аргумента весь список, в то время как цикл может генерировать необходимые значения (в нашем случае целые числа) на лету. Это не проблема в функциональном языке с поддержкой ленивых вычислений, вроде Хаскеля — список будет рассчитываться по мере надобности. Аналогичное поведение может быть реализовано и на С++ с использованием потоков или ленивых итераторов. Я не буду делать это здесь, поскольку списки, с которыми мы имеет дело в этой задаче относительно коротки, но вы можете прочесть больше об этом подходе вот в этой статье.
Мы пока ещё не готовы написать полное решение нашего пазла, но я покажу набросок того, как оно будет выглядеть. Представьте, что StateL — это просто список. Посмотрите, какой смысл приобретает общая картина:
StateL<tuple<int, int, int>> solve()
{
StateL<int> sel = &select<int>;
return for_each(sel, [=](int s) {
return for_each(sel, [=](int e) {
return for_each(sel, [=](int n) {
return for_each(sel, [=](int d) {
return for_each(sel, [=](int m) {
return for_each(sel, [=](int o) {
return for_each(sel, [=](int r) {
return for_each(sel, [=](int y) {
return yield_if(s != 0 && m != 0, [=]() {
int send = asNumber(vector{s, e, n, d});
int more = asNumber(vector{m, o, r, e});
int money = asNumber(vector{m, o, n, e, y});
return yield_if(send + more == money, [=]() {
return yield(make_tuple(send, more, money));
});
});
});});});});});});});});
}
Первый вызов for_each принимает выборку целых чисел, sel (пока не будем задумываться об их уникальности), и «продолжение» — лямбда-функцию, которая принимает один интежер, s и генерирует список решений — кортежей из трёх целых чисел. Это «продолжение», в свою очередь, вызывает for_each с выборкой для следующей буквы, e, и т.д.
Самое внутреннее «продолжение» представляет собой условную версию функции yield, названную yield_if. Она проверяет условие и генерирует либо пустой список, либо список, состоящий из одного элемента — решения. Внутри она ещё раз вызывает yield_if, которая вызывает финальный yield. В этом финальном yield, когда он будет вызван (или не будет, если все вышестоящие условия не сработали), будет сгенерировано решение — тройка чисел, удовлетворяющая условию первоначального паззла. Если решений будет больше одного — все они будут добавлены в результирующий список, создающийся внутри for_each.
Во второй части данной серии статей я вернусь к проблеме выбора уникальных чисел и рассмотрю монаду состояния. Также вы можете взглянуть на финальный код на гитхабе.
Задание для самостоятельной работы
- Реализовать for_each и yield для вектора вместо списка. Использовать std::transform вместо fmap
- Используя монаду списка (или реализованную на предыдущем шаге ей «векторную» модификацию), написать функцию, которая будет генерировать названия всех клеток шахматной доски (наборы пар символ от 'a' до 'h' — число от 1 до 8)
- Реализовать версию функции for_each (назовём её repeat), которая возьмёт «продолжение» k типа function<List<B>()> (обратите внимание на отсутствие аргументов). Функция должна последовательно вызвать k для каждого элемента списка lst.
Комментарии (56)
kokorins
24.06.2015 15:01+8Юный c++ программист плачет во мне от числа копирований объектов в приведенной реализации.
a553
24.06.2015 15:26+18То есть, «умное решение» это «тупое решение», но написанное не на for-ах, а на функциях обработки коллекций (foreach, map, ...). Ну ок.
tangro Автор
24.06.2015 17:25Оно ещё не дописано, будет следующая часть. А «умность» будет заключаться в том, что мы избавимся от кучи проверок, которые были вынуждены писать в форах, за счет правильной работы со списками и текущим состоянием.
DrReiz
24.06.2015 19:16От проверок эффективнее всего избавиться, генерируя перестановки в лексикографическом порядке с использованием алгоритма Нарайаны. ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9D%D0%B0%D1%80%D0%B0%D0%B9%D0%B0%D0%BD%D1%8B
dcc0
24.06.2015 22:50А лексикографический порядок разве тут существенен?
Просто алгоритм с протаскиванием числа по строке, при правильной реализации особенно на C/С++, будет быстрее, я гарантирую. = )
habrahabr.ru/post/260111
MuLLtiQ
24.06.2015 17:03+3Да, все-таки оверхед в решении на C++ достаточно высок. Оригинальное решение на Хаскеле очень элегантное.
Хотя как лабораторная задача это весьма интересно.
SmartEngines
24.06.2015 19:22+3Такую задачу можно решить одним циклом с std::next_permutation(...) и простой проверкой правильности ответа.
Приведите, пожалуйста, пример задачи (подозреваю, что она будет довольно «промышленной»), которую действительно есть смысл решать с помощью монад на С++, причем без сильного оверхеда. Еще лучше, если у вас уже был такой опыт.
AlexPublic
27.06.2015 17:33Да, с помощью next_permutation эта задачка решается на C++ в 4 строчки. Но при этом такое решение минимум в 5 раз медленнее варианта со списками (типа того, что я привёл ниже), т.к. делает много ненужной работы.
fshp
24.06.2015 19:59-2потому что нет двух таких четырёхзначных чисел, которые бы при сложении дали бы число большее 19998
Странные рассуждения у автора. Пытается сократить код, обобщить его. А примеры приводит совсем конкретные. Строго говоря, при сложении всегда в старший разряд переносится максимум 1.
Aquahawk
24.06.2015 22:43+3Каждая буква соответствует цифре от 0 до 9.
Из этого совсем не следует того что разные буквы не могут иметь одно численное значение. И вообще корявый способ решения. Сейчас поиграюсь и возможно приведу и без всяких монад адекватный способ.
amosk
25.06.2015 02:50+1Извините, что без монад :)
/* * s e n d * + m o r e * --------- * m o n e y * */ bool digits[10] = {0}; char letters[8] = {'s', 'e', 'n', 'd', 'm', 'o', 'r', 'y'}; int result[8] = {}; int& s = result[0]; int& e = result[1]; int& n = result[2]; int& d = result[3]; int& m = result[4]; int& o = result[5]; int& r = result[6]; int& y = result[7]; void print() { cout << " " << s << " " << e << " " << n << " " << d << endl; cout << "+ " << m << " " << o << " " << r << " " << e << endl; cout << "---------" << endl; cout << m << " " << o << " " << n << " " << e << " " << y << endl; } bool solve(int letter) { if (letter == sizeof(letters)) { if (m == 0 || s == 0) return false; bool solved = (((s * 10 + e) * 10 + n) * 10 + d) + (((m * 10 + o) * 10 + r) * 10 + e) == ((((m * 10 + o) * 10 + n) * 10 + e) *10 + y); return solved; } for (int i = 0; i < 10; i++) { if (digits[i]) continue; digits[i] = 1; result[letter] = i; if (solve(letter + 1)) return true; digits[i] = 0; } return false; } int main() { if (solve(0)) { print(); } return 0; }stack_trace
28.06.2015 20:06Как-то по стилю больше на С похоже
amosk
29.06.2015 05:03Извините, что без классов ))
stack_trace
29.06.2015 09:43+2Дело не в классах, а в глобальных переменных и странных функциях с побочными эффектами.
P.S. Я, конечно же, понимаю, что это просто решение задачи и вы не стремились создать сверхсопровождаемый код ) Просто обратилось внимание на это.
CrackedSapphire
25.06.2015 07:08экспертная система на бумажке дала рез на 5-ой итерации, почувствовал себя нужным
dcc0
01.07.2015 22:19-1Такую за сколько решите: до+фа=ага?
Только сейчас составил.
BlessMaster
06.07.2015 15:55+1Три шага, двадцать четыре варианта решения, бумажка в отличие от оригинальной задачи не требуется. Несерьёзно.
AlexPublic
25.06.2015 16:20+4На нормальном C++ можно легко написать вариант со списками без всяких монад:
constexpr array<uint8_t, 10> digits={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; class task{ uint8_t s, e, n, d, m, o, r, y; bool _ok=false; auto to_int(initializer_list<uint8_t> l) {return accumulate(l.begin(), l.end(), 0, [](unsigned sum, uint8_t d){return sum*10+d;});} public: auto ok() {return _ok;} auto order() {return tie(s, e, n, d, m, o, r, y);} void check() {_ok=m!=0&&s!=0&&(to_int({s,e,n,d})+to_int({m,o,r,e})==to_int({m,o,n,e,y}));} void print() { if(ok()) cout<<' '<<to_int({s,e,n,d})<<"\n+"<<to_int({m,o,r,e})<<"\n-----\n"<<to_int({m,o,n,e,y})<<endl; else cout<<"there is no solution"<<endl; } }; template<size_t N=digits.size()> auto solve(task t=task(), const array<uint8_t, N>& ds=digits) { for(auto d: ds){ get<digits.size()-N>(t.order())=d; array<uint8_t, N-1> new_ds; remove_copy(ds.begin(), ds.end(), new_ds.begin(), d); auto r=solve(t, new_ds); if(r.ok()) return r; } return t; } template<>auto solve(task t, const array<uint8_t, digits.size()-tuple_size<decltype(t.order())>::value>&) {t.check(); return t;} int main() {solve().print();}
Причём его можно будет безопасно распараллелить в одну строчку. Это я к тому, что обычно называют главным бонусом ФП стиля. Хотя в данной задачке это естественно не требуется, так что в принципе можно сделать передачу task'a по ссылке и получить чуть большую эффективность, но тогда это будет уже не готовый к распараллеливанию код.
freuser
26.06.2015 00:39А я вот на python накодил:
ten = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0} def rang(c, sendmory): if len(sendmory) < 8: for i in (ten^c): if len(sendmory) == 4 and i == 0: # это чтобы не было кучи ложных решений с нулём в начале слова 'more' continue rang(c^{i}, sendmory+str(i)) else: k = {i:[] for i in range(8)} for i in range(8): k[i] = int(sendmory[i]) if (k[0]*1000+k[1]*100+k[2]*10+k[3]+k[4]*1000+k[5]*100+k[6]*10+k[1]) == (k[4]*10000+k[5]*1000+k[2]*100+k[1]*10+k[7]): print ' '+sendmory[0:4]+'\n+'+sendmory[4:7]+sendmory[1]+'\n-----\n'+sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]+'\n'+sendmory c = set({}) rang(c, '')
Почему-то решение выводит на последних секундах из полутора минут ;)
Не надо городить каскады, масштабируется легко.
Подозреваю, что кто-то из вышекомментировавших уже писал подобное, но C++ почти не понимаю, честно писал сам.
P.S. Имена переменных беру от фонаря, да и вообще я не программист, просто поделиться захотелось…AlexPublic
26.06.2015 01:34+1Я данный код на Питоне ещё не разбирал, но сразу хочу сказать, что «полторы минуты» — это просто беспредел какой-то. ) Если что, код выше (который на C++) исполняется 3,5 миллисекунды.
dcc0
26.06.2015 08:12+1Складывается ощущение, что для каждой статьи обязательно найдется человек, который сочтет своим долгом показать, как «это» делается на Python.
freuser
26.06.2015 10:15+1Ну в принципе давно известно, что чем ниже к железу, тем быстрее. Слегка оптимизировать и уже полминуты:
ten = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0} def rang(c, sendmory): if len(sendmory) < 8: for i in (ten^c): if (len(sendmory) == 4 or len(sendmory) == 0) and i == 0: continue rang(c^{i}, sendmory+str(i)) else: if (int(sendmory[0:4])+int(sendmory[4:7]+sendmory[1]))==int(sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]): print ' '+sendmory[0:4]+'\n+'+sendmory[4:7]+sendmory[1]+'\n-----\n'+sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]+'\n'+sendmory c = set({}) rang(c, '')
Это я уже подсмотрел в код amosk'а (не в Ваш, тот дюже зубодробительный). А вначале я и под кат не ходил, набросал пару вариантов, один выложил.
Зато кратко и наглядно — если не считать кучи срезов в конце, всё можно разъяснить на пальцах.
2 dcc0: а Вы бы хотели, чтобы «это» делали на ассемблере? Или ничего не писали, кроме того, что Вам лично интересно? Так не бывает…
Я периодически брал чужие решения на Python и разбирал — так и научился быдлокодить, для дома хватает. Пора отдавать долги. Или Вы считаете, что я маньяк Python и желаю разжечь холивар? Увы, нет. Инструмент, как инструмент.AlexPublic
26.06.2015 12:08+1Полминуты??? Вот этот вот код??? Это что же у вас за компьютер такой? ))) У меня этот ваш пример исполняется 4 секунды на обычном Питоне и 0,1 секунды на PyPy.
Кстати, если пытаться сделать на Питоне наиболее близкую аналогию моему коду, то этот ваш пример надо чуть подправить:
def rang(c={1, 2, 3, 4, 5, 6, 7, 8, 9, 0}, sendmory=''): if len(sendmory)<8: for i in (c): if i==0 and (len(sendmory)==4 or len(sendmory)==0): continue rang(c-{i}, sendmory+str(i)) else: if int(sendmory[0:4])+int(sendmory[4:7]+sendmory[1])==int(sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]): print ' '+sendmory[0:4]+'\n+'+sendmory[4:7]+sendmory[1]+'\n-----\n'+sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7] rang()
Получается и внешне попроще и выполняется чуть лучше — 3,2 секунды на обычном Питоне. Хотя до результатов C++ конечно же всё равно огромная пропасть, даже с PyPy.freuser
26.06.2015 12:38Обычный ноут четырехлетней давности, нечищенный ни разу. Во избежание перегрева переведен на 'powersave' :]]
Да, Ваш вариант выгадал еще 4 секунды у меня, примерно пропорционально. Что ж, когда соберусь изучать C++, начну с Вашего примера, хоть и страшно смотреть. Главное — что алгоритм я знаю, а остальное дело техники.
dcc0
27.06.2015 20:15Лично меня интересует максимально понятное и краткое описание алгоритма или метода естественным языком, можно с картинками :)
А его конкретная реализация — это некая частность, которая может быть кому-то интересна, а кому-то нет.
Или ничего не писали
Пишите-пишите.
BlessMaster
28.06.2015 00:18Ну, если не гнаться за количеством строчек, то вполне можно и с помощью читабельного кода за полсекунды посчитать.
gist.github.com/alexander-irbis/34828a5e9dc41940f506
При этом, самый читабельный вариант на удивление оказывается и самым быстрымAlexPublic
28.06.2015 02:03+1В случае Питона скорость — это довольно неоднозначное понятие. К примеру ваш код (test_dict) исполняется на моём компьютере за 0,33 секунды — казалось бы намного (в 10 раз!) лучше результата кода freuser'a. Однако, если мы запустим тоже самое с помощью PyPy, то ваш код исполнится за 0,14 секунды, что ощутимо медленнее чем у freuser'a (там было 0,1 секунды). Так какой же вариант считать самым быстрым? )
BlessMaster
28.06.2015 06:29Не стоит забывать, что кроме всего прочего ещё важна и версия интерпретатора и возможности процессора и насколько транслятор PyPy эффективно под процессор подстраивается.
Одним из вопиющих примеров разницы между вторым и третьим питоном, возмутившим меня в своё время, является range: xrange во втором обрабатывается раза в три (плюс/минус лапоть) быстрее range в третьем (и это касается и pypy).
Бенчмарки для того и пишутся, чтобы понять, что на самом деле эффективно, а ради чего не стоило мучаться.
Я там ещё один вариант добавил, которым эта задача на самом деле™ должна решаться и он «рвёт шаблоны» о производительности python и pypy (по крайней мере на моей машине) — интерпретатор обгоняет компилятор в пять раз.
Добавил вариант freuser и прогнал тесты через второй. Очень интересный результат в pypy2. Похоже сказывается его лучшая оптимизированность.
Ну и решение в десяток строчек против четырёх десятков — всё-таки, как ни крути, красиво.BlessMaster
28.06.2015 06:45Особенно интересно обратить внимание на вот этот результат:
1.324 sec; test_freuser_ft_alex
0.118 sec; test_freuser_ft_alex_2
Я специально проверил результат поменяв порядок выполнения функций, но нет, всё стабильно.
Различия между функциями минимальны и я ожидал бы, что _2 будет работать чуть дольше (как это и происходит в других версиях), но внезапно. В то же время у Вас, я так понимаю вполне оптимально выполнился код первого варианта?AlexPublic
28.06.2015 10:10Не очень понял кто такие test_freuser_ft_alex и test_freuser_ft_alex_2 — в исходниках такого нет. Но если речь о каких-то примерах из данной темки, то я уже озвучивал все цифры измерений в комментариях выше.
BlessMaster
28.06.2015 17:41Прошу прощения, затерялось ))
Обновил код.AlexPublic
28.06.2015 21:18+1А ну ОК, мои результаты в Python:
0.012 sec; test_z_interval 0.327 sec; test_dict 0.606 sec; test_list2 0.683 sec; test_list 0.744 sec; test_obj 3.389 sec; test_freuser_ft_alex_2 3.436 sec; test_freuser_ft_alex
и в PyPy:
0.059 sec; test_z_interval 0.067 sec; test_freuser_ft_alex_2 0.138 sec; test_dict 0.159 sec; test_list 0.162 sec; test_list2 0.168 sec; test_obj 0.748 sec; test_freuser_ft_alex
Ну и слабая оптимизация test_freuser_ft_alex в PyPy не особо удивительна, т.к. вы тут переделали её в генератор, а такие вещи (там же внутри по сути сопрограмма) неудобны для оптимизатора. Так что ничего странного, не то что с test_z_interval, где действительно нетривиальная ситуация.BlessMaster
01.07.2015 00:23Дело в том, что как раз переделанная в генератор в PyPy отработала быстрее, чем полностью аналогичная без генератора. Но тут на самом деле удивляться нечему: просто выскользнуло из внимания, что без генератора нет механизма завершения выполнения и алгоритм выполняет бессмысленный перебор всех оставшихся вариантов. Из-за этого получается сильно заниженный результат. И вот тут как раз возникает другой парадокс: почему в CPython одинаковое время выполнения?
AlexPublic
01.07.2015 07:28А, ну да, у меня просто измерение времени было внутри главного if'a (перед print'ом), поэтому я разницу с yield не замечал.
А разница там потому, что в PyPy оказывается почему-то используется другой алгоритм обхода элементов множества. В PyPy обходит как есть, начиная с конца. А в Python'e сортирует и обходит с начала. И соответственно если в Питоне у нас попадание происходит на 2002675 варианте (из 2085787), то в PyPy на 116139. «Исправляется» это всё просто: достаточно поменять c={1, 2, 3, 4, 5, 6, 7, 8, 9, 0} на c={0, 9, 8, 7, 6, 5, 4, 3, 2, 1} и результаты генератора в PyPy вернутся к норме — станут одинаково тормозными. )))
P.S. Кстати, судя по всему значительная часть крутой оптимизации PyPy, выявленной в данном обсуждение, на самом деле заключалось в случайном попадание на более выгодную начальную последовательность. )))
P.P.S. Поставил изначальную обратную последовательность в C++ код и повеселился от времени вычисления в 0,13 мс. Мда, всё же данную задачку можно использовать как тест, только если потребовать искать все возможные решения (чтобы код просмотрел все варианты).AlexPublic
01.07.2015 07:57И кстати говоря проблему непонятного поведения test_z_interval в PyPy это тоже объясняет. ))) Правда там ещё надо убрать sorted (зачем оно там вообще было?) и можно полюбоваться на миллисекундные результаты и для Питона. Правда это всё несерьёзно уже — нельзя так измерять. Надо требовать выдачу всех возможных комбинаций. )
BlessMaster
06.07.2015 16:14+1Изначально sorted ставились для однозначности порядка вычисления и сравнения разных интерпретаторов и механизмов работы с памятью в python. Поскольку порядок играет роль, то в случае использования несортированного множества (set), при каждом запуске порядок элементов в множестве различается, задача найти единственное решение даёт достаточно широкий разброс времени выполнения от долей секунды до десятков секунд и это лишает смысла сравнение.
Вытаскивание m на первое место — это как заметил freuser — действительно «жульничество», но это уже в самой статье обсуждённый вариант — m равна единице и ничему иному и это ускоряет перебор на порядок; постановка её на первое место — автоматически делает её единицей. Если продолжить идти путём жульничества, то мы изначально сразу знаем m, s и o и уже только это сокращает тупой перебор в 720 раз. А если идти до конца, то, как тут выше в комментариях справедливо заметили, всё значительно проще решается на бумажке.
freuser
03.07.2015 20:07+1Прошу прощения за поздний комментарий, текучка заела, добрался посмотреть Ваш код только сегодня.
А ведь Вы слегка сжульничали — мой вариант считает все комбинации и выходит после полного перебора, а Ваши мало того, что считают до первого попадания, так еще и ставят 'm' в начало, так что она вообще в переборе не участвует (она ведь равна 1 в ответе, вот уже почти десятикратный выигрыш). Сам перебор не бессмысленный, вполне может быть несколько вариантов ответа, как и не быть ни одного. Если принять, что 'm' может быть 0, то их вообще 24 штук, но тогда условие избыточно (хотя математически верно и задача в принципе решена).
Переделал все подпрограммки с вашего git вместо return на print и добавил return после цикла for (чтобы не ломать счётчик времени), и вот результат (сами цифры не важны, это у меня интерпретатор в Альте кривой какой-то, главное — соразмерность друг с другом):
0.213 sec; test_z_interval
24.966 sec; test_freuser_ft_alex
26.392 sec; test_freuser_ft_alex_2
33.635 sec; test_dict
48.476 sec; test_list2
53.504 sec; test_list
58.025 sec; test_obj
Видите, если не считать z_interval, все остальные медленнее. А то я прямо уважать себя перестал — мало того, что Ваши алгоритмы не понял сразу, особенно z_interval, так еще и мой самый медленный.BlessMaster
06.07.2015 18:21test_freuser_ft_alex_2 — это как раз был вариант доработанный до выхода сразу при нахождении первого ответа. Про жульничество я написал чуть выше — это «жульничество» сразу напрашивается на оптимизацию, как только обнаруживается, что разный порядок обработки даёт разную скорость и разница существенна нахождения единственного ответа. test_interval — это уже окончательно оптимизированный вариант.
«А то я прямо уважать себя перестал» — нет, вот это Вы зря, у Вас очень красивое решение, задействующее сильные стороны Python. В любом случае, значительно большая часть времени уходит на написание самого алгоритма, а выполняется он, несопоставимо быстрее даже в самом медленном варианте. Я потратил значительно больше времени на написание, поскольку занимался исследованием эффективности работы самого интерпретатора и наглядности кода при этом и данная задача просто оказалась «в тему».
К сожалению как оптимизировать Ваш вариант мне слёту в голову не пришло, а надо было просто немного уделить этому внимание. Вот новый вариант
gist.github.com/alexander-irbis/34828a5e9dc41940f506
test_freuser_ft_alex_3 — это дополненная «жульничеством» с m функция. В PyPy этот вариант лидирует с отрывом.
Ещё интересно взглянуть на результат test_dict_str2int — это первоначальный вариант, который я использовал, пока не обнаружил, что преобразование из строки в число — это дорого.freuser
06.07.2015 23:21test_freuser_ft_alex_2 — это как раз был вариант доработанный до выхода сразу при нахождении первого ответа.
И он отличался от первого на секунды (у Вас на десятые доли), потому что ответ в последних рядах :(test_freuser_ft_alex_3 — это дополненная «жульничеством» с m функция. В PyPy этот вариант лидирует с отрывом. Ещё интересно взглянуть на результат test_dict_str2int — это первоначальный вариант, который я использовал, пока не обнаружил, что преобразование из строки в число — это дорого.
Ну вот, другое дело — хотя действительно, эти переходы int<->str и обратно всё равно малину портят.
Вот вариант без конвертации (по мотивам Вашего кода — вместо строки список)
За счет отказа от переходов выигрыш при полном переборе почти вдвое:def test_freuser_3(): ten = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0} def rang(c, msendory): if len(msendory) < 8: for i in (c): if len(msendory) == 0 and i == 0: continue msendory.append(i) rang(c-{i}, msendory) msendory.remove(i) else: if (msendory[1]*1000+msendory[2]*100+msendory[3]*10+msendory[4]+msendory[0]*1000+msendory[5]*100+msendory[6]*10+msendory[2]) == (msendory[0]*10000+msendory[5]*1000+msendory[3]*100+msendory[2]*10+msendory[7]): print msendory rang(ten, []) return (-1, -1, -1)
0.241 sec; test_z_interval
17.102 sec; test_freuser_3
29.788 sec; test_freuser_ft_alex
34.081 sec; test_dict
35.521 sec; test_freuser_ft_alex_2
52.696 sec; test_list2
53.344 sec; test_list
68.790 sec; test_obj
90.478 sec; test_dict_str2int
а при оптимальном (m вначале и остановка при первом ответе) на четверть от freuser_ft_alex_3:
0.102 sec; test_z_interval
2.196 sec; test_freuser_3
2.841 sec; test_freuser_ft_alex_3
3.233 sec; test_dict
4.949 sec; test_list2
5.634 sec; test_list
6.043 sec; test_obj
7.438 sec; test_dict_str2int
27.013 sec; test_freuser_ft_alex_2
Интересно, в Pypy он догонит z_interval или нет? (Кстати, не могу понять, почему при полном переборе z_interval аж 8 раз дает ответ — depth ведь равно пяти. На каждую букву словаря, что ли).
Боюсь, ещё оптимизировать некуда. Как говорится, постояв на вершине, надо с неё спускаться и лезть на следующую.
AlexPublic
28.06.2015 10:08Да, вариант test_z_interval исполняется у меня за 13 миллисекунд, но я не вижу смысла сравнивать эту цифру с остальными. Потому как это не другая запись того же алгоритма, а совсем другой алгоритм с дополнительной проверкой, отбрасывающей большинство веток перебора. Т.е. если скажем закодировать этот же алгоритм на C++, то там будут вообще микросекунды. )))
А вот то, что этот код исполняется на PyPy даже дольше, действительно весьма забавно. ))) Но тут думаю все вопросы к авторам PyPy.BlessMaster
28.06.2015 18:00test_z_interval был интересен именно в контексте обсуждения «ну и что же считать самым быстрым». Всё относительно. Озвученные Вами результаты остальных тестов сильно не совпадают с полученными мною (и я говорю не об абсолютных числах), это хорошая тема для исследования и лишнее напоминание о бессмысленности преждевременной оптимизиации.
Сравнивать время исполнения с языками типа C++ бессмысленно, но когда время исполнения — в любом случае меньше секунды, значительно интереснее сравнивать трудозатраты программиста, которые для решения этой задачи явно не сопоставимы с затратами машинного времени и оптимизация требуется именно для них.
Именно об этом статья и именно поэтому и появилась эта ветка с питоном и последующие за ней.
Я вот от статьи действительно ожидал, что будет продемонстрирован подход позволяющий быстро писать лаконичный, понятный код, позволяющий проще реализовать сложные алгоритмы. Ждём продолжения или кому не терпится — ищем и изучаем самостоятельно )
Upd. А собственно уже не ждём )AlexPublic
28.06.2015 21:00+1Сравнивать время исполнения с языками типа C++ бессмысленно, но когда время исполнения — в любом случае меньше секунды, значительно интереснее сравнивать трудозатраты программиста, которые для решения этой задачи явно не сопоставимы с затратами машинного времени и оптимизация требуется именно для них.
Нууу это сильно зависит от задачки. К примеру если мы работает с обработкой видео в реальном времени, то понятно что нам важна каждая миллисекунда.
Но даже если забыть о таких задачах, то всё равно быстродействие инструмента позволяет некоторые любопытные вещи. К примеру в данном случае мы можем написать тупейший (но зато короткий и простой) код на C++ вида (да, это опять же получается слегка другой алгоритм):
array<int, 10> res; int& s = res[0]; int& e = res[1]; int& n = res[2]; int& d = res[3]; int& m = res[4]; int& o = res[5]; int& r = res[6]; int& y = res[7]; iota(res.begin(), res.end(), 0); auto to_int=[](initializer_list<int> l) {return accumulate(l.begin(), l.end(), 0, [](unsigned sum,int d){return sum*10+d;});}; do{ if(m!=0&&s!=0&&(to_int({s,e,n,d})+to_int({m,o,r,e})==to_int({m,o,n,e,y}))){ cout<<' '<<to_int({s,e,n,d})<<'\n'<<'+'<<to_int({m,o,r,e})<<'\n'<<"-----"<<'\n'<<to_int({m,o,n,e,y})<<endl; break; } } while(next_permutation(res.begin(), res.end()));
и он будет быстрее самого умного варианта на Питоне, не смотря на то, что делает множество ненужных вычислений. Т.е. быстрый инструмент может позволить не только делать быстрый код, но и позволяет быстрое написание кода, т.к. выдаёт приемлемые результаты и с тупейшими алгоритмами в лоб.
На Питоне тоже можно написать такой же тупой код (itertools.permutations у нас имеется), но он будет исполняться неприлично долго. Можно даже ускорить его благодаря наличию itertools.combinations, но всё равно это несравнимые числа.
Я вот от статьи действительно ожидал, что будет продемонстрирован подход позволяющий быстро писать лаконичный, понятный код, позволяющий проще реализовать сложные алгоритмы. Ждём продолжения или кому не терпится — ищем и изучаем самостоятельно )
Да, сама статья про монады вообще не интересная вышла. В реальности в современных императивных языках монады не особо нужны. Но всё же есть парочка полезных применений, типа конвейеров (Boost.Range) или продолжений (future.then(...)). Однако автор ничего не сказал про них, а вместо этого привёл пример отлично решающийся без всяких монад, обосновав это классической словесной чепухой в стиле фанатов ФП. В общем общение в комментариях к этой статье было на порядок интереснее самой статьи. )))BlessMaster
01.07.2015 00:44Согласен, когда мы не упираемся в зависимость от медленных механизмов вроде диска или сети — это преимущество действительно сильно. И есть задачи не решаемые без выжимания всей производительности. Но, если будет зависимость от дорогих или медленных ресурсов, вперёд всё равно вырвутся «красивый» стиль и язык, позволяющие коду быть лаконичным и понятным (специально не делаю никаких выводов и допущений о единственно верном стиле и языке на все времена)
zahardzhan
26.06.2015 04:16Попробуйте решить эту задачу с помощью реализации самопального пролога на С++. Интересно на это взглянуть.
AlexPublic
26.06.2015 12:10Не знаю что за самопальные прологи на C++ имеются в виду. Но на обычном Прологе решение данной задачки записывается в 3 строчки. И считается около 0,7 секунды.
zahardzhan
26.06.2015 12:46Запости код.
AlexPublic
26.06.2015 16:22+4Чуть подправил его. Стало 4 строчки и 0,2 секунды. )))
to_int(D5,D4,D3,D2,D1, R):- R is D5*10000+D4*1000+D3*100+D2*10+D1. solve(_, S:E:N:D:M:O:R:Y:r):- !, S=\=0, M=\=0, to_int(0,S,E,N,D, Send), to_int(0,M,O,R,E, More), to_int(M,O,N,E,Y, Money), Money is Send+More, write(' '), writeln(Send), write('+'), writeln(More), writeln('-----'), writeln(Money). solve(L, R):- member(N, L), delete(L, N, L1), solve(L1, N:R). solve:- numlist(0, 9, L), solve(L, r).zahardzhan
28.06.2015 18:19Брутфорс на лиспе выглядит примерно так же.
(defn as-num [& digits] (apply + (map * (reverse digits) (iterate (partial * 10) 1)))) (some (fn [[s e n d m o r y]] (and (pos? s) (pos? m) (let [send (as-num s e n d) more (as-num m o r e) money (as-num m o n e y)] (when (= (+ send more) money) (println send \+ more \= money))))) (clojure.math.combinatorics/permutations [0 1 2 3 4 5 6 7 8 9]))
ik62
27.06.2015 11:45+2Как вариант наверное можно использовать ленивые комбинации и перестановки. На D выглядит так (nextPermutation — библиотечная функция, combinations — темплейт c rosettacode):
void main() { foreach (c; [0,1,2,3,4,5,6,7,8,9].combinations(8)) { do { // sendmory = c auto m = c[4]; if ( m == 0 ) continue; auto s = c[0]; auto e = c[1]; auto n = c[2]; auto d = c[3]; auto o = c[5]; auto r = c[6]; auto y = c[7]; if ( [s,e,n,d].to_int + [m,o,r,e].to_int == [m,o,n,e,y].to_int ) write(c); } while (c.nextPermutation!"a<b"); } }miriarder
01.07.2015 19:57Предлагаю вариант на перле:
Скрытый текст#!/usr/bin/perl -w use Time::HiRes qw(gettimeofday tv_interval); @list = ([0,0],[1,0],[2,0],[3,0],[4,0],[5,0],[6,0],[7,0],[8,0],[9,0]); sub clear { foreach my $i (@list) { $i->[1] = 0; } } sub get { my $idx = int(rand(scalar @list)); while($list[$idx]->[1] == 1) { $idx++; $idx = 0 if ($idx >= scalar @list); } $list[$idx]->[1] = 1; return $list[$idx]->[0]; } sub a2i { my ($a) = @_; my $s = 0; my $r = 1; for( my $v = scalar @$a - 1; $v >= 0; $v -= 1) { $s += $a->[$v] * $r; $r *= 10; } return $s; } sub check { my ($a, $b, $c) = @_; my $r = a2i($c) == (a2i($b) + a2i($a)); #print_sol($a, $b, $c); return $r; } sub print_int { my ($r) = @_; my $s = ''; foreach my $i (@$r) {$s .= "$i";} return $s; } sub print_sol { my ($a, $b, $c) = @_; print print_int($a). ' + '.print_int($b).' = '. print_int($c)."\n" ; } my $t0 = [gettimeofday()]; my ($a, $b, $c); do { do { clear(); $a = [get(), get(), get(), get()]; $b = [get(), get(), get(), $a->[1]]; $c = [$b->[0], $b->[1], $a->[2], $b->[3], get()]; } while ($a->[0] == 0 || $b->[0] == 0 || $c->[0] == 0); } while(check($a, $b, $c) == 0); print_sol($a, $b, $c); print 'Time spent: '. tv_interval($t0)."\n";dcc0
01.07.2015 11:40Интересно, какие результаты в среднем будут при случайном перемешивании массива, так как ищем одну перестановку, то не должно быть долго?!
<?php $begin_time = time() - 1272000000 + floatval(microtime()); $a=array(1,2,3,4,5,6,7,8,9,10); $b=array(7,1,3,5,4,6,2,8,10,9); $i=0; while ($i != 3628800) { shuffle($a); if ($a==$b) { print_r($a); break; } $i++; } $end_time = time() - 1272000000 + floatval(microtime()) - $begin_time; echo $end_time;$begin_time = time() - 1272000000 + floatval(microtime()); ?>
Выдает результаты для 3 попыток: 0.056333005428314, 0.26838698983192,
1.1526199877262.
+ Время на сложение и подстановку символов.
Правда, однозначной гарнтии с первой попытки получить, наверное, нет.
Но в среднем проваливается каждая 3-я попытка.
BlessMaster
06.07.2015 19:05Смотря что Вы имеете в виду «долго». Минимальный результат — миллисекунды или меньше, сколько там нужно, когда цифры ложатся ровно на свои места, максимальный — время полного перебора, когда перебор не завершается нахождением первого найденного ответа, когда удачной является последняя комбинация в переборе.
PapaBubaDiop
Хабр стал невыносим -не дает поставить плюсик за Вашу публикацию. Газу, говорит, веселящего у меня не хватает…