Подход к тестированию для алгоритмов со сложными выходами

Question

Как проверить результат программы, которая в основном является черным ящиком? Например, год назад мне пришлось написать дерево B в качестве домашней работы, и я действительно изо всех сил пытался проверить правильность. Какие стратегии вы используете в таких сценариях? Визуализация? Надежный ввод -> наборы результатов испытаний? Что вы делаете, когда такие данные трудно получить, потому что единственный способ получить их - это ваша правильная рабочая программа?

РЕДАКТИРОВАТЬ: Я думаю, что мой вопрос был неправильно понят. Не было проблем с пониманием того, как работает B-дерево. Это тривиально. Но написание надежных тестов для проверки правильности его функциональности не так тривиально. Я думаю, что эта школьная проблема похожа на многие практические сценарии реальных слов и тестовых случаев. И иногда понимание предметной области совершенно отличается от предоставления работающей и правильной программы ...

EDIT2: И да, с помощью дерева B можно проверить правильность поведения с помощью ручки и бумаги. Но это действительно грязно и не весело :) Это плохо работает с проблемами, требующими огромного количества данных для их проверки ...

Answer 1

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

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

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

2. Проверка определенных инвариантов, которые должен поддерживать ваш алгоритм (B-дерево должно быть сбалансировано, значения внутри узлов должны быть отсортированы и т. Д.)

3. Может потребоваться несколько небольших «карандашных и бумажных» тестов - отработайте алгоритм вручную и убедитесь, что он соответствует тому, что делает ваш код. Но все тесты больших данных могут быть типа 2. Они также могут быть хрупкими, поэтому, если вам не нужно быть действительно уверенным в своем алгоритме, вы можете их избежать.

Answer 2

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

Answer 3

@ Быстрик Юрина,

Я часто участвую в проектах, которые предполагают конвертацию между разными форматами данных. Большинство ответов были сосредоточены на тестировании B-дерева или аналогичного алгоритма, но, похоже, вы ищете более общий ответ.

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

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

Методы проверки могут включать формальные контрольные примеры или неформальные программы, которые оспаривают ваши предположения. Это может означать написание базовой программы драйвера для выполнения «основных» подпрограмм. Хороший пример - добавить запись в базу данных, затем прочитать ее обратно и сравнить исходный объект с объектом, загруженным из базы данных.

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

Часто я обнаружил, что построение визуализации заставляет меня признать, что способ хранения данных просто не очень понятен. Для B-дерева представление не очень гибкое. Но в других случаях вы можете использовать параллельные массивы, когда вложенное дерево объектов будет более естественным.

Answer 4

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

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

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

Answer 5

Я думаю, что ответ на вопрос, который вы задаете, сводится к разработке для тестируемости. Часто вы получаете тестируемый дизайн бесплатно, когда вы тестируете разработку решения. Но давайте посмотрим правде в глаза, когда вы реализуете высоко математический алгоритм, это просто не выпадает.

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

Часы "Чистые переговоры по коду - модульное тестирование" Миско Хевери , я думаю, это поможет вам обернуть его вокруг.

Answer 6

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

Answer 7

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

Answer 8

Проконсультируйтесь со специалистом по этому вопросу.

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