Алгоритмы поиска строк

Question

У меня есть проект по сравнительному анализу алгоритмов сопоставления строк, и я хотел бы знать, существует ли стандарт для каждого алгоритма, чтобы я мог получить честные результаты с моими экспериментами. Я планирую использовать Java System.nanotime для получения времени выполнения каждого алгоритма. Любые комментарии или реакции относительно моей проблемы очень ценятся. Спасибо!

Answer 1

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

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

Answer 2

Опять же, не ясно, о чем вы спрашиваете, но вот еще одна мысль в дополнение к тому, что сказали Тони и Марк:

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

Answer 3

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