Сравнение двух подходящих алгоритмов строк - Практический подход

Question

Я написал два разных алгоритма, которые разрешают какой-либо конкретный случай соответствия строк (реализованный на C). Я знаю, что теоретические O этих алгоритмов равны, но я думаю, что на практике один лучше, чем другой. Мой вопрос: кто-то может порекомендовать мне какую-нибудь бумагу или какое-нибудь чтение, где показано, как сравнивать алгоритмы с практическим подходом? У меня есть несколько тестовых наборов, мне интересно измерять время выполнения и размер памяти. Мне нужно, чтобы эти значения были как можно более независимыми от операционной системы и других программ, которые могут запускаться одновременно.

Спасибо !!!

Answer 1

Для того, чтобы комментировать, я нашел книгу под названием «Руководство по экспериментальной алгоритмике» Кэтрин К. Макгеох Amazon, и специалист-профессионал рекомендует мне практическую статью pdf.

Answer 2

Вы можете сравнить свои алгоритмы, сформировав код сборки и сравните их.

Вы можете сгенерировать код сборки с gcc -S mycode.c команды

Answer 3

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

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

Итак, в конце концов, нет никакой замены для фактического запуска кода, используя синхронизацию тактового цикла (например, инструкцию RDTSC для процессоров x86) или запуск большого цикла для выполнения кода много раз, чтобы дать разумная продолжительность выполнения.

Если ваш код не должен запускаться на одной внедренной цели, вы, вероятно, захотите запустить код на множестве различных аппаратных средств, чтобы определить, быстрее или быстрее ли работает на процессоре A на B, C и процессоры типа D. Часто это работает, но иногда вы можете обнаружить, что конкретная модель процессора быстрее для НЕКОТОРЫХ операций, а другая быстрее для другой (например, на основе размера кеша и т. Д.).

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