Нужен быстрый алгоритм сравнение строк...

Я делаю так:
сравниваю побайтово символы строки1 и строки2, если хоть один не совпадает то строки не совпадают...
Нужно сделать быстрее. Подскажите какие ещё варианты есть?

Не понимаю, куда такая скорость. Я делал прогу, там надо было не просто сравнивать, а производить поиск сочетаний в вводимом слове. Сочетаний было около 28000, всё должно было обрабатываться в хуке во время печати на клаве. Функции CString действительно тормозили, так как там постоянно память перевыделялась, но Cи Runtime функции справились отлично!

ИМХО
Команда ассемблера cmpsb спасет отца русской демократии

strcmp тоже вроде быстро пашет, всяко быстрее самописного цикла

2kourov :
Понимеешь программа должна проанализировать
сотни тысяч или даже миллионы строк... и побыстрее

2DemonM :
В моём случае strcmp не поможет...

Пишешь примерно следующее (пишу по памяти, поэтому за ошибки не обессудь):
int len1 = strlen(s1);
int len2 = strlen(s2);
if (len1 != len2)
return false;
bool ret_val = false;
_asm
{
mov esi, str1
mov edi, str2
mov ecx, len1
rep cmpsb
jnc exit
mov ret_val, 1
exit:
}
return ret_val;
Поиск длины строки тоже можешь завернуть на ассемблере. Если сделаешь функции инлайновыми, то быстрей алгоритма ты не найдешь.

Кстати, вот пример из CRTL VC++ (файл strncmp из дериктории vc98\crt\src\intel\):
CODESEG
public strncmp
strncmp proc \
uses edi esi ebx, \
first:ptr byte, \
last:ptr byte, \
count:IWORD

mov ecx,[count] ; cx=max number of bytes to compare
jecxz short toend ; it's as if strings are equal
mov ebx,ecx ; bx saves count
mov edi,[first] ; di=first pointer (es=segment part)
mov esi,edi ; si saves first pointer
xor eax,eax ; ax=0
repne scasb ; count bytes
neg ecx ; cx=count - strlen
add ecx,ebx ; strlen + count - strlen
okay:
mov edi,esi ; restore first pointer
mov esi,[last] ; si = last pointer
repe cmpsb ; compare strings
mov al,[esi-1]
xor ecx,ecx ; set return value = 0
cmp al,[edi-1] ; last-first
ja short lastbig ; <last is bigger>
je short toend ; <equal>
;jb short firstbig ; <first is bigger>
firstbig:
dec ecx ; first string is bigger
dec ecx ; make FFFE so 'not' will give 0001
lastbig: ; last string is bigger
not ecx ; return -1
toend:
mov eax,ecx ; return value
ret ; _cdecl return
strncmp endp
end

2Flex Ferrum:
К сожалению тут strlen уже всё тромозит...
если я поставю хтабы только сравнение на разность строк, даже не сравнивая 2 массива, то это уже дольше работает чем так как я делю(как в самой первой месаге написанно)

В той же директории лежит модуль strlen.asm. Объедени это в одну функциию, написанную на асме, или посмотри, как это реализовано в модуле strcmp.asm.

Возможно, поможет такая стратегия (я использовал нечто похожее при написании LZ77-сжатия, и это помогло):
Сравниваем не a[0]==b[0]; a[1]==b[1]; a[2]==b[2]..., а:
L-длинна строки
a[0]==b[0]; a[L-1]==b[L-1]; a[1]==b[1]; a[L-2]==b[L-2]; т.е. начинаем сравнивать с начала и конца.

int find_str(char* buf1,char* buf2,int len1,int len2)
{
for(int i=len;i>=0;i--){
if(!buf1[i]|buf2[i]){return -1}; //строки не совпадают!
};
return 0; //строки совпадают
};

вот как ща сделал...
Кто быстрее сам алгоритм может проедложить?(именно алгоритм а не оптимезацию на асме)

Может хотел написать вот так:
int find_str(char* buf1,char* buf2,int len1,int len2)
{
for(int i=len;i>=0;i--){
if(!(buf1[i]^buf2[i])){return -1}; //строки не совпадают!
// вот тут поправил | на ^ и скобоцки расставил
};
return 0; //строки совпадают
};

надеюсь, просто пропущен код, который сравнивает len1 и len2,
кроме того где-то там же появляется третья переменная len,
видимо меньшая из них.

2 Sourcer: Тебе Flex Ferrum правильно предложил напишу функцию на ассемблере. На Си ты все равно быстрее не напишешь, какой бы ты алгоритм не придумал. Задача тривиальна, алгоритм один, все зависит от реализации.
Предлагаю тебе текст функции и могу заявить, что быстрее реализации ты не придумаешь.
__declspec(naked) int find_str(char* buf1, char* buf2, int len1, int len2)
{
__asm
{
push esi
push edi
xor eax,eax
mov ecx,len1
cmp ecx,len2
jne exit1
mov esi,s1
mov edi,s2
mov edx,ecx
shr ecx,2
jz cmpbytes
repe cmpsd
jne exit1
cmpbytes:
mov ecx,edx
and ecx,3
repe cmpsb
jne exit1
inc eax
exit1:
pop edi
pop esi
ret
}
}
__declspec(naked) не убирай, чтобы компилятор свой пролог и эпилог не вставлял, он тоже может подтармаживать

Если строки длинные, возможно быстрее будет использовать не CMPSB, а CMPSD.

Sourcer:
А что, побитовое OR или XOR работают быстрее обычного стравнения?
И еще. Когда тебе нужен действительно быстрый алгоритм - без ручной оптимизации на ассемблере не обойтись - каким бы ни был хорошим компилятор, все равно он не соптимизирует код лучше человека (в некоторых случаях).

Согласен с Flex Ferrum насчет того, что скорее всего действительно придется переписать на асме, но для начала все-таки неплохо бы выбрать наилучший алгоритм.
Сравнивать строки в лоб - слабая опримизация, не так ли?
Что у тебя будет происходить: сравнение миллионов строк или миллионы сравнений ограниченного количества строк? Во втором случае имхо подошла бы стратегия построения для каждой строки хэша.
Все-таки сравнивать хэши на неравенство поэффективнее будет.

2Valery: Да именно так... ошибся...
2ALL: Да мне нужен алгоритм... а написать я и на асме смогу и на сях..
-----------
Там просто есть какието битовые алгоритмы сравнения и на скока я знаю они быстрее всего работают...

Sourcer:
Не мути воду. Команда rep cmpsb будет работать заведомо быстрее любого битового алгоритма, если таковые существуют. Есть отдельный класс алгоритмов для посика подстрок в строке - это да. Но элементарной сравнение двух строк - это врядли. И действительно, поясни, что тебе нужно - сравнение одной строки со множеством других, или просто сравнение разных строк? Если первый случай, то, действительно, как предложил Valery, считай для строки Hash (например, CRС), после чего сравнивай их значения. Работать будет как из пушки. К томуже, если ты эти CRC еще и в деревце сбалансированное сложишь - то вообще будет супер.

если тебе нужно сравнить сотни тысяч или миллионы строк, то алгоритм сравнения будет занимать малую часть времени. тебе нужно обеспечить быстрый доступ к строкам.
кроме того, эффективность алгоритма будет зависить от длины строк.
если строки в несколько байт длиной, то эффективнее далать через MMX. к тому же комманды MMX выполняются параллельно с другими командами.

при использовании
repe cmpsb
нет необходимости высчитывать длины строк, сравнение будет закончено если найден ноль или разные байты.
можно попробовать
repe cmpsw
или
repe cmpsd
сравниваться будут сразу соответственно два или четыре байта. в конец строки при этом придется записать не менее трех нулевых байт(для cmpsw) или семи нулевых байт (для cmpsd)

вот-с:
_asm{
mov edi, p2;
mov esi, p1;
mov ecx, 16777216; // или из переменной
shr ecx, 3; // деление на 8
dec ecx; // уменьшение для первого сравнения

lp: movq mm0, [edi + ecx * 8]; // тут сррока №1
movq mm1, [esi + ecx * 8]; // тут строка №2
dec ecx;
pcmpeqd mm0, mm1; // сравнение сразу 8 байт
// если хоть один отличен - всё - одни 0
// иначе везде ff
movd eax, mm0; // грузим всё это в eax
prefetcht0 [esi + ecx * 8 - 64]
test al, al; // и тестим на 0
jz stp; // если 0 - всё, строки различены
prefetcht0 [edi + ecx * 8 - 64]
// иначе до упора
jnz lp;
stp: // тут мона ставить некий флажок или ещё что-то
}
_asm emms; // нужно обязательно
в три раза быстрее strcmp()
и в 2 чем вариант Flex Ferrum'a...
Just use this

тут в исходнике небольшая ошибочка - после dec ecx;
надо поставить
jz _exit;

Если строки хранить в виде дерева, то скорость поиска нужной строки не будет зависить от количества исходных строк.
В каждом узле дерева символ строки либо символ конца строки. Из узла указатель(указатели) на следующий символ.
Это дерево позволит организовать самый быстрый алгоритм поиска, и разница С/asm здесь уже не существенна.

Надо что-то типа этого:
int find_str(char* buf1,char* buf2,int len1,int len2)
{
int* i1=(int *)buf1;
int* i2=(int *)buf2;
register int t=0;
register int l;
if (len1<len2) l=len1/4; else l=len2/4;
while ((i1[t]==i2[t])&(t<=l)) t++;
return(t>l);
}

Только перед тем как в строки записывать данные желательно забить памят под неё нулями, хотябы 4 нуля (включая признак конца строки).
На самомо деле какой из алгоритмов самый быстрый будет зависить от конкретного случая, и выбирая алгоритм надо опираться на некоторую предположительную информацию о содержимом строк.

2VuDZ:
Чего-то команду "prefetcht0" мой VC6 никак не признает. Может подкинешь бинарный кодик для строк с ее использованием (prefetcht0 [esi + ecx * 8 - 64] и т.д.) ?

LOL
чего MMX никто не вспомнил?
кусок моей либы
BOOL CompareRowB(void *dest,
void *src,
DWORD size)
{
BOOL rtn=TRUE;
DWORD sz=size;
_asm{
pushad
mov esi,src
mov edi,dest
mov ecx,sz
cld
rep cmpsb
jz cmrqb //jmp quit if *src==*dest
mov rtn,FALSE
cmrqb:
emms
popad
}
return rtn;
}
BOOL CompareRowW(void *dest,
void *src,
DWORD size)
{
BOOL rtn=TRUE;
DWORD sz=size;
_asm{
pushad
mov esi,src
mov edi,dest
mov ecx,sz
cld
rep cmpsw
jz cmrqw //jmp quit if *src==*dest
mov rtn,FALSE
cmrqw:
emms
popad
}
return rtn;
}
BOOL CompareRowD(void *dest,
void *src,
DWORD size)
{
BOOL rtn=TRUE;
DWORD sz=size;
_asm{
pushad
mov esi,src
mov edi,dest
mov ecx,sz
cld
rep cmpsd
jz cmrqd //jmp quit if *src==*dest
mov rtn,FALSE
cmrqd:
emms
popad
}
return rtn;
}
BOOL CompareRowQ(void *dest,
void *src,
DWORD size)
{
BOOL rtn=TRUE;
DWORD sz=size;
_asm{
pushad
xor eax,eax
movd mm2,eax
mov edx,0xFFFFFFFF
mov esi,src
mov edi,dest
mov ecx,sz
mov ebx,8
cld
crql:
movq mm0,[esi]
add esi,ebx
movq mm1,[edi]
add edi,ebx
pcmpeqd mm0,mm1
packuswb mm0,mm2
movd eax,mm0
cmp eax,edx
jnz cmrqb
dec ecx
jz crql //jmp quit if *src==*dest

jmp cmrqb
mov rtn,FALSE
cmrqb:
emms
popad
}
return rtn;
}

BOOL CompareRowFastB(void *dest,
void *src,
DWORD size)
{
if (size==0)
return FALSE;
if (size>8)
{
if (CompareRowFastQ(dest,src,size>>3))
return TRUE;
if (CompareRowB((void*)((DWORD)dest+((size>>3)<<3)),(void*)((DWORD)src+((size>>3)<<3)),size\%8))
return TRUE;
}
else
return CompareRowB(dest,src,size);
return FALSE;
}

BOOL CompareRowFastW(void *dest,
void *src,
DWORD size)
{
if (size==0)
return FALSE;
if (size>4)
{
if (CompareRowFastQ(dest,src,size>>2))
return TRUE;
if (CompareRowW((void*)((DWORD)dest+((size>>2)<<3)),(void*)((DWORD)src+((size>>2)<<3)),size\%4))
return TRUE;
}
else
return CompareRowW(dest,src,size);
return FALSE;
}
BOOL CompareRowFastD(void *dest,
void *src,
DWORD size)
{
if (size==0)
return FALSE;
if (size>2)
{
if (CompareRowFastQ(dest,src,size>>1))
return TRUE;
if (CompareRowD((void*)((DWORD)dest+((size>>1)<<3)),(void*)((DWORD)src+((size>>1)<<3)),size\%2))
return TRUE;
}
else
return CompareRowD(dest,src,size);
return FALSE;
}

BOOL CompareRowFastQ(void *dest,
void *src,
DWORD size)
{
if (size==0)
return FALSE;

if (((DWORD)src\%8!=0) && (size>1))
{ //align src
if (CompareRowQ(dest,src,1))
return TRUE;
if (CompareRowQ((void*)((DWORD)dest+8-((DWORD)src\%8)),(void*)((DWORD)src+8-((DWORD)src\%8)),size-1))
return TRUE;
if (CompareRowB((void*)((DWORD)dest+(size-1)*8),(void*)((DWORD)src+(size-1)*8),(DWORD)src\%8))
return TRUE;
}
else
return CompareRowQ(dest,src,size);
return FALSE;
}

2x - pcmpeqd, prefetcht0 - это не ММХ?

ах, да, забыл....
это SSE

кстати, я тоже думал, что rep cmpsd быстрее, чем rep cmpsb, но после долгих сравнений обнаружил, что rep cmpsd в 4 раза медленнее... почему?

prefetch это не MMX=это SSE & 3DNow
и не нужен он совсем
да кста movd=варварство use movq

2x ты имел в виду
movd eax, mm0; ???
если да, то ню-ню...
кому то надо подучить асм

это похоже тебе надо его подучить если ты не знаешь что такое movd & movq

так как я (несколько) пьян отвечу так:
1. иди лесхозпромзоной (или ещё куды)
2. если ты сможешь скомпилить movq eax, mm0 я тебе памятник при жизни поставлю

Я бы для начала сравнил адресочки строк:
int _strcmp(const char *str1, const char *str2)
__asm {
push esi // нужно сохранить
push edi
mov esi, str1
mov edi, str2
cmp esi, edi
je _equal // адресок один и тот-же, отбой
...
сравниваем...
...
_equal:
pop edi
pop esi
}
На эту мысль меня натолкнул такой кусок программы:
int main() {
const char String1[] = "Тестируем...";
...
_strcmp(String1, "Тестируем..."); // Здесь мой VC6 запихивает в стек ОДИН И ТОТ-ЖЕ адрес для str1 и str2 !
...
}