Оптимизированная версия strstr (поиск имеет постоянную длину),
Моя программа C имела много strstr вызовов функции. Стандартная библиотека strstr уже быстра, но в моем случае строка поиска всегда имеет длину 5 символов. Я заменил его специальной версией для получения некоторой скорости:
int strstr5(const char *cs, const char *ct)
{
while (cs[4]) {
if (cs[0] == ct[0] && cs[1] == ct[1] && cs[2] == ct[2] && cs[3] == ct[3] && cs[4] == ct[4])
return 1;
cs++;
}
return 0;
}
Функция возвращает целое число, потому что достаточно знать, происходит ли ct в cs. Моя функция проста и быстрее, чем стандарт strstr в этом особом случае, но мне интересно слышать, есть ли у кого-либо некоторые повышения производительности, которые могли бы быть применены. Даже маленькие улучшения приветствуются.
Сводка:
- cs имеет длину> =10, но иначе это может варьироваться. Длина известна прежде (не используемый в моей функции). Длина cs обычно от 100 до 200.
- ct имеет длину 5
- Содержание строк может быть чем-либо
Править: Спасибо за все ответы и комментарии. Я должен изучить и протестировать идеи видеть что работы лучше всего. Я запущу с идеи MAK о суффиксе trie.
3 ответа
Существует несколько алгоритмов быстрого строкового поиска . Попробуйте посмотреть алгоритмы Бойера-Мура (как уже было предложено Грегом Хьюгиллом), Рабина-Карпа и KMP .
Если вам нужно найти много маленьких шаблонов в одном и том же большом тексте, вы также можете попробовать реализовать суффиксное дерево или массив суффиксов . Но это, ИМХО, сложнее понять и правильно реализовать.
Но будьте осторожны, эти методы очень быстрые, но дают заметное ускорение только в том случае, если задействованные строки очень большие. Вы можете не увидеть заметного ускорения для строк длиной менее 1000 символов.
РЕДАКТИРОВАТЬ:
Если вы ищете один и тот же текст снова и снова (т.е. значение cs всегда / часто одинаково для всех вызовов), вы получите большое ускорение, используя суффиксное дерево (в основном это дерево суффиксов). Поскольку размер вашего текста составляет всего 100 или 200 символов, вы можете использовать более простой метод O (n ^ 2) для создания дерева, а затем выполнить по нему несколько быстрых поисков. Для каждого поиска потребуется всего 5 сравнений вместо обычных 5 * 200.
Edit 2:
Как упоминалось в комментарии caf, алгоритм C strstr зависит от реализации. glibc использует алгоритм линейного времени, который на практике должен быть более или менее быстрым, чем любой из упомянутых мной методов. Хотя метод OP асимптотически медленнее (O (N * m) вместо O (n)), он быстрее, вероятно, из-за того, что и n, и m (длина шаблона и текста) очень малы и не требуется выполнять долгую предварительную обработку в версии glibc.
Ваш код может получить доступ к cs за пределами его выделения, если cs короче 4 символов.
Распространенной оптимизацией для строкового поиска является использование алгоритма Бойера-Мура , при котором вы начинаете искать в cs с конца того, что было бы ] CT . См. Связанную страницу для полного описания алгоритма.
Уменьшение количества сравнений увеличит скорость поиска. Сохраните текущее целое число в строке и сравните его с фиксированным целым числом для поискового запроса. Если он совпадает, сравните последний символ.
uint32_t term = ct[0] << 24 | ct[1] << 16 | ct[2] << 8 | ct[3];
uint32_t walk = cs[0] << 24 | cs[1] << 16 | cs[2] << 8 | cs[3];
int i = 0;
do {
if ( term == walk && ct[4] == cs[4] ) { return i; } // or return cs or 1
walk = ( walk << 8 ) | cs[4];
cs += 1;
i += 1;
} while ( cs[4] ); // assumes original cs was longer than ct
// return failure
Добавить чеки на короткий CS.
Edit:
Добавлены исправления из комментариев. Спасибо.
Это можно легко приспособить для использования 64-битных значений. Вы можете хранить cs [4] и ct [4] в локальных переменных вместо того, чтобы предполагать, что компилятор сделает это за вас. Вы можете добавить 4 к cs и ct перед циклом и использовать cs [0] и ct [0] в цикле.