«А як все добре починалося...», або Про користь O-нотації не тільки для аналізу алгоритмів

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



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



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

З іншого боку, про інший проект кажуть, що він «розвалюється під власною вагою». Цей проект міг цілком непогано починатися, але архітектурно був збудований так, що його згубила погана асимптотика вартості внесення змін.

Розглянемо три приклади, які, хоча і описують зовні різні ефекти, при уважному розгляді мають багато спільного.

Приклад 1, тривіальний
Кожен програміст коли на початку своєї кар'єри стикався з тим, що програма, чудово, здавалося б, справлявшаяся зі своїм завданням на невеликому початковому наборі даних, починала неймовірно «гальмувати», як тільки обсяги інформації збільшувалися. Біди ніщо не віщувало: ми були впевнені, що налагодили всі помилки і тестовий набір з десятка записів враховує всі можливі варіанти. Майбутні користувачі теж були задоволені: вони все перевірили на початковому наборі даних, домоглися усунення своїх зауважень і вважають, що програму можна застосовувати в робочому середовищі. Програму запускають, і трапляється катастрофа: користуватися системою в реальних умовах не можна, все «зависло».

Вся справа, звичайно, в неоптимально обраному алгоритмі або структурі даних. Невинно виглядає вкладений цикл, виклик зручного методу, швидко працював на невеликій кількості елементів (який-небудь додавання елементів по одному в динамічний масив) — і ми маємо систему, що дає -зростання часу роботи від числа елементів. Щоб подібне не траплялося надалі, достатньо трохи особистого досвіду і освоєння якогось підручника по алгоритмам і структурам даних. На цьому прикладі ми не будемо зупинятися.

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

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

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



    Оскільки ці роботи розподіляються між співробітниками, їх внесок під час виконання має вигляд .
Отже, загальний час виконання проекту визначається кривий наступного виду:



має такий графік:



Витрати в людино-годинах визначаються формулою виду



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

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

Приклад 3
Інший класичний приклад «погано зростаючої залежності наводиться в усіх книжках методології Extreme Programming: це зростання вартості зміни в залежності від стадії, на якій знаходиться проект:



Пояснити таку залежність знову нескладно, якщо зрозуміти, що програмний проект у своєму розвитку починає нагадувати повний граф, вершинами якого є пов'язані з проектом артефакти: програмні модулі, вимоги, тести, документація:



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

В результаті такої діяльності в якийсь момент розвиток проекту «застряє», весь час починає йти на латання старих проблем, нові зміни вносяться неприпустимо повільно і з колосальними труднощами, програмісти твердять, що «все це слід переписати», іншими словами — проект розвалюється під власною вагою.

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

У першому з прикладів питання вирішується вибором алгоритму або структури даних з відповідною асимптотикой.

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



Вибудувавши зв'язку в системі «зіркоподібно», або лінійно, або будь-яким іншим способом, що породжує ребер при вершинах, ми отримуємо систему, яка поводиться якісно іншим способом при своєму зростанні: вартість додавання нової вершини у такій системі завжди постійна.

Кілька слів про те, як цього домогтися на практиці. Користуючись загальним принципом, оптимізувати проект слід в усіх аспектах: від програмної архітектури до організації праці працюючих на проекті фахівців.

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

З урахуванням вищесказаного вже ясно, що деякі початкові накладні витрати на програмування такої архітектури окупаються надалі економією на взаємодію між розробниками надбудов і узгодження компонентів один з одним. Завдання починають ставати відокремлюваними самі собою, підключення нових розробників до проекту стає простим і безпечним.

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

Методика Extreme Programming пропонує цілий комплекс заходів для того, щоб домогтися -асимптотики зростання вартості зміни. Крім важливості налагодження комунікацій (у тому числі, такими радикальними заходами, як парне програмування), особлива увага приділяється розробці через тестування. У цій ситуації в проекті утворюються жорсткі і ізольовані один від одного зв'язки «функціональне вимога — тест — код», не приводять до виникнення зайвих зв'язків і залежностей «всіх від усіх». Ідеальна, з точки зору Extreme Programming, залежність вартості зміни від етапу проекту, виглядає наступним чином:



Як вже говорилося, викладена у статті ідея лежить на поверхні. Якщо ми, розробники, вміємо оцінювати поведінку алгоритму при ускладненні завдання, то чому б схожим чином не почати прогнозувати поведінку параметрів проекту розробки в процесі його росту і розвитку? Якщо ми вміємо оптимізувати алгоритми, позбавляючись від непотрібних циклів і обчислень, то чому б схожим чином не оптимізувати весь проект розробки, видаляючи з нього непотрібні зв'язки і залежності?

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.