О-нотация в проектировании программного обеспечивания

в 13:06, , рубрики: solid, Анализ и проектирование систем, Проектирование и рефакторинг

Разбираясь с SOLID, я части натыкался на то, что неследование этим принципам может приводить к проблемам. Проблемы известны, но плохо формализованы. Эта статья написана с целью формализовать типичные ситуации, возникающие в процессе написания кода возможные решений и вытекающие из этого последствия. Мы поговорим, чем нам грозит плохой код и как проблемы растут вместе с ростом программы. К сожалению, в большинстве случаев оценка сводится к вариантам “много” и “один”, что намекает на несостоятельность О-нотации, но даже такой анализ позволит лучше понимать какой код действительно является опасным для дальнейшего развития системы, а какой код — терпимым.

Определение

Будем говорить, что изменение в программе требует «О» от f(n) действий, если программисту требуется сделать не более f(n) логически обособленных изменений в программе для внедрения изменения с точностью до константного множителя, где под n подразумевается размер программы.

Метрики

Рассмотрим некоторые свойства дизайна по Роберту Мартину и оценим их с точки зрения О-нотации.

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

Существенной является разница О(1) и О(n) изменений. Т.е. допускает наш дизайн константное количество изменений или же по мере роста программы количество изменений будет расти. Далее следует рассмотреть сами изменения — они тоже могут оказаться жесткими с некоторой своей асимптотикой. Таким образом жесткость может иметь сложность вплоть до О(nm). Параметр m будем называть глубиной жесткости. Даже примерная оценка глубины жесткости в дизайне, который хотя бы допускает жесткость О(n) есть дело слишком сложное для человека, так как каждое из изменений надо проверить на еще более глубокие изменения.

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

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

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

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

Вязкость.

Сталкиваясь с необходимостью внести изменение, разработчик обычно находит несколько способов сделать это. Одни сохраняют дизайн, другие – нет (то есть являются, по существу, «хаком»). Если сохраняющие дизайн подходы оказывается реализовать труднее, чем «хак», то вязкость дизайна высока. Решить задачу неправильно легко, а правильно – трудно. Мы хотим проектировать наши программы так, чтобы легко было вносить изменения, сохраняющие дизайн.

Следование вязкости можно назвать недальновидностью с точки зрения О нотации. Да, сначала разработчик действительно имеет возможность внести изменение за О(1) вместо О(n) (из-за жесткости или хрупкости), но зачастую такие изменения приводят к еще большей жесткости и хрупкости, т.е. увеличивают глубину жесткости. Если проигнорировать такой «звоночек», то последующие изменения, возможно будет уже нельзя решить «хаком» и придется вносить изменения в условиях жесткости (возможно большей, чем до «звоночка») или приводить систему в хорошее состояние. То есть при обнаружении вязкости, лучше сразу переписать систему надлежащим образом.

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

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

В этой ситуации становится очевидно, что когда появляется необходимость изменить основу раскопированного действия, это изменение следует произвести в n местах. Учитывая возможность уникальных модификаций в каждом копипасте, это может вылиться еще и в логически несвязанные изменения. При этом есть вероятность просто забыть об изменении в другом месте, так как нет никакой защиты на этапе компиляции. А значит это может превратится еще и в O(n) итераций тестирования.

Применение О нотации к SOLID

SRP (Single Responsibility Principle). Программная сущность должна иметь только одну причину изменений (ответственность). Другими словами, например, класс не должен следить за бизнес логикой и отображением, т.к. при изменении одной ответственности мы должны убедиться в том, что не повредили другую ответственность. То есть несоответствие принципу SRP выливается в жесткость и хрупкость. Так же следование этому принципу помогает избавиться от косности и переносить модули из одной программы в другую с потенциально меньшим количеством зависимостей.

Асимптотика изменений остается в общем-то та же, что и без следования принципу, но существенно уменьшается константный множитель. В обоих случаях нам следует препроверить всё содержимое класса и, в случае изменения интерфейса сущности, места, где с этой сущностью взаимодействуют. Только следование SRP помогает сократить интерфейс и вероятность его изменения, а так же объем внутренней реализации, которая после изменения может оказаться неисправной. Так же аналогичные рассуждения, урезанные до рассуждения об интерфейсах справедливы для ISP (Interface Segregation Principle).

OCP (Open Close Principle). Программные сущности (классы, модули, функции и т.п.) должны быть открыты для расширения и закрыты для модификации. Это следует понимать так, что мы должны иметь возможность модифицировтаь поведение модуля, не затрагивая его исходный код. Как правило, это достигается с помощью наследования и полиморфизма. Так как нарушение принципа LSP является нарушением OCP, и при этом DIP является средством для поддержания OCP, то последующее можно применять и к LSP, и к DIP. Несоответствие принципу открытости-закрытости вынуждает внести изменения во всех незакрытых относительно данного изменения сущностях.

Достаточно тривиальной ситуацией бывает, например, наличие цепочки ифов, которые определяют тип переменной среди перечня дочерних классов. Такие структуры могут появляться в программе более одного раза. И при всяком добавлении нового дочернего класса, следует внести соответствующие изменения в каждой такой цепочке. Подобные ситуации могут появляться не только с дочерними классами, но и со всяким рассмотрением не всех возможных частных случаев [Имеется в виду случаев не в момент написания, а вообще. Случаи могут появиться позже].

Теперь рассмотрим ситуацию, когда мы вносим m изменений одного типа, которые из-за несоответствия принципу открытости-закрытости требуют от нас n операций. Тогда, если мы оставим все как есть, поддерживая архитектуру рассмотрения частных случаев, и не будем обобщать, то получим общую сложность для всех изменений O(mn). Если же мы закроем все m мест относительно данного изменения, то последующие изменения будут занимать у нас O(1) вместо O(m). Таким образом общая сложность сократится до O(m + n). Это значит, что начинать следование OCP никогда не поздно.

Мартин о подобной ситуации говорит, что не стоит угадывать (если вы не знаете точно, конечно) как закрываться от первого изменения, но после первого изменения стоит закрыться, так как первое изменение было маркером того, что система не обязательно останется в текущем состоянии. Это есть логично, так как мы делаем O(1*n) действий из-за незакрытости, а затем O(m) действий, чтоб закрыться от последующих изменений. Итого мы получаем общую сложность О(n + m), но при этом делаем все действия ровно тогда, когда они становятся необходимы и не делаем ничего наперед, не зная точно понадобится ли это.

Паттерны и О-нотация

Можно провести еще одну аналогию между О-нотацией в теории вычислений и О-нотацией в проектировании. Заключается она в том, что количество вычислений мы сокращаем с помощью алгоритмов и структур данных, вроде деревьев поиска и куч, которые решают типичные задачи быстрее “решений в лоб”, а количество операций программиста хорошим дизайном, в котором может использовать так же хорошие типичные решения, которые назвали шаблонами проектирования. Оценить действие паттернов можно в контексте принципов SOLID и, как следствие, в контексте О-нотации.

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

Шаблон Адаптер позволяет нам использовать (читай добавлять) сущности с разными интерфейсами, которые мы будем использовать с общей целью. С помощью этого шаблона можно внедрить новый объект с несовместным интерфейсом в систему за количество операций, не зависящее от размера системы.

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

Разумные пределы

Имея дело с О-нотацией, работая над оптимизационной задачей, надо помнить, что не всегда алгоритм с наилучшей асимптотикой лучше всего подходит для решения задачи. Надо понимать, что сортировка пузырьком для массива в 3 элемента будет работать быстрее пирамидальной, несмотря на то, что пирамидальная сортировка имеет лучшую асимптотику. При малых значениях n большую роль играет константный множитель, который О-нотация скрывает. Так же работает и О-нотация в проектировании. Для малых проектов нет смысла городить много шаблонов, так как издержки от их реализации превышают количество изменений которые следует внести от “плохого проектирования”.

Автор: SanQri

Источник


* - обязательные к заполнению поля