«А как всё хорошо начиналось…», или О пользе O-нотации не только для анализа алгоритмов

Термин «О-большое», знакомый нам из курса матанализа, был введён Паулем Бахманом в конце XIX века для описания асимптотического поведения функций. В конце 1970-х Дональд Кнут придумал применять этот термин для оценки эффективности и ресурсоёмкости алгоритмов, благодаря чему с «О-большим» знакомо большинство программистов. Понимание асимптотики быстродействия и ресурсоёмкости даёт возможность выбрать наиболее подходящий метод решения задачи в зависимости от текущих потребностей. «Плохая» асимптотика позволяет сразу же отбросить неподходящий метод.

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

Например, в перечне достоинств того или иного продукта часто упоминают слово «масштабируемость», хотя вместо этого довольно расплывчатого термина можно было бы говорить о том, что асимптотика производительности или стоимости администрирования относительно числа пользователей системы / программных модулей / экземпляров, допустим, не хуже чем . Если это не так, то «масштабируемость» — не более чем красное словцо для маркетингового запудривания мозгов.

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

Рассмотрим три примера, которые, хотя и описывают внешне различные эффекты, при внимательном рассмотрении имеют много общего.

Пример 1, тривиальный

Каждый программист когда-то в начале своей карьеры сталкивался с тем, что программа, прекрасно, казалось бы, справлявшаяся со своей задачей на небольшом начальном наборе данных, начинала невероятно «тормозить», как только объёмы информации увеличивались. Беды ничто не предвещало: мы были уверены, что отладили все ошибки и тестовый набор из десятка записей учитывает все возможные варианты. Будущие пользователи тоже были удовлетворены: они всё проверили на начальном наборе данных, добились устранения своих замечаний и полагают, что программу можно применять в рабочей среде. Программу запускают, и случается катастрофа: пользоваться системой в реальных условиях нельзя, всё «повисло».

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

Пример 2

Руководителям проектов разработки известно, насколько может ухудшиться и запутаться общее положение вещей при введении в проект нового разработчика, если только ему не удаётся выдать «отделяемую», «изолированную» задачу. Закон, описанный в классической книге Ф. Брукса «Мифический человеко-месяц», гласит: «привлечение новых работников не сокращает, а удлиняет график работ по созданию программного продукта». У этого утверждения есть очень простое и математически точное объяснение.

Зависимость времени, необходимого на проект разработки, от числа задействованных исполнителей, Брукс устанавливает следующим образом: пусть — количество программистов, работающих над проектом. Общее количество работы складывается из трудозатрат на

1. неразделяемые задачи — время выполнения этих задач не зависит от числа сотрудников и всегда равно ;
2. разделяемые задачи — время на их выполнение уменьшается с ростом числа сотрудников и равно ;
3. обмен информацией — Брукс пишет буквально следующее: «Если все задачи должны быть отдельно скоординированы между собой, то затраты возрастают как ». Имеется в виду, что при наличии сотрудников количество трудозатрат, производимых на координацию «всех со всеми», пропорционально числу связей в полном графе (графе, в котором каждая пара вершин соединена):
   

   Т. к. эти трудозатраты распределяются между сотрудниками, их вклад во время выполнения имеет вид .

Итак, общее время выполнения проекта определяется кривой следующего вида:

имеющей такой график:

Затраты же в человеко-часах определяются формулой вида

Основная мысль Ф. Брукса заключется в следующем: увеличение числа разработчиков в команде приводит к сокращению сроков выполнения проекта лишь до некоторого предела, за которым наступает увеличение сроков. Применяя О-нотацию к полученным закономерностям, мы можем сказать, что в «Бруксовом» проекте с ростом числа исполнителей время выполнения растёт как , а стоимость проекта — и вовсе как .

Ценное знание для руководителя, от которого зависит принятие решения о подключении новых сотрудников к проекту с поджимающими сроками, не так ли?

Пример 3

Другой классический пример «дурно растущей» зависимости приводится во всех книгах по методологии Extreme Programming: это рост стоимости изменения в зависимости от стадии, на которой находится проект:

Объяснить такую зависимость снова несложно, если понять, что программный проект в своём развитии начинает напоминать полный граф, вершинами которого являются связанные с проектом артефакты: программные модули, требования, тесты, документация:

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

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

Выводы

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

В первом из примеров вопрос решается выбором алгоритма или структуры данных с подходящей асимптотикой.

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

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

Несколько слов о том, как этого добиться на практике. Пользуясь общим принципом, оптимизировать проект следует во всех аспектах: от программной архитектуры до организации труда работающих на проекте специалистов.

На уровне проектирования приложения мы можем воспользоваться «звездообразностью» архитектуры «платформа — надстройки» или «платформа — плагины». В этой архитектуре имеется некоторая базовая часть, «ядро» или «платформа» приложения, разработанное со всей возможной тщательностью и редко подвергающееся изменениям. Все функции приложения разрабатываются в виде независимых «плагинов», использующих сервисы ядра и взаимодействующих друг с другом только с помощью ядра. Само ядро при этом от надстроек не зависит. В объекто-ориентированных средах разработки возможна очень удобная программная реализация этого принципа при помощи паттерна «источник-подписчик» и особенно при помощи паттерна проектирования «посредник», он же «медиатор».

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

Эффект, описанный Бруксом, также следует уменьшать налаживанием коммуникаций в проекте (уменьшением «квадратичной» части трудозатрат): общие собрания-«планёрки», общие email-рассылки с максимумом информации о происходящем для всех участников создают возможность каждому из рядовых участников взаимодействовать со всеми через «центральную вершину», не тратя тем самым время на поиск нужного адресата. Менеджерам проектов известно, что проблема коммуникации — проблема вовсе не только гигантских проектов, она начинает возникать даже между четырьмя участниками, а уж с их ростом может достигать поистине космических масштабов.

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

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

Автор: IvanPonomarev

Источник