“Тривиальная” задача

Введение.

Исходная задача
Подсчитать количество локальных максимумов в массиве целых чисел.
Локальный максимум — такой элемент массива, который больше своих соседей.

Задача привлекла своей кажущейся простотой и количеством ошибок, которые делают при ее решении. Также очень хорошо, что на примере с малым количеством кода можно продемонстрировать применение различных подходов к решению.
Чужие решения можно посмотреть в ветке rsdn
Мне было интересно проанализировать, как я сам буду ее решать. Т.е. мне интересно не решение, а поиск решения [1]

PS. Я много лет не пишу код. И плохо помню синтаксис С.
PSS. Боже вас упаси использовать этот текст как библию. Повторюсь, я не программист и мне было интересно не получить идеальные артефакты, а проследить за ходом своих мыслей. Пять лет назад фазы были бы другие.

Итак:

Фаза 1.
Требования не полны, возникают вопросы.
1 Будет ли считаться локальным максимум граничное число? Т.е. в последовательности {2,1,3} максимумов 0 или 2?
2 Каков максимальный размер массива?
3 Как передавать обработанные ошибки?
4 Как поступать в случае массива из одного элемента?
Поскольку заказчик недоступен, будем определять требования, исходя из предметной области и KISS принципа.
1 Согласно курсу матанализа, да считается. [2]
2 Произвольно ограничим размер массива. Например, 10 элементами.
3 Функция при успешной работе возвращает целое, неотрицательное число. Одно из возможных решений - использовать “-1″ как сигнал об ошибке.
4 Возвращать 0. Делаем по аналогии с факториалом нуля. Т.е. это не ошибка, а нормальная ситуация. [2]

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

Фаза 3.
Функциональные требования
1 Система должна считать количество локальных максимумов в массиве целых чисел.
2 Система должна сообщать об ошибке при некорректном значении размера массива (см. п 2 фазы 1)
Юзкейсы
1. Подсчет локальных максимумов
Контекст использования. Уровень функции. Основное действующее лицо - вызывающая программа
Основной сценарий
1) ОДЛ Передает массив целых чисел.
2) Система подтверждает, что число элементов массива находится в пределах от 1 до 10
3) Система подсчитывает число локальных максимумов согласно правилу 1 (см. фазу 1).
4) Система возвращает число подсчитанных максимумов
Требований к производительности на данный момент нет.
Требований к ресурсам на данный момент.

Фаза 4.
Реализуем данную функциональность в виде функции.
Выберем язык реализации - С.
Будем использовать методику Test First

Фаза 5.
Имя функции - countMax
В качестве входных параметров функция будет получать размер массива и ссылку
Возвращаемое значение - целое число
[3]

Фаза 6.
Программа должна корректно работать с данными примерами [4].

Входные данные Возвращаемое значение Примечание
5 {1,4,3,5,1} 2 Простой тест
3 {3,2,1} 1 Левый локальный максимум
3 {1,2,3} 1 Правый локальный максимум
5 {-1,-4,-3,-5,0} 3 Отрицательные числа и 0
0 {1} -1 Граничное условие размера массива
1 {4} 0 Граничное условие размера массива
10 {1,2,3,4,5,6,7,8,9,10} 1 Граничное условие размера массива
11 {1,2,3,4,5,6,7,8,9,10,11} -1 Граничное условие размера массива
5 {} Неинициализированный массив. Это проблемы вызывающей функции, не проверяем.

Фаза 7.

void main(){
int a[5] = {1,4,3,5,1};
if (countMax(5, *a[]) != 2) then printf (”Не пройден простой тест\n”)

int a[3] = {3,2,1};
if (countMax(5, *a[]) != 1) then printf (”Не пройден тест на Левый локальный максимум\n”)

int a[3] = {1,2,3};
if (countMax(5, *a[]) != 1) then printf (”Не пройден тест на Правый локальный максимум\n”)

/* И т.д. Дальше тупая реализация запланированных тестов [5]*/
}

Организация тестов в main - неправильна. Лучше использовать NUnit. Но пока остановимся на этом.

Фаза 8.
Это заглушка, чтобы проверить тесты

int countMax(int arraySize, int *array){
return 1;
}

Фаза 9

/* Функция считает количество локальных максимумов в массиве целых чисел.
Локальный максимум — такой элемент массива, который больше своих соседей.
Размер массива ограничен 10 элементами  */

int countMax(int arraySize, int *array)
{
int count = 0;
int i;

if ((arraySize < 1) || (arraySize > 10)) then return -1
if (array[1] > array[2]) then count++
if (array[arraySize] > array[arraySize-1]) then count++
for (i=1;i < arraySize-2; i++){
if ((array[i] > array[i-1]) && (array[i] > array[i+1])) then count++
}
return count;
}

Фаза 10.
Сидим, думаем.
Черт, я забыл вариант плоских экстремумов! (Например массив {1,2,2,1})
Возвращаемся назад.
Фаза 1. Правило 5. Плоские максимумы также должны считаться.
Фаза 3. В юзкейс добавляется шаг 3. Система преобразует исходный массив в массив без плоских экстремумов, заменяя равные соседние элементы массива на один элемент. Исходный массив, при этом не должен буть испорчен.
Фаза 6. Добавляем тесты:
5 {1,4,4,3,1} 1 Плоский максимум
5 {1,4,4,4,1} 1 Длинный плоский максимум
7 {1,4,4,4,5,5,6} 1 Два плоских экстремума
5 {4,4,4,4,4} 0 Вырожденная последовательность. Только экстремум.
5 {5,4,4,5,6} 2 Плоский минимум.
5 {5,5,4,5,5} 2 Плоские граничные максимумы
Фаза 7. Без комментариев.
Фаза 9. Перепишем код.

/* Функция считает количество локальных максимумов в массиве целых чисел.
Локальный максимум — такой элемент массива или группа равных элементов, которые больше своих соседей.
Размер массива ограничен 10 элементами  */

int countMax(int arraySizeIn, int *arrayIn)
{
int count = 0;
int i;
if ((arraySizeIn < 1) || (arraySizeIn > 10)) then return -1

int array [10];
int arraySize=0;
i=0;
while (i < arraySizeIn-1){
if (array[i] != array[i+1]) then{
array[arraySize] = arrayIn[i];
arraySize++;
}
i++;
}

if (array[1] > array[2]) then count++
if (array[arraySize] > array[arraySize-1]) then count++
for (i=1;i < arraySize-1; i++){
if ((array[i] > array[i-1]) && (array[i] > array[i+1])) then count++
}
return count;
}

Фаза 11.
Теперь нужно сделать вычитку кода на синтаксические ошибки, такие как пропущенные точки с запятой, использование зарезервированных слов, пропущенные void, неправильная передача массива, использование “then”, и т.д.
Это лучше делать в отладчике. Наконец настал тот момент, когда нужно перейти от простого редактора к среде разработки.

Фаза 12.
Компилируем, прогоняем тесты и правим код при необходимости.
Первый же тест выявляет ошибку преобразования массива.
Вместо:

  i=0;
while (i < arraySizeIn-1){
if (arrayIn[i] != arrayIn[i+1]) {
array[arraySize] = arrayIn[i];
arraySize++;
}
i++;
}

Должно быть:

  i=0;
while (i < arraySizeIn-1){
if (arrayIn[i] == arrayIn[i+1])
i++;
array[arraySize] = arrayIn[i];
arraySize++;
i++;
}
array[arraySize] = arrayIn[i];
arraySize++;

Третий тест выявил ошику в строке:

if (array[arraySize] > array[arraySize-1]) count++;

Должно быть:

if (array[arraySize-1] > array[arraySize-2]) count++;

Четвертый тест выявил ошику в строке:

if (array[1] > array[2]) count++;

Должно быть:

if (array[0] > array[1]) count++;

Тест на массив из одного элемента вызывает падение в строке

if (array[0] > array[1]) count++;

Добавим:

if (arraySize == 1) return 0;

И т.д. Почти каждый тест выявляет новую ошибку.

Фаза 13.
Все? Нет. Еще можно добавить:
* Два теста на границы по размеру массива, т.е. массивы с размером 2 и 9. Исходя из моей практики, факт отлавливания ошибок таким тестом очень редок. Не делаю.
* Добавить тест на граничные условия по диапазону элементов массива. Абстрагируясь от написанного кода, делаю следующее предположение:
При написании функции можно исследовать изменение знака приращения элементов с “+” на “-” (аналог исследования производной). Такой алгоритм может вызвать ошибку в последовательности {минимальный элемент, 20, минимальный элемент}. К сожалению, данный тест, зависит от компилятора.
У меня под руками Visual Studio. Здесь int от “-2 147 483 648″ до “2 147 483 647″, соответственно тест:
3 {-2147483648,20,-2147483648} 1 Тест на граничные значения элементов.

А теперь проанализируем, что у нас получилось.
Фаза Род деятельности
1 Определение
2 Определение методологии разработки
3 Разработка требований
4 Высокоуровневая архитектура
5 Низкоуровневая архитектура
6 Планирование тестов
7 Реализация тестов
8 Проверка тестов
9 Кодирование
10 и 13 Вычитка артефактов, с повтором фаз, если в артефакте найдена ошибка.
11 Отладка
12 Тестирование и отладка

Временные оценки можете поставить свои, я выскажу свое мнение.
1) Кодирование и отладка, собственно область действия программиста, даже в таком простом примере, по трудозатратам меньше остальной работы.
2) Часто такую задачу не разбивают на части, а поручают одному человеку (программисту). Это не всегда эффективно. Первый, второй, третий и шестой пункт находятся вне сферы компетенции обычного программиста. Что то лучше отдать архитектору, что то тестеру. “Нельзя знать все на отлично”.
——————————————————————
[1] Была хорошая книга “Поиск решения”. Если сможете достать - прочитайте. Она конечно сложновата, но в дальнейшем очень помогает.
[2] Вот и изучение высшей математики пригодилось. А то “Зачем, зачем?”…
[3] Можно добавить диаграммы, но текст здесь не менее нагляден.
[4] Если делать совсем “по хорошему”, то при планировании тестов в фазе 6 нужно было применять ортогональную матрицу. Общее число тестов было бы меньше. И в связи с фазами 10 и 13 это актуально.
[5] Опять же, если делать совсем “по хорошему”, то тест должен быть один, а данные можно брать из массива данных (например их файла или двумерного массива). Но поскольку нас интересует работоспособный код, а не оптимальность тестов, то делать этого не будем.

Оставьте комментарий

Вы должны войти, чтобы оставить свой комментарий.