Рубрика «разделяй и властвуй»

Профессор Никлаус Вирт был прав. Создатель языка Pascal, соавтор технологии структурного программирования, лауреат премии Тьюринга в 1995 году заметил:

«Замедление программ происходит куда быстрее, чем ускорение компьютеров»

С тех пор это высказывание считается законом Вирта. Он фактически нивелирует закон Мура, согласно которому количество транзисторов в процессорах удваивается примерно с 1965 года. Вот что пишет Вирт в статье «Призыв к стройному софту»:

«Около 25 лет назад интерактивный текстовый редактор умещался всего в 8000 байт, а компилятор в 32 килобайта, тогда как их современные потомки требуют мегабайтов. Стало ли всё это раздутое программное обеспечение быстрее? Нет, совсем наоборот. Если бы не в тысячу раз более быстрое железо, то современное программное обеспечение было бы совершенно непригодным».

С этим трудно не согласиться.
Читать полностью »

Программист-защитник сильнее энтропии - 1

© Dragon Ball. Goku.

Программист-защитник в любой момент и в любом месте кода ожидает появления потенциальных проблем и пишет код таким образом, чтобы заранее от них защититься. А если от проблемы нельзя защититься, то хотя бы сделать так, чтобы её последствия и влияние на пользователей были минимальными.

Вспоминается эффект FlashForward из голливудских блокбастеров, когда главный герой видит грядущую катастрофу и остаётся предельно спокойным, потому что заранее знает, что она произойдёт, и имеет от неё защиту. Идея защитного программирования в том, чтобы защититься от проблем, которые сложно или вовсе невозможно предвидеть. Программист-защитник ожидает появления ошибок в любом месте системы и в любой момент времени, чтобы предотвратить их до того, как они нанесут ущерб. При этом цель не в том, чтобы создать систему, которая никогда не падает, это всё равно невозможно. Цель в том, чтобы создать систему, которая падает изящно в случае любой непредвиденной проблемы.

Давайте разберёмся подробнее, что входит в понятие «падать изящно».

  • Падать быстро. В случае непредвиденной ошибки все операции должны завершаться сразу же, особенно если последующие вычисления тяжёлые или могут привести к порче данных.
  • Падать аккуратно. Если возникла ошибка, программа должна освободить все ресурсы, снять локи, удалить временные и наполовину записанные файлы, закрыть соединения. Дождаться завершения критических операций, прерывание которых может привести к непредсказуемым результатам. Либо безопасным способом аварийно завершить эти операции.
  • Падать явно и красиво. Если что-то сломалось, сообщение об ошибке должно быть простым, лаконичным и содержать важные детали из того контекста системы, где возникла ошибка. Это поможет команде, которая отвечает за систему, максимально быстро разобраться в проблеме и исправить её.

Читать полностью »

В этой статье рассматриваются сходства и различия двух подходов к решению алгоритмических задач: динамического программирования (dynamic programing) и принципа «разделяй и властвуй» (divide and conquer). Сравнение будем производить на примере, соответственно, двух алгоритмов: бинарного поиска (как быстро найти число в отсортированном массиве) и расстояния Левенштейна (как преобразовать одну строку в другую с минимальным количеством операций).

Хочу сразу заметить, что данное сравнение и объяснение не претендует на исключительную правильность. И возможно даже некоторые преподаватели в университетах захотели бы меня отчислить :) Эта статья является всего-лишь моей персональной попыткой разложить себе же все по полочками и понять что такое динамическое программирование и каким образом в нем участвует принцип «divide and conquer».

Итак, приступим…

image
Читать полностью »

Почему так важно запретить самому себе отладку руками?

Когда вы отлаживаете программу, то вы, сами того не осознавая, думаете что за один отладочный сеанс исправите все проблемы, возникшие в рамках этой задачи. Но наша недальновидность не хочет верить в то, что на самом деле там не одна проблема, а несколько. И за один отладочный сеанс не получится решить все эти проблемы.

Поэтому вам надо будет несколько раз запускать этот код в отладочном режиме, проводя часы отладки над одним и тем же куском кода. И это только вы один столько времени потратили над этой частью программы. Каждый член команды, кому «посчастливится» работать с этим кодом, будет вынужден прожить ту же самую историю, которую прожили вы.

Я уже не говорю о том, что люди в командах меняются, команды меняются и так далее. Человеко-часы уходят на одно и то же. Перестаньте делать это. Я серьёзно. Возьмите ответственность за других людей на себя. Помогите им не переживать тот же самый участок вашей жизни.
Читать полностью »

image

Недавно, на хабрахабре была опубликована статья, целиком и полностью посвященная диаграммам Вороного. В статье автор подробно описывает алгоритм Форчуна, применяемый для построения Диаграммы Вороного за O(n*log(n)). Стоит отметить, что описание этого алгоритма ни раз появлялось в рунете, в то время как о других алгоритмах (с той же асимптотикой) рассказано ровным счетом ничего. Данная статья исправляет это недоразумение, а также является отличным дополнением к уже опубликованному ранее материалу.

Ниже я расскажу о алгоритме 'разделяй и властвуй' построения диаграммы Вороного за O(n*log(n)), а также, основываясь на своем практическом опыте, о по-настоящему крутых штуках, в которых это применимо. Вообще, алгоритмы типа 'разделяй и властвуй' являются своего рода классикой программирования (думаю, про сортировку данным методом слышал каждый программист), хорошо параллелятся и легко читаются (если, конечно, знать основную идею алгоритма).
Читать полностью »

image
Здесь уже написано множество статей о том, кто такой Fullstack, в чем его плюсы и минусы, в каких проектах есть смысл нанимать таких разработчиков, а где — нет. Я буду исходить из мысли, что Вы понимаете, что такое Fullstack и с чем его едят.

Мысль, которую я хотел бы выразить заключается в следующем — «Почему, даже большие аутсорсинговые и продуктовые компании, хотят нанимать Fullstack и/или развивать своих сотрудников в этом направлении?».
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js