Нужно ли тестировать алгоритмическую сложность? Если так, то как?

Допустим, я реализую что-то простое, например, поиск в отсортированном списке / массиве. Функция (в c #) будет выглядеть так:

static int FindIndex(int[] sortedList, int i);

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

Итак, мой вопрос: должны ли мы попытаться написать тесты, которые гарантируют производительность с точки зрения алгоритмической сложности, и если да, то как?

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

С точки зрения «как», это становится очень интересным :) Вы могли видеть параметризацию оператора сравнения и наличие теста, оператор сравнения которого считает сравнения или что-то в этом роде. Но то, что вы можете, не значит, что вы должны ...

Кто-нибудь еще обдумывал это (наверное)? Благодарю.

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

Абсолютная производительность может быть проверена механически и может сделать полезные юнит-тесты. Если производительность имеет значение, то вы можете указать порог: «этот запрос должен занимать не более 50 мсек для выполнения 10 ⁶ номеров и не более 60 мсек для 10 ⁷ номеров». Для которого вы можете построить модульный тест.

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

Хотя я не уверен, что этот инструмент будет особенно полезен для модульных тестов, в статье «Эмпирическая вычислительная сложность» Голдсмита, Айкена и Уилкерсона описан метод инструментирования кода и наблюдения за его динамическим поведением на множестве различных входов для эмпирического анализа. вывести его асимптотическую сложность. Программа, описанная в статье, имеет открытый исходный код и доступна здесь .

Надеюсь это поможет!

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

В моем опыте настройки производительности, как и в этом примере , что происходит, если какой-то алгоритм (например) O (n ^ 2), может быть просто хорош, если процент времени, который он занимает, никогда не попадает на радар.

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

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

Я не думаю, что вы хотите сделать это модульное тестирование.

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

Из Википедии : нельзя ожидать, что тестирование отследит каждую ошибку в программе: невозможно оценить каждый путь выполнения во всех программах, кроме самых простых. То же самое верно для модульного тестирования. Кроме того, модульное тестирование по определению проверяет только функциональность самих модулей. Следовательно, он не будет отлавливать ошибки интеграции или более широкие ошибки системного уровня (например, функции, выполняемые на нескольких устройствах, или нефункциональные области тестирования, такие как производительность). Модульное тестирование должно проводиться в сочетании с другими действиями по тестированию программного обеспечения. Как и все формы тестирования программного обеспечения, модульные тесты могут показывать только наличие ошибок; они не могут показать отсутствие ошибок.

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

Есть несколько других, таких как тестирование производительности (которое использует стресс-тестирование, нагрузочное тестирование и т. Д.).

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

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

Передача в компараторе и отслеживание количества его вызовов будет работать для простых целей, таких как проверка того, что число сравнений при выполнении поиска в фиксированном вводе (скажем new int[] { 1,2,3, ... , 1024 }) остается ниже 10. Это по крайней мере проясните свои намерения о том, как алгоритм должен вести себя.

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