ошибку (с точки зрения тестировщиков) может сделать программист, создающий реализацию функции, при простом вызове функции binary_search(p1,p2,v)? Ошибки часто возникают в особых ситуациях. В частности, при анализе последовательностей (любого вида) мы всегда ищем их начало и конец. Кроме того, всегда следует проверять, не пуста ли последовательность. Рассмотрим несколько массивов целых чисел, которые упорядочены так, как требуется.
{ 1,2,3,5,8,13,21 } // "обычная последовательность"
{ }
{ 1 } // только один элемент
{ 1,2,3,4 } // четное количество элементов
{ 1,2,3,4,5 } // нечетное количество элементов
{ 1, 1, 1, 1, 1, 1, 1 } // все элементы равны друг другу
{ 0,1,1,1,1,1,1,1,1,1,1,1,1 } // другой элемент в начале
{ 0,0,0,0,0,0,0,0,0,0,0,0,0,1 } // другой элемент в конце
Некоторые тестовые последовательности лучше генерировать программой.
• vector<int> v1; // очень длинная последовательность
for (int i=0; i<100000000; ++i) v.push_back(i);
• Последовательности со случайным количеством элементов.
• Последовательности со случайными элементами (по-прежнему упорядоченные).
И все же этот тест не настолько систематический, насколько нам бы хотелось. Как-никак, мы просто выискали несколько последовательностей. Однако мы следовали некоторым правилам, которые часто полезны при работе с множествами значений; перечислим их.
• Пустое множество.
• Небольшие множества.
• Большие множества.
• Множества с экстремальным распределением.
• Множества, в конце которых происходит нечто интересное.
• Множества с дубликатами.
• Множества с четным и нечетным количеством элементов.
• Множества, сгенерированные с помощью случайных чисел.
Мы используем случайные последовательности просто для того, чтобы увидеть, повезет ли нам найти неожиданную ошибку. Этот подход носит слишком “лобовой” характер, но с точки зрения времени он очень экономный.
Почему мы рассматриваем четное и нечетное количество элементов? Дело в том, что многие алгоритмы разделяют входные последовательности на части, например на две половины, а программист может учесть только нечетное или только четное количество элементов. В принципе, если последовательность разделяется на части, то точка, в которой это происходит, становится концом подпоследовательности, а, как известно, многие ошибки возникают в конце последовательностей.
В целом мы ищем следующие условия.
• Экстремальные ситуации (большие или маленькие последовательности, странные распределения входных данных и т.п.).
• Граничные условия (все, что происходит в окрестности границы).
Реальный смысл этих понятий зависит от конкретной тестируемой программы.
26.3.2.2. Схема простого теста
Существуют две категории тестов: тесты, которые должны пройти успешно (например, поиск значения, которое есть в последовательности), и тесты, которые должны завершиться неудачей (например, поиск значения в пустой последовательности). Создадим для каждой из приведенных выше последовательностей несколько успешных и неудачных тестов. Начнем с простейшего и наиболее очевидного теста, а затем станем его постепенно уточнять, пока не дойдем до уровня, приемлемого для функции binary_search.
int a[] = { 1,2,3,5,8,13,21 };
if (binary_search(a,a+sizeof(a)/sizeof(*a),1) == false) cout << " отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),5) == false) cout << " отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),8) == false) cout << " отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),21) == false) cout << " отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),–7) == true) cout << " отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),4) == true) cout << " отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),22) == true) cout << " отказ";
Это скучно и утомительно, но это всего лишь начало. На самом деле многие простые тесты — это не более чем длинные списки похожих вызовов. Положительной стороной этого наивного подхода является его чрезвычайная простота. Даже новичок в команде тестировщиков может добавить в этот набор свой вклад. Однако обычно мы поступаем лучше. Например, если в каком-то месте приведенного выше кода произойдет сбой, мы не сможем понять, где именно. Это просто невозможно определить. Поэтому фрагмент нужно переписать.
int a[] = { 1,2,3,5,8,13,21 };
if (binary_search(a,a+sizeof(a)/sizeof(*a),1) == false) cout << "1 отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),5) == false) cout << "2 отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),8) == false) cout << "3 отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),21) == false) cout << "4 отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),–7) == true) cout << "5 отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),4) == true) cout << "6 отказ";
if (binary_search(a,a+sizeof(a)/sizeof(*a),22) == true) cout << "7 отказ";
Если вы представите себе десятки тестов, то почувствуете огромную разницу. При тестировании реальных систем мы часто должны проверить многие тысячи тестов, поэтому знать, какой из них закончился неудачей, очень важно.
Прежде чем идти дальше, отметим еще один пример (полуформальный) методики тестирования: мы тестировали правильные значения, иногда выбирая их из конца последовательности, а иногда из середины. Для данной последовательности мы можем перебрать все ее значения, но на практике сделать это нереально. Для тестов, ориентированных на провал, выбираем одно значение в каждом из концов последовательности и одно в середине. И снова следует отметить, что этот подход не является систематическим, хотя он демонстрирует широко распространенный образец, которому можно следовать при работе с последовательностями или диапазонами значений.
Какими недостатками обладают указанные тесты?
• Один и тот же код приходится писать несколько раз.
• Тесты пронумерованы вручную.
• Вывод минимальный (мало информативный).
Поразмыслив, мы решили записать тесты в файл. Каждый тест должен иметь идентифицирующую метку, искомое значение, последовательность и ожидаемый результат. Например:
{ 27 7 { 1 2 3 5 8 13 21} 0 }
Это тест под номером 27. Он ищет число 7 в последовательности { 1,2,3,5,8,13,21 }, ожидая, что результатом является 0 (т.е. false). Почему мы записали этот тест в файл, а не в текст программы? В данном случае мы вполне могли написать этот тест прямо в исходном коде, но большое количество данных в тексте программы может ее запутать. Кроме того, тесты часто генерируются другими программами. Как правило, тесты, сгенерированные программами, записываются в файлы. Кроме того, теперь мы можем написать тестовую программу, которую можно запускать с разными тестовыми файлами.
struct Test {
string label;
int val;
vector<int> seq;
bool res;
};
istream& operator>>(istream& is, Test& t); // используется описанный
// формат
int test_all(istream& is)
{
int error_count = 0;
Test t;
while (is>>t) {
bool r = binary_search( t.seq.begin(), t.seq.end(), t.val);
if (r !=t.res) {
cout << "отказ: тест " << t.label
<< "binary_search: "
