Алгоритмы сравнения двух совпадающих строк — практический подход

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

Спасибо!!!


person pcambre    schedule 09.04.2013    source источник


Ответы (3)


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

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

person MOHAMED    schedule 09.04.2013
comment
Подсчет выполненных инструкций может помочь, да. Можно также рассчитать код. - person Alexey Frunze; 09.04.2013
comment
gcc -S дает вывод на ассемблере. -E для предварительно обработанного кода. - person Mats Petersson; 09.04.2013
comment
Спасибо всем, знаете ли вы, как я могу запустить свой тест в какой-то изолированной среде, то есть изолировать тактовый цикл моего алгоритма от других потоков и получить изолированную меру потребления памяти (ошибки страниц и т. д.)? Еще раз спасибо!!!!! - person pcambre; 09.04.2013
comment
@pcambre Просто запустите свой тест около 1000 раз в цикле и разделите общее время на 1000. - person Alexey Frunze; 09.04.2013

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

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

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

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

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

person Mats Petersson    schedule 09.04.2013

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

person pcambre    schedule 11.04.2013