Модульные тесты для проверки сложности времени - PullRequest
Новая
       13

Модульные тесты для проверки сложности времени

5 голосов
/ 28 января 2009

Кто-нибудь использует модульные тесты для проверки временной и пространственной сложности кода?

Спасибо

Hugo

Ответы [ 4 ]

4 голосов
/ 28 января 2009

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

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

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

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

Unit_Test_To_See_If_X_Takes_More_Than_Y_Seconds(int max_milli_seconds)
{
    int current_millis = getMillis();

    do_operations_on_objects_and_functions();

    int millis_after_executions = getMillis();

    int elapes_millis = millis_after_execution - current_millis;

    if ( elapsed_millis > max_milli_seconds )
      Assert(ERROR);

}

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

1 голос
/ 28 января 2009

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

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

1 голос
/ 28 января 2009

У меня была похожая проблема, когда я настраивал алгоритм. Что я сделал, так это зациклил его, а затем разделил на число циклов и значение big-O. Затем я назвал это «д» или «значение качества». Интересно, что значение было более или менее постоянным, как я ожидал, и немного выше для плохих параметров. Дело в том, что, если вы посмотрите на определение big-O, вы получите измерение «менее доминирующих» вычислений, помимо основного. Они часто постоянны или имеют меньшую сложность. В моем случае это было немного линейно, но все еще не о чем думать.

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

1 голос
/ 28 января 2009

Возможным решением было бы протестировать функцию Филипа с 1 итерацией, затем 100, затем 1000, затем 10000 (и т. Д.) И вывести результаты на график, чтобы определить сложность по времени. Или используйте математические расчеты, чтобы получить наибольшую разность факторов между каждым прогоном. Однако я не уверен, как вы будете тестировать пространство.

Я не думаю, что вывод будет простым проходом или неудачей, если не существует существующего алгоритма для получения наибольшего коэффициента (N ^ 2 и т. Д.) И сравнения с ним.

...