Большой опрос по алгоритмам

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

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

auto mid = start + std::distance(start, end) / 2;

или, для более широкого круга итераторов:

auto mid = start;
std::advance(mid, std::distance(start, end) / 2);

То есть я правильно понимаю, что если не могу переизобрести RBTree, а как именно черный дядя с красным племянником взаимодействуют не помню, то галочку не ставлю?

Нам платят не за забивание головы тем, что гуглится за 5 минут. Ничего грустного в этом нет — наоборот, больше места в памяти для хранения уникальных знаний и навыков. Помните Шерлока Холмса, который не знал устройство солнечной системы, зато знал сотни сортов табака? :)

И у квиксорта тоже несколько вариантов и модификаций, а некоторые небезызвестные люди вроде Robert Sedgewick и вовсе диссертацию по нему защитили. С таким же успехом можно к большому количеству алгоритмов придраться… Или Вы действительно думаете, что у этого опроса высокая точность? :)

"Maximum subarray problem" обычно попадает туда же, куда и Дейкстра: не бывает хороших программистов, не умеющих подобный алгоритм реализовать, но бывают хорошие программисты, не умеющие его назвать.

Вопрос для "Дейкстры": как пойдёт юнит в Цивилизации, если его задача — дойти максимально быстро до точки, куда его послали? Hint: Убедитесь что ваш модуль объезжает болото по железной дороге если это выгодно и прёт напролом, если железная дорога слишком длинна.

Вопрос для "maximum subarray problem" — собственно формулировка задачи.

это не алгоритм, а реализация

Причём там могут применять несколько разных сортировок в зависимости от количества элементов.

По поводу сложности — для уже отсортированного массива из неповторяющих элементов если не вычислять медианы или не рандомизировать алгоритм то в любом случае это O(n^2).

И 3-way тоже имеет квадратичную сложность на некоторых наборах.

Раз Вы считаете, что мой ответ полезен, могу его дополнить.

В-третьих, от того, каким будет распределение голосов на таком опросе ровным счётом ничего не зависит. Если опрос покажет, что программисты должны изучать алгоритмы, то никто не побежит покупать книги вроде (простейших) Т. Кормена "Алгоритмы. Построение и анализ", а если покажет, что не должны, то никто не побежит эти книги выбрасывать. Потому что каждому своё. Вот, скажем, должен ли печник хорошо владеть основами строительной механики? По идее да, но только очень поверхностно, чтобы лишь грамотно рассчитать фундамент и отверстие в крыше для трубы. Однако и печник, и инженер-строитель — это профессии строительные. Так и и программист, за этим словом скрываются десятки разных направлений. Опрос покажет только наличие людей тех или иных направлений, принявших участие в опросе.

В-четвёртых, сама постановка Ваших вопросов совершенно неверна. Спрашивать, может ли кто-то написать нечто почти не подглядывая — это не то же самое, что знать алгоритм. При работе в проектировании и кодировании библиотек нередко разработчик изобретает сам способ кодирования того или иного алгоритма, зачастую даже не зная алгоритма, а зная лишь идею. Одно из моих правил, которого я последнее время придерживаюсь — не смотреть коды или псевдокоды из литературы. Я читаю у кого-то об алгоритме (как правило, это научная статья), но только до момента, когда автор предлагает код (или псевдокод), сам код принципиально не смотрю. Затем додумываю алгоритм по-своему и пишу код свой собственный. Так нужно делать обязательно, потому что авторы научных статей — математики — зачастую (но не обязательно) — плохие программисты на практике. Где-то в 80% случаев написанный таким образом собственный код (без знания алгоритма, а со знанием только общей идеи) оказывается впоследствии красивее, короче и быстрее кода автора. Но есть и обратные примеры. Сейчас я занимаюсь учебным проектом по длинной арифметики и вижу, насколько хорошо она уже реализована в проектах вроде gmp и mpir. Поэтому идеи заимствую оттуда и сделать даже чуть-чуть лучше получается редко, если вообще получается. Чего не скажешь про stl, всё кроме бинарного поиска и сортировки можно написать эффективнее без особого труда.

То есть этим абзацем я хочу сказать, что знать алгоритм — это ни о чём не говорит. Нужно задавать вопрос конкретно: "можешь ли ты реализовать деление длинного числа на длинное число (пусть, для начала, будет тысяча десятичных знаков)?" или "есть массив из миллиона целых чисел от 1 до 10, можешь ли ты отсортировать его по неубыванию?" (горе тому, кто скажет хоть слово про qsort или mergeSort) или "рассчитай n-е число Фибоначчи в цикле, используя во всей программе лишь 3 переменных (одна из которых нужна для организации самого цикла)". Нужно спрашивать не о знании алгоритмов, а о понимании общей культуры программирования в том или ином направлении. Ещё аналогия. Можно знать (в теории), как пробежать 1000 метров за 3 минуты, а можно уметь это делать, но тогда неизбежно ты будешь уметь и 500 метров за 70 секунд, и 3 км за 10-11 минут и вообще будешь понимать общую биомеханику бега.

Надеюсь, мысль понятна. Знать алгоритмы — это всё равно что знать 1000 фактов, но не понимать, что они означают. Уметь программировать — это всё равно что уметь сопоставлять эти 1000 фактов с реальностью, согласованно друг с другом, пусть даже не обязательно хорошо зная все эти факты, а просто открывая их для себя по мере надобности из необходимости практики жизни.

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

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

Про мозг — вопрос сложный. Насколько помню видеолекции Анохина, все воспоминания остаются навсегда, теряется доступ к ним. И не факт, что это равносильно: не имея возможности вспомнить алгоритм, мы имеем определенный фундамент из всех изученных ранее алгоритмов. Может они натренировали мозг (т.е. дело не в памяти, а параметрах работы мозга), может "забытые" куски все-таки участвуют в решении задач, но польза от изученного ранее, я уверен, есть.

Про разделение аудитории — честно, не вижу смысла. И без опросов понятно, что всегда найдутся особы люди (о чем бы ни шла речь), которые постоянно используют в работе то, что иные лишь ненадолго впустили в свою память. Разработчики библиотек по-полной варятся во всех алгоритмах — это скорее исключения, далекие от общей картины (а ведь речь о ней). Упомянутые в заголовке статьи "современные разработчики" — это огромная толпа людей, использующих те самые библиотеки, и им алгоритмы на практике нужны довольно редко. Зачем знать 10 алгоритмов сортировки, когда можно вызвать стандартный std::sort? В ответ люди почему-то начинают приводить исключения, какие-то редкие кейсы, когда человеку почему-то понадобится написать свой велосипед. И вот это поражает, совершенно иррациональный подход в рациональной сфере.

Редкое происходит редко, частое — часто, большую часть усилий нужно отдать на то, что даст большую часть результата. Алгоритмы — гимнастика мозга, но к реальной разработке они все меньше относятся. Поэтому, неприятно на собеседованиях видеть, когда интервьюер (чаще, молодые ребята) просто светится от гордости, что он знает на память пять видов сбалансированных деревьев и до деталей алгоритм удаления из них (особенно Яндекс промышляет почитанием Скиены).

Зачем?
Знания ради знаний? Вклад этих знаний в результат (для большинства кейсов, повторюсь!) — минимален. Если для человека программирование — это удовольствие само по себе, человек наливается эндорфинами от решения сложных задач, желательно в неком сэндбоксе, оторванной от живых пользователей задачи — тогда да, 100+1 способов отсортировать массив способен доставить удовольствие. Если программирование для вас — не только приятная и увлекательная деятельность, но инструмент улучшения мира, способ дать людям нечто новое, то надо это просто сделать, быстро и качественно, используя насколько можно готовые библиотеки! Здесь важнее понимание архитектурных принципов, цикла разработки, построения удобного UI и пр. Это способность решить реальную задачу реального мира за ограниченное время, в процессе чего вероятность реализации давно известного алгоритма стремится к минимуму. Или же результаты опроса говорят об обратном?