Пособие по практике программирования
Существующая версия strstr работала вполне
Существующая версия strstr работала вполне удовлетворительно, когда и образец, и строка были достаточно коротки и менялись при каждом новом вызове, но когда строка оказалась длинной и при этом фиксированной, издержки оказались чрезмерно высоки.
Исходя из вышеизложенных соображений, st rst r была переписана так, чтобы и обход строк образца и сообщения, и поиск совпадений осуществлялись прямо в ней, причем без вызова дополнительных функций. Поведение получившейся реализации было предсказуемо: в некоторых случаях она работала несколько медленнее, но зато в спам-фильтре — гораздо быстрее, и что самое главное, не встретилось случаев, когда бы она работала очень медленно. Для проверки корректности и производительности этой новой реализации был создан набор тестов производительности. В этот набор вошли не только обычные примеры вроде поиска слова в предложении, но и патологические случаи, такие как поиск образца из одной буквы х в строке из тысячи е и образца из тысячи х в строке с одним-един-ственным символом е, а надо сказать, что оба эти случая могли бы стать настоящей проблемой для непродуманной реализации. Подобные экстремальные случаи — ключевая часть оценки производительности.
Наша новая st rst r была добавлена в библиотеку, и в результате спам-фильтр стал работать примерно на 30 % быстрее, чем раньше, — хороший результат для изменения одной функции.
К сожалению, и это было слишком медленно.
Чтобы решить задачу, важно задавать себе правильные вопросы. До сего момента мы искали самый быстрый способ поиска текстового образца в строке. Но на самом деле наша проблема заключается в поиске большого фиксированного набора текстовых образцов в большой строке переменной длины. Если исходить из этого, то наша st rst г не представляется, очевидно, лучшим решением.
Наиболее эффективный способ ускорить программу — применить алгоритм получше. Теперь, когда у нас есть четкое определение проблемы, можно подумать и об алгоритме.
Основной цикл
