Оптимизированная версия strstr (поиск имеет постоянную длину)

Question

В моей 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.

Answer 1

Существует несколько быстрых алгоритмов поиска строки . Попробуйте взглянуть на алгоритмы Бойера-Мура (как уже было предложено Грегом Хьюгиллом), Рабин-Карп и KMP .

Если вам нужно искать множество небольших шаблонов в одном и том же большом тексте, вы также можете попробовать реализовать суффиксное дерево или суффиксный массив . Но их ИМХО несколько сложнее понять и правильно реализовать.

Но будьте осторожны, эти методы очень быстрые, но дают вам заметное ускорение, только если задействованные строки очень большие. Вы можете не увидеть заметного ускорения для строк длиной менее 1000 символов.

EDIT:

Если вы выполняете поиск по одному и тому же тексту снова и снова (т. Е. Значение cs всегда / часто одинаково для всех вызовов), вы получите значительное ускорение при использовании суффикса trie (в основном три суффиксов). Поскольку ваш текст составляет всего 100 или 200 символов, вы можете использовать более простой метод O (n ^ 2) для построения дерева и затем выполнить несколько быстрых поисков по нему. Каждый поиск потребует только 5 сравнений вместо обычных 5 * 200.

Редактировать 2:

Как отмечено в комментарии caf, алгоритм C strstr зависит от реализации. glibc использует алгоритм линейного времени, который на практике должен быть более или менее быстрым, как любой из методов, которые я упомянул. Хотя метод OP асимптотически медленнее (O (N * m) вместо O (n)), он быстрее, вероятно, из-за того, что оба n и m (длины шаблона и текста) очень малы, и это не требуется выполнять длительную предварительную обработку в версии glibc.

Answer 2

Уменьшение количества сравнений увеличит скорость поиска.Сохраняйте int в строке и сравнивайте его с фиксированным int для поискового запроса.Если он совпадает, сравните последний символ.

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

Добавьте проверки для короткого кода.

Редактировать:

Добавлены исправления из комментариевСпасибо.

Это может быть легко принято для использования 64-битных значений.Вы можете хранить cs [4] и ct [4] в локальных переменных, не предполагая, что компилятор сделает это за вас.Вы можете добавить 4 к cs и ct перед циклом и использовать cs [0] и ct [0] в цикле.

Answer 3

Интерфейс strstr налагает некоторые ограничения, которые могут быть побеждены.Он принимает строки с нулевым символом в конце, и любой конкурент, который первым сделает "стрельбу" своей цели, потеряетОн не требует аргумента «состояние», поэтому затраты на настройку нельзя амортизировать для многих вызовов, скажем, с одной и той же целью или шаблоном.Ожидается, что он будет работать с широким диапазоном входных данных, включая очень короткие цели / паттерны и патологические данные (рассмотрите возможность поиска «ABABAC» в строке «ABABABABAB ... C»).libc также теперь зависит от платформы.В мире x86-64 SSE2 уже семь лет, а strlen и strchr в libc, использующие SSE2, в 6-8 раз быстрее наивных алгоритмов.На платформах Intel, поддерживающих SSE4.2, strstr использует инструкцию PCMPESTRI.Но вы можете и это побить.

У Бойера-Мура (и Turbo BM, и Backward Oracle Matching, и др.) Есть время установки, которое в значительной степени выбивает их из строя, даже не считая нользаданная строка.Хорспул - ограниченный БМ, который хорошо работает на практике, но плохо справляется с крайними случаями.Лучшее, что я нашел в этом поле, - это BNDM («Обратное недетерминированное направленное ациклическое сопоставление слов-графов»), реализация которого меньше его имени: -)

Вот несколько фрагментов кода, которые могутпредставлять интерес. Интеллектуальный SSE2 превосходит наивный SSE4.2 и обрабатывает проблему нулевого завершения. Реализация BNDM показывает один из способов сохранения затрат на настройку.Если вы знакомы с Horspool, вы заметите сходство, за исключением того, что BNDM использует битовые маски вместо пропусков.Я собираюсь опубликовать, как решить проблему с нулевым терминатором (эффективно) для суффиксных алгоритмов, таких как Horspool и BNDM.

Общим признаком всех хороших решений является разбиение на разные алгоритмы для разных длин аргументов.Примером является функция "Рейлган" Санмейса .

Answer 4

Хорошая реализация на современном компьютере x86 не сравнится.

Новые процессоры Intel имеют инструкцию, которая занимает 16 байтов исследуемой строки, до 16 байтов строки поиска, и в одной инструкции возвращается, которая является первой позицией байта, в которой может находиться строка поиска (или если здесь ничего нет). Например, если вы ищете «Hello» в строке «abcdefghijklmnHexyz», первая инструкция скажет вам, что строка «Hello» может начинаться со смещения 14 (поскольку при чтении 16 байтов процессор имеет байты H , e, неизвестно, какое может быть местоположением "Hello". Следующая инструкция, начинающаяся со смещения 14, затем сообщает, что строки нет. И да, она знает о конечных нулевых байтах.

Это две инструкции, чтобы найти, что строка из пяти символов отсутствует в строке из 19 символов. Попробуйте обыграть это любым специальным кодом. (Очевидно, это сделано специально для strstr, strcmp и подобных инструкций).

Answer 5

Ваш код может получить доступ к cs за пределами своего выделения, если cs короче 4 символов.

Обычная оптимизация для поиска по строке - это использование Boyer-Moore алгоритм, в котором вы начинаете искать в cs с конца того, что будет ct.См. Связанную страницу для полного описания алгоритма.