Как ускорить функцию поиска подстроки на C?

Question

[Данил Тунев]

Как можно ускорить функцию поиска подстроки в строке (strstr)? Написал исчерпывающее решение (для меня). но оно не ровня библиотечным функциям (по времени выполнения) на linux для C. Сразу скажу, что компилировал с оптимизацией 1, выше поднимался. но время выполнения не менялось и добавил пару аргументов: длина строки и длина подстроки

char* fun_search_c(register char* m_0,int l_0,char* m_1,int l_1)
{
        register char* m=m_0+l_0;
        register int l=0;
        for(;m_0<m;m_0++){
                if(m_0[0]==m_1[0]){
                        for(;m_0<m;m_0++,m_1++,l++){
                                if(m_0[0]!=m_1[0]){
                                        m_0-=l;
                                        m_1-=l;
                                        l=0;
                                        break;
                                }
                                if(l==l_1-1){
                                        return m_0-l;
                                }
                        }
                }
        }
        return 0;
}

Comments

[Lynn «Кофеман»]

Ну можно с википедии начать https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D...

[Сергей Горностаев]

Алексей Тен, это вполне тянет на ответ.

Answer 1

[Karpion]

У меня есть подозрение, что функции работы со строками пишутся на ассемблере и используют команды процессора типа REP SCAS - надеюсь, Вы знаете, что это такое.
Проверить это можно на исходниках библиотек, благо в Linux они доступны.

Навскидку я могу Вам посоветовать заменить m_0[0] на *m_0 - хотя это вряд ли что-то изменит.

И я вообще не понял Вашего алгоритма. Такое ощущение, что Вы зачем-то сравниваете с конца.

И ещё интересно, на каких примерах Вы это тестировали. Есть тонкость - многие алгоритмы поиска подстроки сильно зависят от данных. Если строка набита случайными символами - лучший подход один; если строка содержит повторяющиеся куски - лучший подход немного совсем другой.

Comments

[Сергей Горностаев]

У меня есть подозрение, что функции работы со строками пишутся на ассемблере и используют команды процессора типа REP SCAS

Да не обязательно, достаточно не использовать квадратичный алгоритм.

[Karpion]

Сергей Горностаев, Поскольку алгоритм оказывается квадратичным только на определённых строках - весьма вероятно, что постой алгоритм на ассемблерном ускорении будет работать быстрее.
Кстати, встроенную функцию при константных аргументах - можно выполнить при компиляции.

[Karpion]

Данил Тунев, Очевидно - подставить на место вызова/выполнения функции результат выполнения. Простейший пример: вместо "x=sin(30 градусов)" делается "x=0.5".
Прочитайте про оптимизирующие компиляторы, что они творят и как это временами глючит.

[Данил Тунев]

Karpion, Я хотел писать на чистом си, но видимо не все золото можно найти в медных рудниках