Тестирование программы

Существует три аспекта проверки программы

1. Проверка правильности удостоверяет, что программа делает в точности то, для чего она предназначена. При этом исходят из предположений:

· математическая безупречность алгоритма не гарантирует правильности его перевода в программу;

· отсутствие диагностических сообщений компилятора не гарантирует правильность программы;

· разумный вид получаемых результатов не дает достаточной гарантии правильности программы.

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

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

· Программному тестированию должны предшествовать следующие аналитические проверки:

o на соответствие команд алгоритма их программной реализации;

o на соответствие описания переменных и размерностей массивов требуемым значениям;

o на принадлежность значений переменных и индексов массивов допустимым диапазонам при их инициализации и при каждом обращении к внутренним и внешним процедурам;

o на возможность попадания программы в бесконечные циклы.

· Тестированию должно подвергаться возможно большее число ветвей программы. Проверка должна продолжаться до тех пор, пока каждый оператор не будет давать правильный результат.

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

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

Для выявления ошибок должны быть предусмотрены все меры (в том числе и повторная проверка) и зарезервировано достаточно времени.

2. Проверка вычислительной сложности, как правило, заключается в экспериментальном анализе сложности алгоритма или сравнительном анализе нескольких алгоритмов, решающих одну и ту же задачу.

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

При сравнительном анализе нескольких алгоритмов учитывают следующие факторы:

· различие аппаратных средств, на которых проводилось тестирование, языках программирования (компиляторов) и квалификации разработчиков; без учета этого простое сравнение продолжительности работы программ бессмысленно;

Опытный программист реализует экспоненциальный алгоритм более эффективно, чем неопытный — полиномиальный.

· различие задач, на которых проводилось тестирование; целесообразно провести объединение задач;

Каждый найдет для себя наиболее благоприятный случай.

· необходимость комплексной проверки;

Две удачи из трех — еще не повод для окончательных выводов.

· использование комплексных критериев оценки программ.

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

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

Наиболее очевидные способы оптимизации программы следующие.

· Правильное использование типов данных (экономится время и, возможно, память). Дискретные типы (целочисленные, символьные и т. п.) более эффективны, чем непрерывные (вещественные). Эффективность использования типов снижается с ростом их физического размера.

В языке Pascal обработка данных типа real выполняется менее эффективно, чем типов single, double, extended.

Следует избегать неявного преобразования типов, требующего дополнительного вызова библиотечных функций.

Неэффективно:	Эффективно:
double x = 1; // Фактически: // x = (double) 1;   var x: double; ... x:= 1; // Фактически: // x:= double(1);	double x = 1.0;   var x: double; ... x:= 1.0;

· Правильное использование структур данных (экономится время и память). Для эффективной индексации массивов рекомендуется уменьшать число их измерений (сокращаются затраты времени на векторизацию).

Менее эффективно:	Более эффективно:
int x[3][4], i = 1, j = 2; cout << x[i][j] << eol; // Фактически: // k = j + 4 * i // x[k];   var i, j: integer; x: array [1.. 3] of array [1.. 4] of integer; ... i:= 2; j:= 3; writeln(x[i][j]); // Фактически: // k = j + 4 * (i – 1) // x[k];	int x[12], i = 1, j = 2, k = j + 4 * i; cout << x[k] << eol;   var i, j, k: integer; x: array [1.. 12] of integer; ... i:= 2; j:= 3; k = j + 4 * (i – 1); writeln(x[k]);

Использование констант для индексации позволяет оптимизировать обращение к массиву на этапе компиляции.

Неэффективно:	Эффективно:
i = 1; cout << x[i] << eol;   i:= 1; writeln(x[i]);	cout << x[1] << eol;     writeln(x[1]);

При объявлении многомерных массивов его измерения рекомендуется размещать в порядке возрастания. (В этом случае минимизируется таблица векторизации, содержащая результаты расчета относительного положения элементов — последнее измерение не векторизуется.)

Неэффективно:	Эффективно:
// 10 векторов int x[10][5];   var x: array [1.. 10] of array [1.. 5] of double;	// 5 векторов int x[5][10];   var x: array [1.. 5] of array [1.. 10] of double;

· Правильное использование операций (экономится время). Арифметические операции сложения и вычитания выполняются быстрее, чем умножение и деление. Операция деления менее эффективна, чем умножение. Возведение в степень – самая неэффективная операция (кроме возведения в квадрат в языке Pascal).

Неэффективно:	Эффективно:
1.5 * x + y / 2.0 a ^ 3	(x + x + x + y) * 0.5; a * a * a

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

Неэффективно:	Эффективно:
int k, m = 10 * k;     var k, m: integer; ... m:= 10 * k;	int k, m = k << 3 + k << 1;   var k, m: integer; ... m:= k shl 3 + k shl 1;

Логические операции над дискретными типами выполняются очень эффективно.

Неэффективно:	Эффективно:
int x, y, z; ... z = x, x = y, y = z;   var x, y, tmp: integer; ... z:= x; x:= y; y:= z;	int x, y; ... x ^= y ^= x ^= y;   var x, y: integer; ... x:= x xor y; y:= x xor y; x:= x xor y;

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

Неэффективно:	Эффективно:
int i, j; double x, y; ... y = x + i + j;   var i, j: integer; x, y: double; ... y:= x + i + j;	int i, j; double x, y; ... y = x + (i + j);   var i, j: integer; x, y: double; ... y:= x + (i + j);

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

В программе:	Фактически:
double x = 2.5; if (2.0 * x == 5.0) ...	double x = 2.5; if (4.9999... == 5.0) ...

Логические выражения обрабатываются программой до получения результата, поэтому в конъюнктивных формах их целесообразно упорядочивать по убыванию вероятности получения значения False, а в дизъюнктивных формах — по убыванию вероятности получения значения True.

Пример: если в конструкции A && B && C языка C (эквивалент ( A) and (B) and (C) для языка Pascal ) значение A — False, то B и C не проверяются. Аналогично: если в конструкции A || B || C языка C (эквивалент ( A) or (B) or (C) для языка Pascal ) значение A — True, то B и C не проверяются.

Замечание: если в конструкции f(A) && B && Cf(A) чаще принимает значение False, но вычисление самой функции требует существенных затрат времени, то может оказаться, что конструкция B && C && f(A) будет более эффективной.

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

Пример: прямой расчет корней квадратного уравнения при положительном дискриминанте (операций сложения и вычитания — 4, умножения и деления — 10, вызовов функции — 2, операций присваивания — 2).

x1 = (-b – sqrt(b * b – 4.0 * a * c)) / (2.0 * a);

x1 = (-b + sqrt(b * b – 4.0 * a * c)) / (2.0 * a);

Расчет корней квадратного уравнения при положительном дискриминанте с промежуточными переменными (операций сложения и вычитания — 5, умножения и деления — 4, вызовов функции — 1, операций присваивания — 5).

a2 = a + a;

c2 = c + c;

D = sqrt(b * b – a2 * c2);

x1 = (-b – D) / a2;

x1 = (-b + D) / a2;

· Правильная организация циклов (экономия времени). Она достигается следующими способами:

o сокращение числа инициализаций цикла (сокращение потерь времени на приращение и проверку счетчиков);

Неэффективно:	Эффективно:
// Инициируются два цикла for (i = 0; i < 100; i++) x[i] = 0.0; for (i = 0; i < 100; i++) y[i] = 0.0;	// Инициируется один цикл for (i = 0; i < 100; i++) x[i] = y[i] = 0.0;
	// Цикл развертывается for (i = 0; i < 50; i++) j = i + i, x[j] = x[j + 1] = y[j] = y[j + 1] = 0.0;
for i:= 1 to 100 do x[i]:= 0.0; for i:= 1 to 100 do y[i]:= 0.0;	for i:= 1 to 100 do begin x[i] = 0.0; y[i] = 0.0; end;
	for i:= 1 to 100 do begin j:= 2 * i – 1; x[j]:= 0.0; x[j + 1]:= 0.0; y[j] = 0.0; y[j + 1] = 0.0; end;
// Внутренний цикл // инициируется 100 раз for (i = 0; i < 100; i++) for (j = 0; j < 10; j++) a[i][j] = 0.0;   for i:= 1 to 100 do for j:= 1 to 10 do a[i][j]:= 0.0;	// Внутренний цикл // инициируется 10 раз for (j = 0; j < 10; j++) for (i = 0; i < 100; i++) a[i][j] = 0.0; for j:= 1 to 10 do for i:= 1 to 100 do a[i][j]:= 0.0;

o упрощение циклов (сокращение или удаление вычислений из них);

Неэффективно:	Эффективно:
for (i = 0; i < 10; i++) for (j = 0; j < 10; j++) c[i][j] += i * b[i] * a[i][j];	for (i = 0; i < 10; i++) { // Исключается ненужная // адресация массива b // во внутреннем цикле s = 0.0; for (j = 0; j < 10; j++) s += a[i][j]; // Исключается ненужное // вычисление b * i // во внутреннем цикле c[i][j] = i * b[i] * s; }
for i:= 1 to 10 do for j:= 1 to 10 do c[i][j]:= a[i][j] + i * b[i] * a[i][j];	for i:= 1 to 10 do begin s = 0.0; for j:= 1 to 10 do s:= s + a[i][j]; c[i][j]:= i * b[i] * s; end;

· Правильное использование подпрограмм. Передача данных в процедуры через список параметров менее эффективна, чем через глобальные переменные

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

Дата добавления: 2015-07-14