Отладка и тестирование

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

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

Во-вторых, работа класса тестируется для коллекций, содержащих большие объёмы данных. Целью тестирования является получение статистических оценок трудоёмкости Big-O для основных операций коллекции, а также проверка устойчивости работы коллекции, хранящей большой объём данных, в условиях потока вызовов различных методов.

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

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

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

Для статистического тестирования операций коллекции используется специально разработанная программа (драйвер тестирования эффективности), генерирующая поток операций с заданными свойствами для коллекции заданного размера. Единицы измерения размера коллекции и трудоёмкости операций определяются спецификой коллекции и задаются в задании к лабораторной работе. Драйвер тестирования задаёт модель потока операций гипотетической клиентской программы. Поток состоит из чередующихся равновероятных операций поиска, вставки и удаления данных. Операции задают равновероятные позиции и/или равновероятные значения данных в коллекции. Общее количество операций пропорционально размеру коллекции. Для каждого вида операций задаётся вероятность промаха. Для операций поиска или удаления промахом считается поиск или удаление значения, отсутствующего в коллекции. Если в коллекции запрещено хранение данных с одинаковыми значениями, то вставка нового значения, уже присутствующего в коллекции, ведёт к промаху операции вставки.

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

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

Дата добавления: 2015-11-04