3 заметки с тегом

алгоритмы

Уборка по-программерски

Когда-то ещё в лицее один мой друг изложил следующий простой алгоритм уборки стола:

while ( лажа_на_столе ) do { лажа_на_полу; }

Отличная штука — до сих пор пользуюсь.

Рекурсия

Если моя гипотеза про фракталы верна, то нет ничего удивительного в том, что на собеседовании я очень люблю задавать задачу на рекурсию. Идея не нова, я её нагло украл у Джоэля. Джоэль предлагал задавать вопросы на указатели и рекурсию, я пока ограничился второй, потому что в PHP указателей нет, у нас есть ссылки, но они используются не так часто, поэтому насиловать ими мозг кандидату смысла особо нет.

Традиционно для тестирования понимания рекурсии дают задачу на факториал. Я решил, что факториал — это не модно и придумал задачу в рамках традиционной для похапешников предметной области — вывести дерево категорий онлайн-магазина.

Задача не самая лучшая, но на её примере забавно посмотреть, как люди с ней мучаются. Например, один кандидат в первой версии забыл передать $depth, и ему пришлось дописывать его в решение на листике. Что ещё классно, что у этой задачи нет одного чёткого решения, и каждый изобретает свой велосипед (типичная фигня в программировании). Это видно даже по комментариям к задаче на квизфуле. Так что таким образом заодно можно увидеть, как человек мыслит и какими шаблонами решает задачу. Например, решение через регекспы меня очень позабавило, я бы такого человека взял просто за то, что он пошёл нестандартным путём и нашёл не правильное, но неплохое решение.

Возвращаясь на уровень вверх к фракталам. Задачка на рекурсию тренирует ту самую способность спуститься на уровень вниз и увидеть не только верхний слой, а ещё и то, как он был составлен. То есть увидеть мозгом этот фрактал и в следующий раз подойти к задаче с “двухуровневым” сознанием))

Aktualisierung (22.01.2015): Гриша на яваскрипте написал кошерный вариант — http://jsfiddle.net/cu20x6p8/4/

ПС: Вспомнил, что PHP содержит рекурсию в самом имени. То-то я удивляюсь, чего меня штырит так-то?

Алгоритмы

Вот и у Макса Бурцева я нашёл подтверждение той же самой идеи, которую высказывал раньше: дети познают мир единственным доступным нам методом — методом проб и ошибок. Отличие “взрослых” от “детей” по факту лишь в том, что взрослые перестали учиться и забыли про этот метод. Так что нет никаких “взрослых” и “детей”, есть лишь взрослые дети. Но пост не о том.

Всякий программист, независимо от того, на какой Джаве он программирует, работает с одним и тем же набором алгоритмов — сортировка, поиск минимума, фильтр, мэп-редьюс и так далее. Некоторые при этом даже догадываются, что на уровне ассемблера все их прекрасные единороги, паттерны и прочий говнокод превращается в банальное “попытаться сделать А и, если получится, то пойти и сделать Б, а если не получится, то пойти и сделать В”. Ничего не напоминает? Но пост не о том.

Знаете, почему, как я предполагаю, скайп стал так мегапопулярен, и все на него перешли из аськи? Не из-за видеозвонков или голоса. Скайп был первый, кто добавил возможность исправлять ошибку в отправленном сообщении. Аська этого не умела. Но пост не о том.

Вспомните симплекс-метод и метод градиентного спуска. Это всё — банальный перебор. Симплекс-метод не зря так называется. Он называется так, потому что simple — это “простой”. Это просто самый простой метод. Хотя название тут врёт — это не метод, а алгоритм. И тут и кроется разница. Метод — это всего лишь статический список ваших возможностей для развития, тогда как алгоритм — это динамика. Это чёткая инструкция, как эту статику пошагово переводить в другую статику. Иными словами, алгоритм — это та выборка шагов из метода, которая прямо сейчас де факто таки работает и таки переводит систему из одного состояния в другое. И “симплекс-метод” правильнее называть “симплекс-алгоритм”. Но пост не о том, всё равно всё то, что я тут написал, поймёт всего 1% читателей :))

Так что любая программа, любой самый сложный распараллеленный софт на гламурной Скале или обычный вебсайтик на быдловордпрессе — по сути всего лишь большой-большой фрактал if-else-ов и ничего более. И только от самого программиста зависит, видит ли он самый верхний кусок или способен пройти сквозь фрактал внутрь него, а потом внутрь него и так далее сколько хватит силы.

Ну не умеем мы делать ничего другого, извините. Всё, что мы умеем, это ошибаться. И всё, как мы можем стать лучше — это ошибаться быстрее и точнее. Попытаться сделать А и, если получится, то пойти и сделать Б, а если не получится, то пойти и сделать В.