Прочитал весь текст и комментарии. Много полезных советов и пищи для ума, но в целом текст отдает эгоцентризмом, циничностью, разделением мира на «черное» и «белое». Фразы вроде «второсортные ребята», «звуко-поглотители», «ничего не достигли», «остались отбросы» — это всегда однобокий и неверный взгляд. Не все готовы уходить с работы ночью и приходить на выходных — не от того, что нет силы воли, — а потому, что осознают важность баланса вещей вроде работы, cемьи, развлечений, общения, ЗОЖ или хобби. У каждого он — свой, соответствующий субъективным взглядам на жизнь и жизненные ценности. Очевидно, Хэминга в людях интересовали только научные амбиции и взгляды — история с «химиками» это подтверждает. Еще один тезис — «они не достигли величия, ибо решали неважные задачи». Опять он про «величие»… А что, если эти задачи были им интересны? P.S.: Не отрицаю тот факт, что лекция полезная и хорошая, но это уже и так многократно отметили.
Если они и устаревшие — то не более, чем на 5 недель. Справедливо, как минимум, для офиса в Цюрихе — лично проверял :) Может не везде ввели еще новую практику. Но не согласен с вами — печатать код в редакторе, по сравнению с писанием на доске — большой шаг вперед. Пару программ занимали целую доску, и все они были в стиле данного топика.
На онсайт-собеседованиях в Гугл весь код пишется маркером на доске. А бедный интервьювер его следом переписывает как раз на бумажку — для отчетности :-)
На практике классические алгоритмы CS вообще редко применяются :) Это, конечно, провокационное утверждение, но у любой прикладной задачи, как правило, присутствует более простое, быстрое и менее универсальное решение, которое отлично подходит для нужд потребителя.
КМП относится к фундаментальным (вероятно, в отличие от Хорспулла) строковым алгоритмам, самым что ни на есть классическим. Со всеми вытекающими последствиями, например, для собеседований в некоторые компании :) Его `сила` состоит не в скорости исполнения, а в довольно простой реализации и доказательстве важной концепции: поиск подстрок может быть осуществлен за O(n) универсально, без использование `читов` вроде хэширования, предположений о размере алфавита, свойствах строки и т.д.
Если кому-то интересно копнуть поглубже — используемая в КМП префикс-функция может быть основой для более сложных строковых алгоритмов и подходов. Подробнее можно почитать, например, здесь.
Спасибо за статью. Было приятно прочесть ваши размышления, даже вне контекста ФП. Я полностью разделяю мнение, что программирование — это, в первую очередь, решение задачь. Тренды имеют значение, но они вторичны. А хорошего программиста, имхо, отличает вовсе не знание N->max модных технологий, а рациональное мышление, умение видеть абстракции, опыт, «крепкий фундамент» и здравый смысл.
Т.к. классический алгоритм, для которого справедливы указанные оценки, выглядит чуть иначе — приходится говорить о «ваших вставках» как о реализации, приведенной вами :-)
К сожалению, ночью я просмотрел, что ваш алгоритм «вставками» не выполняет break, находя позицию очередного элемента в отсортированном подмассиве. И делает это, соответственно, операциями полного, а не половинного обмена. В этом виде к нему применима та же оценка, что и для «пузырька». Единственная разница — полная упорядоченность данных, на которых работает 1й алгоритм, и почти полное ее отсутствие — во втором случае. Видимо, вы правы касательно оптимизаций. К слову, на моем процессоре (AMD Turion X2 1.6 mobile) первоначальный выигрыш ваших «вставок» по времени не превышал 30%, а после отключения оптимизаций компиллятора (/Od) — сократился до 15% (msvc).
Ребята, вы упустили важную деталь. Производительность кешей, оптимизации процессора, аппаратные уловки — это все хорошо. Однако, сравнительный анализ тем полезнее, чем более эквивалентны сравниваемые сущности. А данном случае, это — далеко не так!
Несмотря на внешние сходства и общую ассимптотику O(N2), «вставки» и «пузырек» — суть разные подходы. Для ознакомления могу отправить к матчасти (например, Р. Седжвик, «Фундаментальные алгоритмы на С++ [1-4]», часть 3: «Сортировка», стр. 264 :)). А вкратце — «пузырек» ведет себя, скорее, как сортировка «выбором», нежели «вставками». Но с меньшей эффективностью. Впрочем, производительность даже продуманных модификаций «пузырька» (например, Шейкер-сортировки) оставляет желать лучшего. Но в случае «вставок» — все наоборот. Это — очень мощный алгоритм, к которому часто прибегают (привет усомнившимся в применимости квадратичых методов!) для упорядочивания малых или почти отсортированных (с малым количеством инверсий) массивов. Естественно, при этом обычно добляют пару символов и улучшают его быстродействие еще в 1.5 раза.
Напоследок, приведу несколько лемм без доказательства:
1. «Вставки» производит около N2/4 сравнений и обменов в среднем случае, и около N2/2 — в худшем (это — редко).
2. «Пузырек» — около N2/2 операций сравнения и обмена как в среднем, так и в худшем случаях.
Вывод: прежде аппаратных оптимизаций, имеет смысл подумать о программных (алгоритмических). В случае анализа кода — все аналогично. Не смотря на это, автор — молодец :-) Интересный материал.
КМП относится к фундаментальным (вероятно, в отличие от Хорспулла) строковым алгоритмам, самым что ни на есть классическим. Со всеми вытекающими последствиями, например, для собеседований в некоторые компании :) Его `сила` состоит не в скорости исполнения, а в довольно простой реализации и доказательстве важной концепции: поиск подстрок может быть осуществлен за O(n) универсально, без использование `читов` вроде хэширования, предположений о размере алфавита, свойствах строки и т.д.
Если кому-то интересно копнуть поглубже — используемая в КМП префикс-функция может быть основой для более сложных строковых алгоритмов и подходов. Подробнее можно почитать, например, здесь.
Несмотря на внешние сходства и общую ассимптотику O(N2), «вставки» и «пузырек» — суть разные подходы. Для ознакомления могу отправить к матчасти (например, Р. Седжвик, «Фундаментальные алгоритмы на С++ [1-4]», часть 3: «Сортировка», стр. 264 :)). А вкратце — «пузырек» ведет себя, скорее, как сортировка «выбором», нежели «вставками». Но с меньшей эффективностью. Впрочем, производительность даже продуманных модификаций «пузырька» (например, Шейкер-сортировки) оставляет желать лучшего. Но в случае «вставок» — все наоборот. Это — очень мощный алгоритм, к которому часто прибегают (привет усомнившимся в применимости квадратичых методов!) для упорядочивания малых или почти отсортированных (с малым количеством инверсий) массивов. Естественно, при этом обычно добляют пару символов и улучшают его быстродействие еще в 1.5 раза.
Напоследок, приведу несколько лемм без доказательства:
1. «Вставки» производит около N2/4 сравнений и обменов в среднем случае, и около N2/2 — в худшем (это — редко).
2. «Пузырек» — около N2/2 операций сравнения и обмена как в среднем, так и в худшем случаях.
Вывод: прежде аппаратных оптимизаций, имеет смысл подумать о программных (алгоритмических). В случае анализа кода — все аналогично. Не смотря на это, автор — молодец :-) Интересный материал.