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

Question

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

1. имеет много решений (вы не знаете / не заботитесь о том, сколько их существует),

2. вы можете иметь только небольшое подмножество всех возможных решений, а

3. Проверка правильности решения может быть немного хитрой (возможно, сравнимой по сложности с самим алгоритмом).

Я знаю, что этих условий нет в самой проблеме N-Квинса, но я упомянул ее, чтобы привести пример.

Answer 1

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

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

• Happyтесты пути, чтобы проверить, что алгоритм принимает множество правильных решений
• тесты счастливого пути, чтобы проверить, что алгоритм отклоняет множество неправильных решений
• тесты печального пути, чтобы убедиться, что алгоритм правильно обрабатывает не-candidates (например, «решение» с 7 королевами вместо 8 и т. д.)

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

2:

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

Answer 6

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

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

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

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

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

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

Answer 7

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

Answer 8

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