Как выполнить модульное тестирование с неопределенностью?

Question

У нас есть несколько разных алгоритмов оптимизации, которые дают разные результаты для каждого прогона. Например, целью оптимизации может быть нахождение минимума функции, где 0 - глобальные минимумы. Прогоны оптимизации возвращают такие данные:

[0.1, 0.1321, 0.0921, 0.012, 0.4]

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

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

Вот некоторые дополнительные пояснения:

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

• К сожалению, я не могу выбрать фиксированное начальное число для генератора случайных чисел, потому что я не хочу проверять, дает ли алгоритм тот же самый результат, что и раньше, но я хочу проверить что-то вроде: «С уверенностью 90% я получить результат с 0.1 или лучше ".

Answer 1

Похоже, ваш оптимизатор нуждается в двух видах тестирования:

1. проверка общей эффективности алгоритма
2. проверка целостности вашей реализации алгоритма

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

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

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

Обновление : я написал главу об этой проблеме в книге Beautiful Testing. См. Главу 10: Проверка генератора случайных чисел .

Answer 2

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

Вы можете либо

1. Разрешить вызывающему абоненту выбрать начальное число для генератора случайных чисел. Затем используйте в тесте твердо закодированное семя.
2. Пусть вызывающий абонент предоставит генератор случайных чисел. Затем используйте в тестах ложный генератор случайных чисел.

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

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

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

Например, при реализации алгоритма оптимизации Foo-Bar-Baz (TM) вы могли случайно написать x: = x / 2 вместо x: = x / 3. Это может означать, что алгоритм работает медленнее, но все равно находит тот же алгоритм. Вам понадобится тестирование белого ящика, чтобы найти такую ​​ошибку.

Edit:

К сожалению, я не могу выбрать фиксированное начальное число для генератора случайных чисел, потому что я не хочу проверять, дает ли алгоритм тот же самый результат, что и раньше, но я хочу проверить что-то вроде «С 90% уверенностью, я получаю результат с 0,1 или лучше ".

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

Если вы хотите проверить «С 90% уверенностью, я получаю результат с 0.1 или лучше», я бы предложил что-то вроде:

double expectedResult = ...;
double resultMargin = 0.1;
int successes = 0;
for(int i=0;i<100;i++){
  int randomSeed = i;
  double result = optimizer.Optimize(randomSeed);
  if(Math.Abs(result, expectedResult)<resultMargin)
    successes++; 
}
Assert.GreaterThan(90, successes);

(Обратите внимание, что этот тест является детерминированным).

Answer 3

У модульного теста никогда не должно быть неизвестного состояния прохождения / сбоя. Если ваш алгоритм возвращает разные значения при запуске с одними и теми же входами несколько раз, вы, вероятно, делаете что-то странное в своем алгоритме.

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

РЕДАКТИРОВАТЬ : Для адресации случайных компонентов вашей системы вы можете либо ввести возможность передать начальное число для генератора случайных чисел, либо вы можете использовать библиотеку насмешек (ala RhinoMocks). заставить его использовать конкретное число, когда RNG запрашивается случайное число.

Answer 4

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

Answer 5

Спасибо за все ответы, я сейчас делаю это:

1. Запустите тест 5 раз и возьмите средний результат.
2. Если медианный результат ниже определенного порога, тест завершается успешно.
3. Если порог не пройден, протестируйте снова, пока не будет достигнут порог (тест пройден успешно) ИЛИ пока я не выполнил столько итераций (около 100 или около того), что я могу быть уверен, что медиана не опустится ниже порога больше.

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

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

Answer 6

Я бы предложил, чтобы вместо того, чтобы ваш тест выполнялся с кодом, создающим гауссовский дистрибутив, вы создали алгоритм типа Монте-Карло, который многократно запускает метод, а затем тестирует общее распределение результатов с использованием соответствующей модели распределения. Например, если это среднее значение, то вы сможете иметь возможность проверить на устойчивое пороговое значение. Если он более сложный, вам нужно создать код, который моделирует соответствующее распределение (например, значения

Имейте в виду, что вы не тестируете генератор чисел, вы тестируете модуль, который генерирует значения!

Answer 7

Как jUnit, так и NUnit могут утверждать типы данных с плавающей запятой со значением допуска / дельты. То есть вы проверяете, является ли вывод правильным значением, задайте или примите некоторое десятичное число. В вашем случае правильное значение, которое вы хотите проверить, равно 0, с допуском 0,5, если вы хотите, чтобы все значения в данном выходном сигнале прошли (или 0,20 с допуском +/- 0,20).

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