Компьютерный Дом
о фирме прайс в Exel формате статьи услуги контакты
аудиокниги
Статьи :: тестирование производительности
 
Часть 2.
Задача о Ханойских башнях

Эта интересная задача была сформулирована в 1883 году математиком Э.Люка. Многие учебные пособия по программированию используют ее как классический пример рекурсивного алгоритма. Суть задачи состоит в следующем. Где-то далеко в окрестностях города Ханой стоят три башни. Одна из башен состоит из 64 дисков, положенных друг на друга - как кольца в детской пирамиде. Диаметры всех дисков различны и уменьшаются от нижнего к верхнему. Необходимо перенести все диски с одной башни на другую. При этом диски можно переносить только по одному с любой башни на другую. Ставить диск на землю или надевать больший на меньший нельзя.

Рекурсивность алгоритма решения задачи заметить очень легко. Пусть наши башни будут обозначены буквами A, B, C. Диски, надетые на башню A, следует перенести на башню C. Для упрощения будем рассматривать 3 ситуации - когда башня А состоит из 1, 2 и 3 дисков. Тогда алгоритмы решения будут следующими:

 

1 ДИСК

2 ДИСКА

3 ДИСКА

A -> C

A -> B

A -> C

 

A -> C

A -> B

 

B -> C

C -> B

 

 

A -> C

 

 

B -> A

 

 

B -> C

 

 

A -> C

Для одного диска операция сводится к переносу этого диска с башни А на башню С. Для двух дисков мы переносим сначала диск с А на В, потом с А на(как в предыдущем случае!), потом с В на С. Для трех дисков предварительно выполняется процедура переноса двух дисков с А на В (А->C,A->B,C->B), потом с А на С и, наконец, перенос двух дисков с В на С (В->A,B->C,A->C). Нетрудно заметить, что для переноса башни из n дисков алгоритм решения имеет следующий вид: сначала башня из (n-1) дисков в верхней части переносится на рабочую башню (B). Потом один нижний диск переносится на башню C. И, наконец, башня из (n-1) дисков переносится с башни B на башню C.

Сортировка одномерного массива

Яркий пример рекурсии - это алгоритм сортировки данных, разработанный К.Хоором и известный под названием метода быстрой сортировки. По своему быстродействию метод существенно превосходит все остальные. Суть алгоритма для сортировки элементов одномерного массива чисел по не убыванию (возрастанию) их значений можно определить следующим образом:

  • Пусть x - элемент, расположенный в середине массива. Будем просматривать массив слева направо до тех пор, пока не обнаружим элемент a[i], для которого a[i] > x. Аналогично, просматривая массив, справа налево, ищем элемент a[j], для которого a[j] < x
  • Меняем элементы a[i] и a[j] местами. Продолжаем процесс просмотра массива до его середины
  • Таким образом, массив будет разбит на две части, в одной из которых будут собраны элементы большие, чем x, а в другой - меньшие, чем x
  • Процесс, описанный в пунктах 1-3, следует повторить для каждой из получаемых таким образом частей. Когда размеры частей станут равными одному элементу, массив будет содержать упорядоченную последовательность

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

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

2.2.2. Описание функции Аккермана

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

Существует несколько способов задания функции Аккермана: например, они могут различаться количеством параметров. Ниже приведена функция Аккермана от двух и трех параметров.

 

 

 

  • функция Аккермана (А) от трех параметров, индуктивно задается на трех неотрицательных целых числах и выглядит следующим образом :

| X+1, если N=0

| X, если N=1, Y=0,

| 0, если N=2, Y=0,

A(N,X,Y)= | 1, если N=3, Y=0,

| 2, если N=>4, Y=0,

| A(N-1,A(N,X,Y-1),X), если N#0, Y#0;

где N,X,Y - целые неотрицательные числа

  • функция Аккермана (А) от двух параметров, индуктивно задается на паре неотрицательных целых числах [9]:

Значение этой функции очень быстро возрастает по мере увеличения первого из ее параметров(“ m”). Рассмотрим функцию Аккермана первого порядка A(1, n): зафиксируем первый параметр и будем постепенно увеличивать второй.

A(1,0)=A(0,1)=1+1=2

A(1,1)=A(0,A(1,0))=1+A(1,0)=1+2=3

A(1,2)=A(0,A(1,1))=1+A(1,1)=1+1+A(1,0)=2+2=4

A(1,3)= A(0, A(1,2))=1+ A(1,2)=1+1+ A(1,1)=1+1+1+ A(1,0)=3+2=5

A (1, n )= n +2

Наблюдается линейная зависимость между значением функции и параметром “ n”. Аналогично рассмотрим функцию Аккермана второго порядка:

A(2,0)= A(1,1)=1+2=3

A(2,1)= A(1, A(2,0))= A(0, A(1,( A(2,0)-1)))=2+3=5

A(2,2)=A(1,A(2,1))=A(1,5)=A(0,A(1,4))=A(0,A(0,A(1,3)))=…=1+1+1+1+3=4+3=7

A(2,n)=2*n+3

Таким образом, были получены формулы для вычисления функции Аккермана со степенью m=2,3,4.

Анализируя полученные выражения, делаем вывод, что функция Аккермана уже третей степени обладает степенной зависимостью от параметра « m», а для четвертой степени – характер зависимости многостепенной. На рисунке 2.1. наглядно продемонстрирован рост функции Аккермана при возрастании ее параметров.

 

 


 

 


Рис. 2.3. Зависимость значения функции Аккермана от параметра “ n”

 

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

2.2.3. Разработка алгоритма программы

Для построения алгоритма программы используем сведения, изложенные в разделе 1 о рекурсивных функциях, а также описание свойств функции Аккермана из предыдущего параграфа.

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

main() /* вызывающая функция */

{... Akk()...}

Akk() /* рекурсивная функция */

{ ... Akk()...}

Рекурсивная функция Akk имеет параметры Р1,Р2,...,Рs, внутренние переменные V1,V2,...,Vt и в функциях main и Akk имеется k обращений к функции Akk. Для реализации такой функции требуются следующие дополнительные объекты:

  • переменные AR1,AR2,...,ARs, содержащие значения фактических параметров при вызове функции Akk (типы переменных должны соответствовать типам параметров Р1,Р2,...,Рs);
  • переменная rz для вычисляемого функцией Akk результата (тип переменных совпадает с типом возвращаемого значения функции Akk);
  • стек, содержащий в себе все параметры и все внутренние переменные функции Akk, а также переменную lr типа int, для хранения точки возврата, и переменную pst типа указатель, для хранения адреса предыдущего элемента стека;
  • указатель dl для хранения адреса вершин стека;
  • промежуточный указатель u для операций над стеком;
  • k новых меток L1,...,Lk для обозначенных точек возврата;
  • промежуточная переменная l типа int для передачи номера точки возврата.

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

В результате получим следующий набор действий, выполняемый программой:

1) считывание исходных данных;

2) выбор теста;

3) выполнение выбранного теста;

4) вывод результатов тестирования на экран;

5) запись результатов в файл

Полученная обобщенная схема алгоритма программы изображена на рисунке 2.4.

 

 


 

Рис. 2.4. Общая схема алгоритма процесса тестирования

Основная логика программы, реализующая вычисление функции Аккермана, будет включена в функцию Akkerman. Алгоритм функции Akkerman представлен на рисунке 2.5.

 


Рис. 2.5. Процедура вычисления функции Аккермана

В алгоритм введено понятие «объект» и анализ полей «объекта». Объект представляет собой структуру со следующими полями:

  • Am – хранит первый параметр функции Аккермана
  • An – хранит второй параметр функции Аккермана
  • Rz – в эту переменную записывается результат вычислению данной функции
  • L – уровень текущей функции, подробно это поле будет описано ниже
  • Указатель на такую же структуру – это поле необходимо для включения вновь созданного объекта в стек

Таким образом, каждый объект представляет собой функцию Аккермана со своими параметрами. При рекурсивном вызове функции, создается новый объект и помещается в начало стека. Каждому, вновь созданному, объекту присваивается определенный уровень “ L”: L=1 – означает, что данная функция Аккермана последняя в стеке и вычисление закончено; L=2 – означает, что данная функция порождает новую функцию Аккермана со следующими параметрами: А( am, an-1); L=3 – означает, что надо вызывать новую функцию Аккермана с параметрами A( am-1, rz), где rz – это результат вычисления функции Аккермана на предыдущем шаге.

2.3. Реализация программного продукта

2.3.1. Выбор технологии программирования

Система C++ Builder производства корпорации Borland предназначена для операционных систем Windows 95 и NT. Интегрированная среда C++ Builder обеспечивает скорость визуальной разработки, продуктивность повторно используемых компонент в сочетании с мощью языковых средств C++, усовершенствованными инструментами и разномасштабными средствами доступа к базам данных.

К несомненным достоинствам C++ Builder можно отнести следующие особенности:

1)Интегрированная среда разработки объединяет Редактор форм, Инспектор объектов, Палитру компонент, Администратор проекта и полностью интегрированные Редактор кода и Отладчик - инструменты быстрой разработки программных приложений, обеспечивающие полный контроль над кодом и ресурсами.

2)Профессиональные средства языка C++ интегрированы в визуальную среду разработки. C++Builder предоставляет быстродействующий компилятор с языка Borland C++, эффективный инкрементальный загрузчик и гибкие средства отладки как на уровне исходных инструкций, так и на уровне ассемблерных команд - в расчете удовлетворить высокие требования программистов-профессионалов.

3) Конструирование по способу "drag-and-drop " позволяет создавать приложение простым перетаскиванием захваченных мышью визуальных компонент из Палитры на форму приложения. Инспектор объектов предоставляет возможность оперировать со свойствами и событиями компонент, автоматически создавая заготовки функций обработки событий, которые наполняются кодом и редактируются в процессе разработки.

4)Механизмы двунаправленной разработки (two-way-tools) устраняют барьеры между программистом и его кодом. Технология двунаправленной разработки обеспечивает контроль над кодом посредством гибкого, интегрированного и синхронизированного взаимодействия между инструментами визуального проектирования и Редактором кода.

5)Мастер инсталляции руководит созданием унифицированных дистрибутивных пакетов для разработанных приложений.

6)Исходные тексты Библиотеки Визуальных Компонент облегчают разработку новых компонент на базе готовых примеров.

7)Отрытые инструменты API могут быть непосредственно интегрированы в визуальную среду системы. Есть возможность подключения привычного текстового редактора или создания собственного мастера для автоматизации выполнения повторяющихся процедур[11].

Помимо этих и многих других достоинств самой системы разработки C++ Builder можно упомянуть и некоторые удобства самого языка C++, перечисленные в [11]:

1)Оптимизирующий 32-разрядный компилятор построен по компиляторной технологии корпорации Borland, обеспечивающей исключительно падежную и быструю оптимизацию как длины выходного исполняемого кода, так и расходуемой памяти.

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

3)Создание DLL, LIB, и ЕХЕ файлов предоставляет свободу выбора формата целевого приложения в соответствии с требованиями конкретного проекта.

4)Прямое обращение к системным функциям Windows 95 и NT дает возможность программистам, работающим в среде C++Builder, при необходимости воспользоваться всеми усовершенствованиями современных операционных систем.

5)Поддержка промышленных стандартов ActiveX, OLE, СОМ, MAPI, Windows Sockets TCP/IP, ISAPI. NSAPI, ODBC, Unicode и MBCS.

Все приведенные выше достоинства среды C++ Builder говорят в пользу его использования при написании пакета тестирующих программ.

2.3.2. Общие принципы реализации приложения

Вся программа включает в себя два файла программного кода: Unit1. cpp и Unit2. cpp, каждый из которых описывает отдельную экранную форму.


Главная экранная форма программы изображена на рисунке 2.6.:

 

Рис. 2.6. Главная экранная форма программы

Как видно из рисунка 2.6., на главной форме программы присутствуют следующие элементы, реализованные с помощью библиотеки визуальных компонент системы Bulder:

  • кнопки “запуск теста”, ”очистить”, ”сохранить” на основе компоненты TButton
  • контейнеры, объединяющие логически связанные группы некоторых компонентов, на основе компоненты T groupBox

 

  • экран сообщений на основе T Memo
  • окна редактируемого ввода на основе компоненты TEdit
  • спаренные кнопки для установки целочисленного значения – компонента TCSpinEdit
  • контейнер для отображения статусной информации - TStatusBar
  • стандартный набор кнопок приложений Windows: “свернуть”, “развернуть”, “закрыть”, имеющихся во всех объектах класса TForm

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

При запуске программы, внизу оконной формы появляется подсказка–указание пользователю: «выберите один из тестов», т.е. пользователю предлагается выбрать один из тестов который он хочет использовать для тестирования системы. Нужный тест указывается в окне «тесты» с помощью кнопок переключения. Для выбора доступно два теста: тест, на базе вычисления функции Аккермана и Whetstone. После выбора, пользователю необходимо задать параметры этого теста. Для задания параметров используется специальное окно: «параметры теста», в нем задаются следующие значения: два целых неотрицательных числа – параметры функции Аккермана, и время выполнения – для Whetstone.

Проделав описанные выше действия, можно переходить к запуску тестов. Для запуска процесса тестирования служит кнопка “запуск теста”. При ее нажатии, программа анализирует выбранный тест и запускает его на выполнение, результаты тестирования выводятся на экран сообщений. Результаты работы тестов продемонстрированы на рисунке 2.7.

 

 

 


Рис. 2.7. Результаты работы тестирующей программы

На приведенном выше рисунке видно, что последовательно были запущены два теста: вначале функция Аккермана с параметрами A(3,8), а затем Whetstone для которого время выполнения было задано равным тридцати трем секундам. Результатом выполнения первого теста являются следующие полученные данные: время вычисления функции Аккермана, выраженное в секундах и число – ответ, полученный при вычислении функции. Результатом выполнения теста Whetstone является оценка производительности данной вычислительной системы, выраженная в специальных единицах - MWIPS. Подробнее об этом показателе производительности написано в второй главе, в первом параграфе.

После того как пользователь провел все необходимые эксперименты, результаты тестирования можно записать в файл. Для этой цели служит кнопка “сохранить”, при ее нажатии, на экран выводится вторая оконная форма, приведенная на рисунке 2.8.


Рис. 2.8. Вспомогательная форма программы

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

  • Data – дата тестирования (например 01.01.02)
  • Computer – какие-либо дополнительные сведения о компьютере
  • CPU Chip – тип тестируемого процессора
  • Clock MHz – тактовая частота процессора
  • Cache size – объем кэш памяти
  • OS Version – операционная система, поставленная на тестируемом компьютере

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

Текст программы приведен в пункте 2 приложения, структурная схема программы представлена на чертежах 1, 2.

 

<<<Назад Далее>>>

 

 

 

 

 

Компьютерный Дом 2008г.
Rambler's Top100