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

Заранее извиняюсь если тема немного не туда, но вроде под вынь32.

Я из сети получаю пакет данных(обычный массив типа char*) и в нём надо найти кодовую последовательность.(например 55АА=) ). Причём код очень кретичен к скорости. (Сам знаю асм(но не очень хорошо), но надо писать на С++, поэтому наверно асмовская вставка). можно конечно банальным for'ом, но может есть решение поэлегантнее? Заранее спасибо

 

под вынь не знаю под Dos что то вроде

при условии что конец масива обозначается нулём

- если иначе то придётся указывать размер масива - и прогонять через цикл

Код (Text):

1. massiv db 'asdsadktw452984523945orgj mm cas;',55h,0AAh
2.        db 'fkhg dfmcssadax;sldk ma;dkadl; a;sdkfsa '    
3. ...
4. ...
5.           lea si,massiv       ;si на указатель масива
6. NexSymbol:lodsb               ;получаем в al символ
7.           or al,al            ;Код ноль?
8.           jz ExitFind         ;угу - сваливаем
9.           cmp al,55h          ;Первый символ нашей
10.                               ;последовательности?
11.           jnz NexSymbol       ;неа - идём смотреть следующий
12.           lodsb               ;да наш - получаем следующий
13.           cmp al,0AAh         ;следующий наш?
14.           jz Found            ;ага - нашли
15.           dec si              ;нет - уменьшаем указатель
16.           jmp NexSymbol       ;дальше
17. ExitFind:
18. ...
19. ...
20. ...
21. found:
22. ....
23. ....
24. ....
25.      

 

или так

Код (Text):

1.  
2. massiv db 'asdsadktw452984523945orgj mm cas;',55h,0AAh
3.        db 'fkhg dfmcssadax;sldk ma;dkadl; a;sdkfsa '    
4. ...
5. ...
6.           lea si,massiv       ;si на указатель масива
7. NexSymbol:lodsw               ;получаем в ax пару символов
8.           or al,al            ;У поледнего код ноль?
9.           jz ExitFind         ;угу - сваливаем
10.           cmp ax,0AA55h       ;Это оно?
11.           jz Found            ;Да - сваливаем
12.           dec si              ;нет - уменьшаем указатель
13.           jmp NexSymbol       ;продолжить поиск
14. ExitFind:
15. ...
16. ...
17. ...
18. found:
19. ....
20. ....
21. ....

 

Спасибо!=) последний вариант мне особенно понравился!=))

Интересно, а за сколько он успеет просмотреть 20000 байт?

(вопрос конечно глупый, но число тактов наверно приблезительно оценить можно)

 

eXod



Если искомая последовательность наверняка есть в массиве, то можно сделать короче и быстрее исключив проверку на окончание массива:

Код (Text):

1.     lea esi,massiv      ;esi на указатель масива
2. NexSymbol:lodsw         ;получаем в ax пару символов
3.     dec esi
4.     cmp ax,0AA55h       ;Это оно?
5.     jne short NexSymbol ;Нет - продолжаем
6. ExitFind:               ;Здесь окажемся когда найдено.
7.     ....

 

=) жаль вот только последовательности там может и не оказаться...

Может кто подскажет как можно замерить время выполнения программы? хочу стравнить разные варианты на асм вставках и на чистом с++=) может если скорость будет выше то в итоге вообще оставлю только описание функций/классов, а всё тело буду реализовывать на асме.(полностью к сожалению не получиться, другим надо класс встраивать в свою программку на с++)

 

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

http://algolist.manual.ru/search/esearch/index.php

 

Как испытать на время ? - Делаеш тестовую прогу с большим циклом этой продседуры. Запускаеш в Soft-ice и там показывается время исполнения.Получается что строчные инструкции и смена адресации тормозные (не испльзуй lodsb и word адресацию).

Код (Text):

1.  
2. start:
3. mov dword ptr [esi],eax
4. inc esi
5. cmp eax, '55AA' ; char
6. je  p1:1
7. inc esi
8. inc esi
9. inc esi
10. jmp start
11. p1:
12. mov byte ptr [esi],al
13. cmp al,'='
14. jne start
15.  

 

2Dr.Golova огромное спасибо за ссылку!!!!

2zzzyab дык софтайс ещё поставить надо... но помниться после перехода с 9х на НТ(2000) у меня так и не получилось его нормально поставить=( (в смясле не софтайс для 9х, а для НТ... на 2000 не хотел вставать). Может можно как-то программно(то бишь кодом в самой программе)?

 

eXod



поиск по форуму: RDTSС

 

Dr.Golova



Получается тот, кто не использует алгоритм Боуера-Мура ненормальный?



Для данного случая тогда может Алгоритм Сдвига-Или предпочтительней? Как раз для маленьких искомых последовательностей. По сравнению с Боуера-Мура он требует меньше времени как в худшем случае, так и в усредненном варианте.

 

Между прочим, поиск в строке реализован аппаратно - и по идее должен выполняться быстрее такой код:

Код (Text):

1.  
2.     _asm {
3.         mov eax, 0AA55h
4.         mov ecx, length    ;  в вордах!
5.         mov edi, pArray
6.         cld
7.         repne scasw
8.         setz al
9.         mov fFound, al
10.     }
11.  

 

_Juicy



К примеру, у меня такая строка:



pArray db AAh,55h,AAh,55h ...

 

Верно

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

 

Можно два раза прогнать

зачем? просто нужно scasb использовать...



Можно попробовать распараллелить процесс:

Код (Text):

1.  
2. in_str proc
3. ;вход:
4. ;edi - адрес строки
5. ;ecx - длина строки
6.  
7. ;выход:
8. ;не найдено - ecx==FALSE
9. ;найдено    - ecx!=FALSE, edi указывает на 0xAA55
10.  
11.     mov ax,0AA55h
12.     lea ecx,[edi+(ecx-1)-3]
13.  
14.     cmp edi,ecx
15.     jae eo_long
16. @@:
17.     cmp [edi],ax
18.     je at0
19.     cmp [edi+1],ax
20.     je at1
21.     cmp [edi+2],ax
22.     je at2
23.     cmp [edi+3],ax
24.     je at3
25.     add edi,4
26.     cmp edi,ecx
27.     jc @B       ;достаточно больших циклов
28. eo_long:
29.  
30.     add ecx,3
31.     sub ecx,edi
32.     je eo_short
33. @@:
34.     cmp [edi+ecx-1],ax ;не факт, что мы найдем первое!
35.     je atECX
36.     dec ecx
37.     jne @B
38. eo_short:
39.     ret
40.  
41. atECX:
42.      lea edi,[edi+ecx-1]
43.      ret
44. at3:    inc edi
45. at2:    inc edi
46. at1:    inc edi
47. at0:    ret
48. in_str endp
49.  

должно быть быстрее в разы,.. хотя не знаю как там scasb работает...

 

Если использовать scasb, придется дополнительно проверять второй байт.

 

придется дополнительно проверять второй байт

Да и еще ecx на ноль, но это же лучше двух проходов

 

Если размер строки большой (мегабайты) нужно оптимизировать под кеш - сначала читать блок, скажем 128Кб, потом уже искать в нём каким нибудь хитрым способом.

А тут же маленький пакет, просто тупо искать:

Код (Text):

1.        mov    esi, pointer_to_string
2.        mov    edx,  0AA55h
3.        align  16
4. loop:  movzx  eax, word[esi] ; именно так
5.        inc    esi
6.        cmp    eax, edx
7.        jz     found
8.        test   al, al
9.        jnz    loop      

zzzyab



Оригинальный способ заполнения области памяти .

 

Скорее байт - линейка обычно 64 байта. Пока просматриваем одну нужно делать prefetch на следующую, и т.д. Наверно так...



...Да и ecx на ноль после scasbа все-таки можно не проверять, если в конец строки записать например 0

 

boozook >

IMHO не будет оно быстрее, там куча 16-битных операций над невыровненными данными ( cmp [edi],ax )





Параллелить, это как-нибудь так (без учёта длины!):

Код (Text):

1. .1:     mov     eax, [esi]
2. .2:     add     esi, 4
3.  
4.         xor     eax, 55555555h
5.         lea     edx, [eax-01010101h]
6.         not     eax
7.         and     edx, 80808080h
8.         and     edx, eax
9.         jz      .1
10.  
11.         lea     ebx, [eax-01010101h]
12.         not     eax
13.         and     ebx, 80808080h
14.         and     ebx, eax
15.         jnz     доп_проверка    ; DWORD содержит одновременно 55h и 0AAh
16.                                 ; нужно отдельно проверить, что это именно 55h[b],[/b]AAh, но мне лень :)
17.  
18.         ; вариант пересечения DWORD
19.         test    edx, edx
20.         mov     eax [esi]
21.         jns     .2
22.         cmp     al, 0AAh
23.         jz      .2
24. found: