close

Вход

Забыли?

вход по аккаунту

?

Лаб 5 Метрики Холстеда

код для вставкиСкачать
 Лабораторна робота №5.
Оцінювання якості розробки програм на основі метрик Холстеда.
1.Вимірювання властивостей алгоритмів 
Якщо задана реалізація алгоритму на деякій мові можна ідентифікувати всі операнди, визначені як змінні або константи, що використовуються в цій реалізації. Аналогічно можна ідентифікувати всі оператори, визначені як символи або комбінації символів, що впливають на значення або на порядок операндів. Виходячи з ідентифікації операторів і операндів, можна визначити ряд вимірних категорій, обов'язково присутніх у будь-якій версії будь-якого алгоритму. Вони визначаються метриками, за допомогою яких можуть бути отримані основні характеристики якості програм. До складу вимірних властивостей будь-якого подання алгоритму (або програми) можуть бути включені наступні метричні характеристики 
- число простих (унікальних) операторів, що з'являються в даній реалізації;
- число простих (унікальних) операндів, що з'являються в даній реалізації;
- загальне число всіх операторів, що з'являються в даній реалізації;
- загальне число всіх операндів, що з'являються в даній реалізації;
- число входжень j оператора, де j=1,2,3,...;
- число входжень j оператора, де j=1,2,3,...;
Відштовхуючись від цих основних метричних характеристик для програми, зручно визначити:
словник та довжину реалізації програми.
Відповідно до даних визначеннями повинні виконуватися наступні три співвідношення:
Розглянемо приклад обчислення введених метрик для програми, що реалізує широко відомий алгоритм Евкліда знаходження найбільшого загального дільника (НЗД) двох цілих чисел. Можливі варіанти програми на мовах Паскаль і С наведені в таблиці 1.
Таблиця 1
Програма на Паскалі
Програма на С
Function GCD (a,b: integer): integer;
Label L1, L2;
Var G, R : integer;
Begin
If (a=0) then
L1: begin GCD := b; return end;
If (b=0) then
Begin GCD := a; return end;
L2: G := a/b;
R := a - b*G;
If (R=0) GOTO L1;
a :=b; b:=R; GOTO L2;
End.
Int gcd ( int a, int b )
{ int G;
int R;
if (!a) return (b);
if(!b) return (a);
while(1)
{ G = a/b;
R = a - b*G;
If (R) { a = b; b = R; }
else return (b);
}
}
Результати підрахунку числа типів операторів і операндів і їх загальної кількості зведені в таблицю 2 для програми на Паскалі і в таблицю 3 для програми на С. При підрахунку використовувалися наступні міркування 
Щодо класифікації операторів інтуїтивно зрозуміло  що символи:
=знак присвоєння;
=знак рівності (або знак присвоювання у програмі на С);
--знак віднімання;
/ знак ділення;
*знак множення
відповідають їх звичайному визначенню.
Пара  що складається з дужок відкриванння і закривання ()  {} класифікується як один оператор групи  Оскільки пара слів  Begin  End виконує таку ж функцію групування, вона класифікується як такий же самий оператор  Мітки L1 і L2 - не змінні і не константи, тому вони не є операндами. Отже, вони повинні бути операторами або їх складовими частинами. Комбінація GO TO і мітки L1 визначає хід виконання програми шляхом задання для неї лічильника або вказівника коду; ця комбінація класифікується як один оператор. Мітка, що не використовується трактується всього лише як коментар, тому її присутність в програмі не обов'язкова. Обмежувач ; (крапка з комою) також визначає хід виконання програми (простим просуванням лічильника ), що дозволяє класифікувати точку з комою як оператор. По тій ж причині всі керуючі структури, наприклад IF, IF ... THEN ... ELSE, DO ... WHILE, класифікуються як оператори. Показник виклику функції або оператор процедури також є операторами. Крім того, можливість задання помічених ділянок та введення нових функцій усувають будь-які обмеження на зростання величини  1 (числа типів операторів)  які в іншому випадку могли б бути накладені набором команд машини або розробкою мови 
Оператор I F1i Операнд J F2j ; 1 14 GCD 1 2 := 2 6 G 2 2 = 3 3 R 3 3 () або begin end 4 6 A 4 5 If 5 3 B 5 6 / 6 1 0 6 3 * 7 1 - 8 1 GOTO L1 9 1 GOTO L2 10 1 Function GCD 11 1 Return 12 2 Таблиця 2
Відповідно, вимірні метрики програми на Паскалі будуть дорівнювати:
η1 = 12; N1 = 40; η2 = 6; N2 = 21; η = 18; N = N1 + N2 = 61; 58,53
Таблиця 3 Оператор I F1i Операнд J F2j ; 1 9 GCD 1 1 = 2 4 G 2 2 , 3 1 R 3 3 () або {} 4 11 A 4 5 If 5 3 B 5 6 / 6 1 1 6 1 * 7 1 - 8 1 ! 9 2 Int GCD 10 1 Return 11 3 Відповідно, вимірні метрики програми на С будуть рівні:
η1 = 11; N1 = 37; η2 = 6; N2 = 18; η = 17; N = N1 + N2 = 55; 53,56
Довжина програми
З використанням розглянутих програмних параметрів можна отримати рівняння для оцінки кількісного співвідношення між довжиною програми N і словником . Це рівняння на перший погляд може здатися дещо несподіваним. Однак ретельний аналіз доводить його правомірність крім того його правильність підтверджується експериментально.
Рядок N  що утворений символами, що входять до словника з  символів  повинен підкорятися ряду обмежень. Вимога за якою кожен символ словника повинен з'явитися щонайменше хоча б один раз, гарантує виконання умови
,
що визначає нижню границю для N визначену через . Знайдемо верхю границю для N. Розібємо рядок довжини N на підрядки довжиною . Поділена таким чином програма на ЕОМ складається з N/ операторів довжиною  кожен. Тепер якщо ми захочемо щоб рядок не містив двох однакових підрядків довжини  то з'явиться шукана верхня межа
Вимога відсутності дублікатів підрядків довжини  є досить обгрунтованою у програмах для ЕОМ в яких економія висловів призводить до того  що загальному подвираженій дається окреме ім'я тому його треба обчислювати тільки один раз. Отже якщо загальний підвираз довжиною  необхіден програмі більше одного разу присвоювання його окремому операнду збільшить  (число типів операторів) на одиницю
Число можливих комбінацій з  елементів взятих по , добре відоме з курсу матиматики і складає N  +1
Якщо врахувати, що оператори і операнди, як правило чергуються, то можна отримати інше співвідношення
N1122
Верхня межа для цієї нерівності повинна включати не тільки впорядковану множину з N елементів що представляють досліджувану програму  але і її будь-які підмножини Сімейство всіляких підмножин з N елементів містить 2N елементів. Отже  ми можемо прирівняти число можливих комбінацій з операторів і операндів (рівне числу підрядків N / ) числу підмножин з N елементів і виразити довжину реалізації алгоритму через його словник  З рівняння 2N = 1122
отримуємо
N = log2 (1122)
або N = log2 11 + log2 22
Це дає нам рівняння оцінки довжини 1 log21 + 2 log22(1.1)
У цьому виразі символ N забезпечили  для того  щоб відрізняти обчислену (теоретичну) оцінку довжини від значення N отриманого в результаті безпосереднього вимірювання (досліджуваної довжини) Ця оцінка відповідає основним концепціям теорії інформації, за якими частота використання операторів і операндів у програмі пропорційна двійковому логарифму кількості їх типів. Вираз (1.1) являє собою ідеалізовану апроксимацію виміряної довжини , справедливу для програм що не містять недосконалостей (стилістичних помилок). Експериментальні дослідження ряду авторів на представницькій групі програм показали, що для стилістично коректних програм відхилення в оцінці їхньої теоретичної довжини від дослідженої не перевищують (10-15)%.
Об'єм програми Важливою характеристикою програми є її розмір. При перекладі алгоритму з однієї мови на інший розмір програми буде змінюватися. Вивчення цих змін кількісними методами вимагає, щоб розмір був вимірною величиною.
Крім того, метрична характеристика розміру повинна бути застосовна до широкого кола мов без втрати спільності та об'єктивності отже, не повинна залежати від набору символів, необхідних для подання алгоритму, тобто символів, що використовуються для запису операторів або імен операндів.
Вирішення цієї проблеми пов'язано з тим, що можна визначити абсолютний мінімум довжини подання найдовшого оператора або імені операнда. Мінімальна довжина залежить тільки від числа елементів у словнику . У загальному випадку є мінімальна довжина (в бітах) всієї програми. Під бітом тут розуміється логічна одиниця інформації - символ, оператор, операнд - те, чим оперує програміст при створенні програми.
Відповідна метрична характеристика розміру будь-якої реалізації якогось алгоритму, що називається об'ємом V, може бути визначена як
(1.2)
де - довжина реалізації, а її словник.
Очевидно, що якщо даний алгоритм перекладається з однієї мови на іншу, то його обсяг змінюється. Наприклад, при перекладі алгоритму з Паскаля в машинний код будь-якої конкретної машини його об'єм збільшиться. З іншого боку, вираження алгоритму на більш розвиненій мові, ніж та, на якій він написаний початково, призведе до зменшення його об'єму. Остання можливість надзвичайно важлива і заслуговує спеціального розгляду.
Потенційний об'єм V*
Вираз алгоритму в найбільш стислій формі передбачає існування мови, в якій необхідна операція вже визначена або реалізована, можливо, у вигляді процедури або підпрограми. Для реалізації алгоритму в такій мові потрібні лише імена операндів для його аргументів і результатів.
Позначивши відповідні програмні параметри можливо найкоротшою або в найбільш стислій формі алгоритму зірочками, з рівняння (1.1) отримаємо, що мінімальний (або потенційний) обсяг дорівнює
V* = (N1* + N2*) log2(1* + 2*)(1.3)
Але у мінімальній формі ні оператори, ні операнди не вимагають повторень, тому
N1* = 1* ( N2* = 2*
що дає нам V* = (1* + 2*) log2(1* + 2*)
Крім того, відоме мінімально можливе число операторів для будь-якого алгоритму. Кожен алгоритм повинен включати один оператор для імені функції або процедури і один в якості символу привласнення або угруповання, тобто мінімальне значення .
Рівняння тепер набуде вигляду: V* = (2+ 2*) log2( 2+ 2*),(1.4)
де повинне являти собою число різних вхідних і вихідних параметрів.
З рівняння (1.4) випливає, що потенційний об'єм V * будь-якого алгоритму не повинен залежати від мови, якою він може бути виражений. Якщо  2 * розцінюється як число єдиних за змістом (ненадлишкових) операндів, то V * виявляється найбільш корисною мірою вмісту алгоритму.
Повернімося до прикладу програми для алгоритму Евкліда і визначимо його обсяг для програм на Паскалі і С.
Паскаль:V =N * log2  = 61* log2 18 = 254.4 бітів(
С:V =N * log2  = 55* log2 18 = 224.8 бітів(
Щоб знайти потенційний обсяг, нам потрібно підрахувати число необхідних вхідних і вихідних параметрів. В даному випадку це А, В і GCD, так що . Отже, потенційний об'єм:
V* = (2 +2*) log2( 2 + 2*) = (2+3) log2(2+3) = 11(6 бітів
Як вже згадувалося вище, при перекладі алгоритму з однієї мови на іншу його потенційний обсяг V * не змінюється, але дійсний обсяг V збільшується або зменшується в залежності від розвиненості розглянутих мов. Проте легко помітити, що не може бути гладкого переходу від виразу на потенційній мові, для якого V = V *, до будь-якої менш розвиненої мови, для якої VV *. Такий різкий перехід обумовлений тим, що для потенційної мови , в той час як для всіх інших мов застосовується рівняння довжини і >.
Документ
Категория
Рефераты
Просмотров
161
Размер файла
159 Кб
Теги
холстеда, метрика, лаб
1/--страниц
Пожаловаться на содержимое документа