Быстрый метод проверки подстрок

Question

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

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

---

Я играл с std::string::find() и функцией strstr(). Согласно моим тестам, std::string::find() был явно быстрее, чем старая функция в стиле C strstr().

Я знаю, что std::string очень хорошо оптимизирован, но массивы char в стиле C и их собственные функции всегда казались несколько быстрее, особенно если строка должна создаваться снова и снова.

Итак, есть ли что-нибудь быстрее, чем std::string::find() для сканирования серии символов на наличие заблокированных слов? std::string::find() быстрее strstr() или мои тесты паршивые? Я знаю, что выигрыш может быть незначительным по сравнению с усилиями, необходимыми для поддержания чистоты массивов и их функций в стиле C char, но я бы хотел сохранить его как можно быстрее, даже если это только для целей тестирования.

---

РЕДАКТИРОВАТЬ: Извините, забыл упомянуть, что я использую MSVC ++ 2010 Express. Я ориентируюсь только на машины Windows.

Answer 1

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

Answer 2

Вы пробовали библиотеку регулярных выражений в C ++ 11, если вы используете это, или в Boost, если вы этого не делаете?Я не уверен в скорости, но я считаю, что они работают довольно хорошо.Кроме того, если вы используете его в качестве фильтра от ненормативной лексики, вам все равно потребуются регулярные выражения, чтобы избежать тривиального обхода.

Answer 3

Существуют более быстрые алгоритмы поиска, чем линейный поиск, обычно используемый в STL, или strstr.

Бойер-Мур довольно популярен.Требуется предварительная обработка целевой строки, что должно быть выполнимо для вашего варианта использования.

Точные алгоритмы сопоставления строк - это бесплатная электронная книга с подробным описанием различных алгоритмов поиска.и их преимущества.

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