Unit-тестирование сложного алгоритма

Ответ 1

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

Ответ 2

В вашем примере, я думаю, вы говорите, что хотите unit test алгоритм, который проверяет предлагаемое решение.

Вы хотите охватить следующие случаи:

• Счастливые тестовые тесты для проверки того, что алгоритм принимает множество правильных решений.
• Счастливые тестовые тесты для проверки того, что алгоритм отклоняет множество неправильных решений.
• Печатные тесты пути, чтобы алгоритм правильно обрабатывал не-кандидатов (например, "решение" с 7 ферзями вместо 8 и т.д.).

Здесь "разнообразие" означает, что вы хотите, чтобы решения охватывали пространство возможностей. Но то, что означает, чтобы покрыть это пространство, является специфичным для конкретной проблемы. Я недостаточно разбираюсь в проблеме N-queens, чтобы узнать, какое разнообразие существует в правильных решениях, но эта информация была бы полезной, если бы я был реализован тест. Что касается неправильных решений, вы хотите, чтобы некоторые из них включали один и тот же ранг, тот же файл, ту же диагональ и микс. Некоторые из них связаны с экспозицией вдоль края доски, а некоторые - с выдержкой с края. Etc.

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

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

Ответ 3

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

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

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

Тогда я смог "усилить" канонические случаи, применяя случайные преобразования. Это немного помогло.

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

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

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

Объединив все эти методы, я смог получить высокую уверенность в коде.

Ответ 4

Если вы знаете, какой алгоритм вам понадобится, тогда один из вариантов - реализовать некоторые части этого алгоритма с использованием TDD. Так что, когда эти части были реализованы, построение полного алгоритма будет тривиальным.

Вот один из примеров проблемы (диаграмма из девяти мест), для которой я не знал решения, поэтому для написания теста для него было бы трудно, если не невозможно, или непрактично с точки зрения TDD (это потребовало бы слишком большого скачка). Я понял, что он очень похож на проблему с Девятью Queens, поэтому я решил использовать аналогичный алгоритм, который я использовал для решения Nine Queens. Я использовал DiagramTest для тестового диска Diagram, после чего помещение всего в DiagramOfNinePlaces было всего лишь дюжиной строк кода. После запуска кода я проверил конечный результат вручную, и это действительно решение проблемы.

Ответ 5

Алгоритмы на самом деле являются самыми легкими в unit test, поскольку у вас нет внешних зависимостей. Лучшим подходом является использование test-driven-development: выясните, какое следующее крошечное требование вы хотите, чтобы алгоритм выполнил, создайте тест для него, а затем напишите код, чтобы удовлетворить этот тест (и не больше кода, чем необходимо, даже если это означает hardcoding результат). Затем вы продолжаете, рефакторинг кодовой базы по мере необходимости, чтобы сделать ее более общей и принять больше случаев использования. К тому времени, когда все ваши варианты использования будут рассмотрены, вы должны иметь прочную реализацию алгоритма.

Ответ 6

Вы можете только проверить, какое поведение вы можете ожидать.

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

Знаете ли вы, что никаких решений для каких-либо других тестовых данных не существует? Например. вы можете легко убедить себя, что невозможно посадить трех ферзей на 3x3 или девять ферзей на 8x8. Затем проверьте, что ваша программа не возвращает никакого решения или выбрасывает ожидаемое исключение.

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

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

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

Ответ 7

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

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

2:

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

Ответ 8

unit test должен проверять вывод алгоритма для широкого разнообразия входов и потому что эта задача также сложна, ее нужно записать другим человеком (и надеяться, что если в коде есть ошибка, не делайте ту же ошибку)