Задача 2 от брой 11/2003 - МОДУЛНА СТРУКТУРА - Анализ

Тази година Турнирът на БАСКОМ беше специален Коледен кръг от Конкурса на PC Magazine и Мусала Софт.  Желанието на колегите от БАСКОМ да има кръг от Конкурса под патронажа на асоциацията ни доведе до идеята да разширим кръга от задачи с такива от областта Software Engineering, с която всеки професионалист вече трябва да е запознат. На всички заинтересовани препоръчваме известната книга на Roger S. Pressman Software Engineering. A Practitioner’s Approach.

За Турнира избрахме тема от една от основните части на книгата на Pressman – Част Трета. Конвенционални методи - и по специално Глава 13. Основни понятия и принципи на проектирането. В тази глава се обсъждат фундаментални понятия за разработчика на софтуер, като Проектиране и качество на софтуера, Еволюция на софтуерния проект, Абстракция, Детайлизация, Модулност и т.н. Специален раздел (13.5.) е посветен на ефективното проектиране на модулната структура, където са дефинирани двете характеристики кохезия (cohesion) и обвързаност (coupling) и се подчертава ролята на баланса между тях при разработване на модулната структура на голяма програмна система. За съжаление, дори в книгата на Pressman не се посочват нито подходи за постигане на този баланс, нито някаква метрика с която да се измерва балансът. Това беше истинско предизвикателство за екипа и бе свързано с много проблеми. 

Основният проблем беше да се доведат текстуалните описания от книгата до формално поставена задача, да се дефинира понятието баланс така, че двете противоречащи си характеристики да бъдат отчетени в съответствие с текстовото им описание. Ясно е, че за да се подобри балансът на системата е необходимо да се определят някакви промени в модулната структурата, които да запазват важни нейни характеристики (в текста на задачата сме си позволили да употребим понятието “еквивалентни структури”). Почти очевидно е, че една еквивалентност силно би ограничила възможните изменения в модулната структура, с помощта на които можем да се опитаме да подобрим баланса и така задачата би се опростила много. Затова екипът предпочете да специфицира явно операции, които изменят структурата, но запазват съществуващите в структурата ориентирани пътища (и евентуално добавят нови). Ето защо същността на задачата може накратко да се опише така: използвайки двете разрешени операции да се подобри колкото може повече баланса на структурата.

При работата върху текста на задачата, от двете обсъждани дефиниции за теглото на обединена връзка (СУМА от теглата на двете стари връзки или МАКСИМУМ от теглата на тези две връзки) бе избрана – сума на теглата. Това може да се определи като съществен “дефект” на модела. Наистина, заради сумирането на теглата на обединяваните връзки, е възможно да се организира достатъчно дълга последователност от двете операции и в резултат да се получи връзка с произволно голямо тегло. Когато тази връзка се “обърне” във вътрешномодулна, с това практически се свежда до теоретичния минимум обвързаността на структурата. Фрагментите, които не са краища на получената “тежка” връзка се поставят в отделни модули и с това и кохезията се редуцира много близко до теоретичния минимум Такова нещо не може да стане, ако теглото на обединената връзка беше определено като максимум на теглата на обединяваните. Екипът ни съжалява за допуснатата неточност.

Споменатият дефект, обаче, не е глобален. Той не може да бъде прилаган в структури само с последователни модули, както и при наличието на връзки и в двете посоки между паралелен и някакъв друг модул. Затова участниците имаше с какво да се преборят.

Трудно е да си представим, че за такава задача може да бъде посочен някакъв “добър” алгоритъм. В подобни “грапави” задачи за оптимизация добър подход е локално-оптимизиращата (greedy) техника, известна като “изкачване на хълм” (hill climbing). Да си представим пространството от допустимите модулни структури като планинска местност, а зададената структура –  като точка в тази местност, в която се намира планинар (разработваната програма), целта на който е да се изкачи колкото може по-високо в планината. Мярката за височината, до която планинарът е достигнал, в нашия случай е балансът на структурата. Идеята на “изкачването” е да се опитат няколко неголеми “крачки” в различни посоки и да се избере тази от посоките, в която се постига най-голямо подобрение на достигнатата височина, след което да се опитат отново няколко посоки и т.н. Когато няма посока по която височината да нараства изкачването завършва, тъй като точката в която се намира планинарят е някакаъв (локален) максимум.   

В чисто геометрични пространства, за избягване на локалните маскимуми, се препоръчват няколко “скока” на по-голямо разстояние и повтаряне на процедурата. В нашия случай това не е лесно, защото нямаме свободата да “скочим” в произволна точка на пространството. За да се увеличат шансовете за постигане на по-добър баланс би било полезно да се запомнят места, в които е имало повече от една възможност за локална стъпка с подобрение на височината близко до максималното. След достигане на локален максимум може да се опитат няколко нови изкачвания от запомнените попътно перспективни места. Както се вижда от резултатите, такова подобрение като че ли не е опитвано от никой участник.

На това място бихме искали да отбележим, че в задачата има възможност и за друга локална оптимизация. Не е трудно да се види, че във верига от модули с последователна организация може да се реши локална за веригата оптимизационна задача, за която е приложим подходът “динамично оптимиране”. Надяваме се, че за нашите читатели не е проблем да си формулират съответната оптимизационна теорема.

Разбира се, не на последно място за добро решение на задачата от голямо значение е и представянето на данните в паметта. Много често в такъв род задачи, при които има голяма динамика, състезателите са склонни да изберат динамични имплементации на използваните структури от данни. От теоретична гледна точка това е оправдано. В състезателното програмиране, обаче, динамичните имплементации са по-скоро пречка отколкото предимство, тъй като многократното заделяне (и освобождаване) на памет могат да влошат значително времето за работа на програмата, а то е един от важните критерии при оценяването. При цялата динамика на тази задача тя притежава една статична характеристика – постоянния брой фрагменти – на която естествено е да се опре статична имплементация на структурите от данни. Още повече, че динамично изменящата се характеристика – броят на модулите – не може да надхвърли броя на фрагментите.

Ето и още един ресурс свързан с представянето на данните. Много правилно някои от участниците, вместо да престрояват модула участващ в split (или съответно модулите, участващи в join) обявяват този модул за “невалиден”  и записват резултата на ново място, като при нужда могат да използват паметта отделена за представяне на вече “невалиден” модул за записване на новополучени от операциите модули.

За бързината на решението е важно и да не се пресмята баланса от нула всеки път когато е необходим за работата на алгоритъма, а да се модифицира при всяка приложена операция. Така например всяко прилагане на операцията split увеличава броя на модулите с 1, а всяка операция join намалява с 1 този брой. Затова в първия случай кохезията се намалява от N/M до N/M+1, а във втория се увеличава от N/M до N/M-1. Малко по-сложно се пресмятат измененията в обвързаността, в зависимост от вида на разбиваните или обединявани модули, но и в този случай могат да се изведат достатъчно прости процедури за пресмятане на изменението в баланса и да се избегне неговото пълно пресмятане. 

По-долу е дадено част от описанието на алгоритъма на Орлин Колев.

“ ... Дефинираме три операции, които ще прилагаме върху структурата:

1.       Разбиване на всички последователни модули на такива с по един елемент.

2.       Обединяване на всеки два свързани последователни модула, ако това би подобрило баланса.

3.       Разбиване на всеки паралелен модул, ако това би подобрило баланса. Паралелният модул се разбива на един с големина 1 (той става последователен) и друг, в който са всички останали фрагменти.

Редът и броя на прилагане на операциите трябва да се определи експериментално. Една добра възможност е 1-2-3-2. Фактът, че параметрите на баланса се променят означава, че дори една операция върху модул да не е била рентабилна в един момент, тя може да стане такава след промяна на структурата.”

На практика Орлин Колев е реализирал “изкачване на хълм”, като за начална позиция избира структура, в която всички последователни модули са разбити на модули с по един фрагмент. При това алгоритъмът му си позволява понякога и да “слиза”, разчитайки на това, че някои влошавания на баланса не са фатални и по-късно водят до подобряването му. Би било интересно да се формулират по-точно условията, при които това се случва.

Ето и краткото обяснение на Владимир Недев за използвания от него алгоритъм (една по-чиста версия на “изкачване на хълм”, с малко повече опитвани стъпки, която видимо се задоволява с локални оптимуми):

“... Използвам greedy алгоритъм, който на всяка стъпка избира измежду няколко операции, в зависимост от това коя от тях най-много подобрява баланса. Ето и операциите:

1.       Разделяне на последователен модул.    

2.       Обединяване на последователни модули.

3.       Разделяне на праралелен модул на неутрален и паралелен.

4.       Операция 3 и обединяване на резултатния неутрален модул с някой последователен, от който има връзка към резултатния.

5.       Операция 3 и обединяване на резултатния неутрален модул с някой последователен, към който има връзка от резултатния.

6.       Операция 4 и операция 5.

Повтарям това докато никоя операция не води до подобрение на баланса.”

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.