Jaki jest najszybszy algorytm wyszukiwania podciągów?


165

OK, więc nie brzmię jak idiota, mam zamiar określić problem / wymagania dokładniej:

  • Igła (wzór) i stóg siana (tekst do wyszukania) to ciągi zakończone znakiem C w stylu C. Brak informacji o długości; w razie potrzeby należy ją obliczyć.
  • Funkcja powinna zwrócić wskaźnik do pierwszego dopasowania lub NULLjeśli nie zostanie znalezione żadne dopasowanie.
  • Przypadki niepowodzenia są niedozwolone. Oznacza to, że każdy algorytm z niestałymi (lub dużymi stałymi) wymaganiami dotyczącymi pamięci masowej będzie musiał mieć przypadek rezerwowy dla błędu alokacji (a wydajność w opiece rezerwowej przyczynia się w ten sposób do wydajności w najgorszym przypadku).
  • Implementacja ma być w C, chociaż dobry opis algorytmu (lub link do takiego algorytmu) bez kodu też jest w porządku.

... a także to, co mam na myśli przez „najszybszy”:

  • Deterministyczne O(n)gdzie n= długość stogu siana. (Ale może być możliwe użycie pomysłów z algorytmów, które są normalnie O(nm)(na przykład toczący się hash), jeśli są połączone z bardziej niezawodnym algorytmem, aby dać deterministyczne O(n)wyniki).
  • Nigdy nie działa (wymiernie; kilka zegarów if (!needle[1])itp. Jest w porządku) gorzej niż naiwny algorytm brutalnej siły, szczególnie na bardzo krótkich igłach, które są prawdopodobnie najczęstszym przypadkiem. (Bezwarunkowe, duże obciążenie wstępne przetwarzania jest złe, podobnie jak próba poprawy współczynnika liniowego dla patologicznych igieł kosztem prawdopodobnych igieł).
  • Biorąc pod uwagę dowolną igłę i stóg siana, porównywalna lub lepsza wydajność (nie gorsza niż 50% dłuższy czas wyszukiwania) w porównaniu z jakimkolwiek innym szeroko stosowanym algorytmem.
  • Poza tymi warunkami zostawiam definicję „najszybszego” otwartego. Dobra odpowiedź powinna wyjaśniać, dlaczego uważasz proponowane podejście za „najszybsze”.

Moja obecna implementacja działa mniej więcej od 10% wolniej do 8 razy szybciej (w zależności od danych wejściowych) niż implementacja dwukierunkowa glibc.

Aktualizacja: mój aktualny optymalny algorytm jest następujący:

  • W przypadku igieł o długości 1 użyj strchr.
  • W przypadku igieł o długości 2-4 użyj słów maszynowych, aby porównać 2-4 bajty naraz w następujący sposób: Wstępnie załaduj igłę 16- lub 32-bitową liczbą całkowitą z przesunięciami bitów i przełączaj stary bajt / nowe bajty ze stosu siana w każdej iteracji . Każdy bajt stogu siana jest odczytywany dokładnie raz i podlega sprawdzeniu względem 0 (koniec ciągu) i jednym 16- lub 32-bitowym porównaniem.
  • W przypadku igieł o długości> 4 użyj algorytmu dwukierunkowego ze złą tabelą zmian (np. Boyer-Moore), która jest stosowana tylko do ostatniego bajtu okna. Aby uniknąć narzutu inicjalizacji tabeli 1kb, co byłoby stratą netto dla wielu igieł o średniej długości, zachowuję tablicę bitową (32 bajty) oznaczającą, które wpisy w tabeli przesunięć są inicjalizowane. Bity, które nie są ustawione, odpowiadają wartościom bajtów, które nigdy nie pojawiają się w igle, dla których możliwe jest przesunięcie o pełną długość igły.

Najważniejsze pytania, jakie mam w głowie, to:

  • Czy istnieje sposób na lepsze wykorzystanie złego stołu zmiany biegów? Boyer-Moore najlepiej go wykorzystuje, skanując do tyłu (od prawej do lewej), ale dwukierunkowy wymaga skanowania od lewej do prawej.
  • Jedyne dwa realne algorytmy kandydatów, które znalazłem dla ogólnego przypadku (brak warunków braku pamięci lub kwadratowych wydajności), to dwukierunkowe i dopasowywanie ciągów w uporządkowanych alfabetach . Ale czy istnieją łatwe do wykrycia przypadki, w których różne algorytmy byłyby optymalne? Z pewnością wiele z algorytmów kosmicznych O(m)(gdzie mjest długość igły) można by użyć do m<100lub czegoś podobnego. Byłoby również możliwe użycie algorytmów, które są w najgorszym przypadku kwadratowe, jeśli istnieje łatwy test dla igieł, który, jak można udowodnić, wymaga tylko czasu liniowego.

Punkty bonusowe za:

  • Czy możesz poprawić wydajność, zakładając, że zarówno igła, jak i stóg siana są dobrze uformowane w UTF-8? (Przy znakach o różnych długościach bajtów, dobrze uformowana struktura narzuca pewne wymagania dotyczące wyrównania łańcucha między igłą a stogiem siana i umożliwia automatyczne przesunięcie o 2-4 bajty w przypadku napotkania niedopasowania bajtu głowy. Ale czy te ograniczenia kupują wiele / cokolwiek poza tym, co maksymalne obliczenia sufiksów, dobre przesunięcia sufiksów itp. już dają Ci różne algorytmy?)

Uwaga: dobrze znam większość dostępnych algorytmów, ale nie wiem, jak dobrze działają w praktyce. Oto dobre odniesienie, aby ludzie nie podawali mi referencji na temat algorytmów jako komentarzy / odpowiedzi: http://www-igm.univ-mlv.fr/~lecroq/string/index.html


Istnieje wiele algorytmów wyszukiwania ciągów wymienionych w sekcji Algorytmy na ciągach . Możesz opisać, które algorytmy rozważałeś z tej listy.
Greg Hewgill

61
Ten link na końcu jest złoty!
Carlos

4
Nie mogę uwierzyć, że nadal nie zaakceptowałeś odpowiedzi.
użytkownik541686

1
@Mehrdad: Już miałem powiedzieć, że nie ma odpowiedzi, które naprawdę odnoszą się do zadanego pytania, ale wydaje się, że twoja. W momencie, w którym odpowiedziałeś, poszedłem dalej i zostawiłem dalsze ulepszenia strstrna później, więc tak naprawdę nie zabrałem się za prawidłowe przeczytanie artykułu, który łączysz, ale brzmi to bardzo obiecująco. Dziękuję i przepraszam, że nie oddzwoniłem.
R .. GitHub PRZESTAŃ POMÓC W LODZIE

Odpowiedzi:


37

Zbuduj bibliotekę testową prawdopodobnych igieł i stogów siana. Profiluj testy kilku algorytmów wyszukiwania, w tym brutalnej siły. Wybierz ten, który najlepiej sprawdza się z Twoimi danymi.

Boyer-Moore używa złej tabeli znaków z dobrą tabelą sufiksów.

Boyer-Moore-Horspool używa złej tabeli znaków.

Knuth-Morris-Pratt używa częściowej tabeli odpowiedników.

Rabin-Karp używa uruchomionych skrótów.

Wszyscy oni zamieniają się na mniejsze porównania w różnym stopniu, więc rzeczywiste wyniki będą zależeć od średniej długości igły i stogu siana. Im więcej początkowych narzutów, tym lepiej przy dłuższych wejściach. Przy bardzo krótkich igłach może wygrać brutalna siła.

Edytować:

Do znajdowania par zasad, wyrażeń angielskich lub pojedynczych słów może być najlepszy inny algorytm. Gdyby istniał jeden najlepszy algorytm dla wszystkich danych wejściowych, zostałby opublikowany.

Pomyśl o poniższej małej tabeli. Każdy znak zapytania może mieć inny najlepszy algorytm wyszukiwania.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

To naprawdę powinien być wykres z zakresem krótszych lub dłuższych danych wejściowych na każdej osi. Gdybyś wykreślił każdy algorytm na takim wykresie, każdy miałby inną sygnaturę. Niektóre algorytmy cierpią z powodu dużej liczby powtórzeń we wzorcu, co może wpływać na zastosowania takie jak wyszukiwanie genów. Niektóre inne czynniki, które wpływają na ogólną wydajność, obejmują wyszukiwanie tego samego wzorca więcej niż jeden raz i jednoczesne wyszukiwanie różnych wzorców.

Gdybym potrzebował przykładowego zestawu, myślę, że zeskrobałbym witrynę taką jak Google lub Wikipedia, a następnie usunąłbym kod HTML ze wszystkich stron wyników. W przypadku witryny wyszukiwania wpisz słowo, a następnie użyj jednego z sugerowanych wyszukiwanych słów. W razie potrzeby wybierz kilka różnych języków. Korzystając ze stron internetowych, wszystkie teksty byłyby krótkie lub średnie, więc połącz wystarczającą liczbę stron, aby uzyskać dłuższe teksty. Możesz również znaleźć książki należące do domeny publicznej, dokumenty prawne i inne duże zbiory tekstów. Lub po prostu generuj losową treść, wybierając słowa ze słownika. Ale celem profilowania jest sprawdzenie pod kątem rodzaju treści, które będziesz przeszukiwać, więc jeśli to możliwe, używaj próbek ze świata rzeczywistego.

Zostawiłem krótko i długo niejasne. Jeśli chodzi o igłę, myślę, że krótka ma mniej niż 8 znaków, średnia to mniej niż 64 znaki, a długość poniżej 1 tys. Jeśli chodzi o stóg siana, myślę, że krótki to mniej niż 2 ^ 10, średni - mniej niż 2 ^ 20, a długi - maksymalnie 2 ^ 30 znaków.


1
Czy masz dobre sugestie dotyczące biblioteki testowej? Poprzednie pytanie, które zadałem na SO było z tym związane i nigdy nie otrzymałem żadnych prawdziwych odpowiedzi. (poza moim własnym ...) Powinien być obszerny. Nawet jeśli moim pomysłem na aplikację dla strstr jest przeszukiwanie tekstu w języku angielskim, ktoś inny może szukać genów w sekwencjach par zasad ...
R .. GitHub STOP HELPING ICE

3
To trochę bardziej skomplikowane niż krótkie / długie. W przypadku igły najważniejsze pytania dotyczące wydajności większości algorytmów to: Długość? Czy jest jakaś okresowość? Czy igła zawiera wszystkie unikalne znaki (bez powtórzeń)? A może ta sama postać? Czy w stogu siana jest duża liczba postaci, które nigdy nie pojawiają się w igle? Czy jest szansa, że ​​będziesz musiał poradzić sobie z igłami dostarczonymi przez atakującego, który chce wykorzystać wydajność w najgorszym przypadku, aby sparaliżować Twój system? Itd ..
R .. GitHub STOP POMOC LODOWI

31

Wydany w 2011 roku wydaje mi się, że może to być algorytm „Prostego dopasowania ciągów w przestrzeni stałej w czasie rzeczywistym” autorstwa Dany'ego Breslauera, Roberto Grossiego i Filippo Mignosi.

Aktualizacja:

W 2014 roku autorzy opublikowali następujące ulepszenie: W kierunku optymalnego dopasowania upakowanych ciągów .


1
Wow dzięki. Czytam gazetę. Jeśli okaże się lepszy niż to, co mam, na pewno przyjmuję twoją odpowiedź.
R .. GitHub STOP HELPING ICE

1
@R ..: Jasne! :) A propos, jeśli uda Ci się zaimplementować algorytm, rozważ opublikowanie go na StackOverflow, aby każdy mógł z niego skorzystać! Nigdzie nie znalazłem jego implementacji i nie jestem dobry we wdrażaniu algorytmów, które znajduję w artykułach naukowych haha.
user541686

2
Jest to wariant algorytmu „dwukierunkowego”, którego już używam, więc dostosowanie mojego kodu do tego może być łatwe. Muszę jednak przeczytać artykuł bardziej szczegółowo, aby mieć pewność, i muszę ocenić, czy wprowadzone zmiany są zgodne z moim użyciem „tabeli złych znaków”, co znacznie przyspiesza typowy przypadek.
R .. GitHub PRZESTAŃ POMÓC W LODZIE

11
I nadal nie zaakceptowałeś odpowiedzi @ Mehrdad! :-)
lifebalance

3
@DavidWallace: Co? Zawiera tytuły artykułów i autorów. Nawet jeśli link zniknie, możesz znaleźć dokumenty. Czego ode mnie oczekujesz, napiszę pseudokod dla algorytmu? Dlaczego myślisz, że rozumiem algorytm?
user541686

23

http://www-igm.univ-mlv.fr/~lecroq/string/index.html odwołuje wskazaniu jest doskonałym źródłem i podsumowanie niektóre z najbardziej znanych i badanych algorytmów dopasowywania smyczkowych.

Rozwiązania większości problemów związanych z wyszukiwaniem obejmują kompromisy związane z narzutem wstępnego przetwarzania, wymaganiami czasowymi i przestrzennymi. Żaden pojedynczy algorytm nie będzie optymalny ani praktyczny we wszystkich przypadkach.

Jeśli Twoim celem jest zaprojektowanie określonego algorytmu wyszukiwania ciągów, zignoruj ​​resztę tego, co mam do powiedzenia, jeśli chcesz opracować uogólnioną procedurę wyszukiwania ciągów znaków, spróbuj wykonać następujące czynności:

Poświęć trochę czasu na przejrzenie konkretnych mocnych i słabych stron algorytmów, do których już się odnosisz. Przeprowadź przegląd w celu znalezienia zestawu algorytmów obejmujących zakres i zakres wyszukiwań ciągów, które Cię interesują. Następnie zbuduj selektor wyszukiwania interfejsu użytkownika w oparciu o funkcję klasyfikatora, aby wskazać najlepszy algorytm dla danych wejściowych. W ten sposób możesz zastosować najbardziej wydajny algorytm do wykonania zadania. Jest to szczególnie skuteczne, gdy algorytm jest bardzo dobry w przypadku niektórych wyszukiwań, ale słabo się psuje. Na przykład brutalna siła jest prawdopodobnie najlepsza w przypadku igieł o długości 1, ale szybko ulega degradacji wraz ze wzrostem długości igły, po czym algoritim sustik-mooremogą stać się bardziej wydajne (w przypadku małych alfabetów), wtedy dla dłuższych igieł i większych alfabetów algorytmy KMP lub Boyer-Moore mogą być lepsze. To tylko przykłady ilustrujące możliwą strategię.

Podejście oparte na wielu algorytmach nie jest nowym pomysłem. Wydaje mi się, że był używany przez kilka komercyjnych pakietów Sort / Search (np. SYNCSORT powszechnie używany na komputerach mainframe implementuje kilka algorytmów sortowania i używa heurystyki, aby wybrać „najlepszy” dla danych wejściowych)

Każdy algorytm wyszukiwania występuje w kilku odmianach, które mogą znacząco różnić się jego wydajnością, jak na przykład w tym artykule ilustruje .

Porównaj swoją usługę, aby skategoryzować obszary, w których potrzebne są dodatkowe strategie wyszukiwania, lub aby bardziej efektywnie dostroić funkcję selektora. To podejście nie jest szybkie ani łatwe, ale jeśli zostanie wykonane dobrze, może przynieść bardzo dobre wyniki.


1
Dziękuję za odpowiedź, zwłaszcza link do Sustik-Moore, którego wcześniej nie widziałem. Podejście oparte na wielu algorytmach jest z pewnością w powszechnym użyciu. Glibc zasadniczo robi strchr, dwukierunkową bez złej tablicy przesunięć znaków lub dwukierunkową ze złą tabelą przesunięć znaków, w zależności od tego, czy needle_len to 1, <32 czy> 32. Moje obecne podejście jest takie samo, z tym wyjątkiem, że zawsze używam tabeli zmian; Zastąpiłem 1kb memset niezbędny do tego 32-bajtowym zestawem memset na zbiorze bitów używanym do zaznaczenia, które elementy tabeli zostały zainicjowane, i otrzymuję korzyść (ale nie narzut) nawet dla małych igieł.
R .. GitHub PRZESTAŃ POMÓC NA LODZIE

1
Po przemyśleniu jestem naprawdę ciekawy, jaka jest przeznaczona aplikacja dla Sustik-Moore. Z małymi alfabetami nigdy nie dokonasz żadnych znaczących przesunięć (wszystkie znaki alfabetu prawie na pewno pojawią się blisko końca igły), a metody automatów skończonych są bardzo wydajne (mała tablica przejść stanów). Więc nie mogę sobie wyobrazić scenariusza, w którym Sustik-Moore mógłby być optymalny ...
R .. GitHub STOP HELPING ICE

świetna odpowiedź - gdybym mógł zagrać tę konkretną odpowiedź, zrobiłbym to.
Jason S,

1
@R .. Teoria stojąca za algorytmem sustik-moore jest taka, że ​​powinien on dawać większe średnie wartości przesunięcia, gdy igła jest stosunkowo duża, a alfabet jest stosunkowo mały (np. Wyszukiwanie sekwencji DNA). Większy w tym przypadku oznacza po prostu większy niż podstawowy algorytm Boyera-Moore'a przy tych samych danych wejściowych. Trudno powiedzieć, o ile bardziej efektywne jest to w porównaniu z podejściem automatów skończonych lub jakąś inną odmianą Boyera-Moore'a (których jest wiele). Dlatego podkreśliłem, że poświęciłem trochę czasu na zbadanie konkretnych mocnych / słabych stron algorytmów kandydatów.
NealB,

1
Hm, myślę, że utknąłem, myśląc o zmianach tylko w sensie złych zmian charakteru z Boyer-Moore. Jednak dzięki poprawie w zakresie przesunięć przyrostków BM, Sustik-Moore mógłby prawdopodobnie przewyższyć podejścia DFA do wyszukiwania DNA. Schludne rzeczy.
R .. GitHub PRZESTAŃ POMÓC W LODZIE

21

Byłem zaskoczony, widząc nasz raport techniczny cytowany w tej dyskusji; Jestem jednym z autorów algorytmu, który powyżej nazwano Sustik-Moore. (Nie używaliśmy tego terminu w naszym artykule).

Chciałem tutaj podkreślić, że dla mnie najbardziej interesującą cechą algorytmu jest to, że dość łatwo jest udowodnić, że każda litera jest badana najwyżej raz. W przypadku wcześniejszych wersji Boyer-Moore udowodnili, że każdy list jest badany najwyżej 3, a później najwyżej 2 razy, a dowody te były bardziej skomplikowane (patrz cytaty w artykule). Dlatego też dostrzegam wartość dydaktyczną w przedstawianiu / studiowaniu tego wariantu.

W artykule opisujemy również dalsze warianty, które są ukierunkowane na efektywność, jednocześnie zmniejszając gwarancje teoretyczne. Jest to krótka praca, a materiał moim zdaniem powinien być zrozumiały dla przeciętnego maturzysty.

Naszym głównym celem było zwrócenie uwagi na tę wersję innym, którzy mogą ją dalej ulepszać. Przeszukiwanie ciągów znaków ma tak wiele odmian i sami nie jesteśmy w stanie wymyślić wszystkich, w których ten pomysł mógłby przynieść korzyści. (Stały tekst i zmieniający się wzorzec, stały wzorzec inny tekst, przetwarzanie wstępne możliwe / niemożliwe, wykonywanie równoległe, znajdowanie pasujących podzbiorów w dużych tekstach, zezwalanie na błędy, bliskie dopasowania itp.)


1
Czy wiesz o dostępnej implementacji C lub C ++? Myślę o użyciu tego do wyszukiwania motywów DNA (dokładne dopasowanie motywu). Jeśli nie, może spróbuję samodzielnie stworzyć implementację i
przesłać

4
Przy braku znanej dostępnej implementacji algorytm Sustik-Moore / 2BLOCK wydaje się mało prawdopodobny do zastosowania w praktyce i nadal jest pomijany w wynikach w artykułach podsumowujących, takich jak „The Exact String Matching Problem: a Comprehensive Experimental Evaluation”
JDiMatteo

18

Najszybszy algorytm wyszukiwania podciągów będzie zależał od kontekstu:

  1. wielkość alfabetu (np. DNA vs angielski)
  2. długość igły

Artykuł z 2010 r. „The Exact String Matching Problem: a Comprehensive Experimental Evaluation” podaje tabele z czasem wykonywania dla 51 algorytmów (z różnymi rozmiarami alfabetu i długościami igieł), dzięki czemu można wybrać najlepszy algorytm do swojego kontekstu.

Wszystkie te algorytmy mają implementacje C, a także zestaw testów, tutaj:

http://www.dmi.unict.it/~faro/smart/algorithms.php


4

Naprawdę dobre pytanie. Po prostu dodaj małe kawałki ...

  1. Ktoś mówił o dopasowywaniu sekwencji DNA. Ale w przypadku sekwencji DNA zwykle budujemy strukturę danych (np. Tablicę sufiksów, drzewo sufiksów lub indeks FM) dla stogu siana i dopasowujemy do niej wiele igieł. To jest inne pytanie.

  2. Byłoby naprawdę świetnie, gdyby ktoś chciał porównać różne algorytmy. Istnieją bardzo dobre testy porównawcze dotyczące kompresji i konstrukcji tablic przyrostków, ale nie widziałem testu porównawczego dopasowywania ciągów. Potencjalni kandydaci na stóg siana mogą pochodzić z testu porównawczego SACA .

  3. Kilka dni temu testowałem implementację Boyer-Moore ze strony, którą poleciłeś (EDYCJA: potrzebuję wywołania funkcji jak memmem (), ale nie jest to funkcja standardowa, więc zdecydowałem się ją zaimplementować). Mój program do testów porównawczych wykorzystuje losowy stóg siana. Wygląda na to, że implementacja Boyer-Moore na tej stronie jest razy szybsza niż memmem () glibc i strnstr () Maca. Jeśli jesteś zainteresowany, implementacja jest tutaj, a kod do testów porównawczych jest tutaj . To zdecydowanie nie jest realistyczny punkt odniesienia, ale to początek.


Jeśli masz jakieś dobre igły do ​​przetestowania wraz z kandydatami do stogów siana z testu porównawczego SACA, opublikuj je jako odpowiedź na moje drugie pytanie i, oprócz uzyskania lepszej odpowiedzi, oznaczę je jako zaakceptowane.
R .. GitHub PRZESTAŃ POMÓC NA LODZIE

3
Jeśli chodzi o twoją pamięć i Boyer-Moore, jest bardzo prawdopodobne, że Boyer-Moore (a raczej jedno z ulepszeń Boyer-Moore) będzie działał najlepiej na losowych danych. Dane losowe mają wyjątkowo niskie prawdopodobieństwo okresowości i długich częściowych dopasowań, które prowadzą do kwadratowego najgorszego przypadku. Szukam sposobu, aby połączyć Boyer-Moore i Two-Way lub skutecznie wykryć, kiedy Boyer-Moore jest „bezpieczny w użyciu”, ale jak dotąd nie odniosłem żadnego sukcesu. Swoją drogą nie użyłbym memmem glibc jako porównania. Moja implementacja tego samego algorytmu co glibc jest kilka razy szybsza.
R .. GitHub PRZESTAŃ POMÓC NA LODZIE

Jak powiedziałem, to nie jest moja realizacja. Podziękowania dla Christiana Charrasa i Thierry'ego Lecroqa. Mogę sobie wyobrazić, dlaczego losowe dane wejściowe są złe dla testów porównawczych i jestem pewien, że glibc wybiera algorytmy z powodów. Myślę też, że memmem () nie jest efektywnie zaimplementowane. Spróbuję. Dzięki.
user172818

4

Wiem, że to stare pytanie, ale większość złych tabel zmian to pojedynczy znak. Jeśli ma to sens dla twojego zbioru danych (np. Szczególnie jeśli jest to napisane słowa) i jeśli masz dostępne miejsce, możesz uzyskać dramatyczne przyspieszenie, używając złej tabeli zmiany biegów złożonej z n-gramów, a nie pojedynczych znaków.


3

Użyj stdlib strstr:

char *foundit = strstr(haystack, needle);

Było bardzo szybkie, pisanie zajęło mi tylko około 5 sekund.


26
A jeśli przeczytasz moje pytanie, zobaczysz, że miałem dość łatwy czas, aby go wyprzedzić. Podoba mi się twój sarkazm, ale pominę -1.
R .. GitHub PRZESTAŃ POMÓC NA LODZIE


3

Szybszy strchralgorytm „Wyszukaj jeden pasujący znak” (ala ).

Ważne notatki:

  • Te funkcje używają gcckompilatora wewnętrznego „liczba / liczba (wiodących | końcowych) zer” kompilatora __builtin_ctz. Te funkcje będą prawdopodobnie działać szybko tylko na maszynach, które mają instrukcje, które wykonują tę operację (np. X86, ppc, arm).

  • Te funkcje zakładają, że architektura docelowa może wykonywać niewyrównane obciążenia 32- i 64-bitowe. Jeśli twoja docelowa architektura tego nie obsługuje, będziesz musiał dodać trochę logiki startowej, aby odpowiednio wyrównać odczyty.

  • Te funkcje są niezależne od procesora. Jeśli docelowy procesor ma instrukcje wektorowe, możesz zrobić (znacznie) lepiej. Na przykład strlenponiższa funkcja używa SSE3 i może być w prosty sposób zmodyfikowana do XOR skanowanych bajtów w celu wyszukania bajtu innego niż 0. Testy porównawcze przeprowadzone na laptopie 2,66 GHz Core 2 z systemem Mac OS X 10.6 (x86_64):

    • 843,433 MB / s dla strchr
    • 2656,742 MB / s dla findFirstByte64
    • 13094,479 MB / s dla strlen

... wersja 32-bitowa:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

... i wersja 64-bitowa:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

Edycja 2011/06/04 OP zwraca uwagę w komentarzach, że to rozwiązanie ma „błąd nie do przezwyciężenia”:

może czytać poza poszukiwanym bajtem lub zakończeniem zerowym, który mógłby uzyskać dostęp do niezamapowanej strony lub strony bez prawa odczytu. Po prostu nie możesz używać dużych odczytów w funkcjach łańcuchowych, chyba że są wyrównane.

Jest to technicznie prawda, ale dotyczy praktycznie każdego algorytmu, który działa na fragmentach większych niż jeden bajt, w tym metody sugerowanej przez OP w komentarzach:

Typowa strchrimplementacja nie jest naiwna, ale trochę wydajniejsza niż to, co podałeś. Zobacz koniec tego, aby zapoznać się z najczęściej używanym algorytmem: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

To też naprawdę nie ma nic wspólnego z wyrównaniem jako takim . To prawda, może to potencjalnie spowodować zachowanie omówione na większości powszechnie używanych architektur, ale ma to więcej wspólnego ze szczegółami implementacji mikroarchitektury - jeśli niewyrównany odczyt przekracza granicę 4K (znowu, typowo), to odczyt spowoduje program przerywanie błędu, jeśli następna granica strony 4K nie jest odwzorowana.

Ale to nie jest „błąd” w algorytmie podanym w odpowiedzi - takie zachowanie jest spowodowane tym, że funkcje lubią strchri strlennie akceptują lengthargumentu ograniczającego rozmiar wyszukiwania. Wyszukiwanie char bytes[1] = {0x55};, które dla celów naszej dyskusji tak się składa, że ​​znajduje się na samym końcu granicy strony maszyny wirtualnej 4K, a następna strona nie jest odwzorowana, z strchr(bytes, 0xAA)(gdzie strchrjest implementacja bajt po czasie), zakończy się dokładnie ta sama droga. To samo dotyczy strchrpokrewnego kuzynastrlen .

Bez lengthargumentu nie ma sposobu, aby stwierdzić, kiedy należy wyłączyć szybki algorytm i wrócić do algorytmu bajt po bajcie. O wiele bardziej prawdopodobnym „błędem” byłoby odczytanie „przekraczającego rozmiar alokacji”, co technicznie skutkuje undefined behaviorzgodnie z różnymi standardami języka C i zostałby oznaczony jako błąd przez coś podobnego valgrind.

Podsumowując, wszystko, co działa na fragmentach większych niż bajty, działa szybciej, jak ten kod odpowiada i kod wskazany przez OP, ale musi mieć semantykę odczytu z dokładnością do bajtów, prawdopodobnie będzie „błędne”, jeśli nie ma lengthargumentu kontrolować narożne przypadki „ostatniego odczytu”.

Kod w tej odpowiedzi jest jądrem umożliwiającym szybkie znalezienie pierwszego bajtu w porcji o naturalnym rozmiarze słowa procesora, jeśli docelowy procesor ma ctzinstrukcje podobne do szybkich . Dodanie takich rzeczy, jak upewnienie się, że działa tylko na prawidłowo wyrównanych granicach naturalnych lub jakiejś formie lengthograniczenia, które pozwoliłoby na wyjście z szybkiego jądra do wolniejszego sprawdzania bajt po bajcie, jest trywialne .

PO stwierdza również w komentarzach:

Jeśli chodzi o optymalizację ctz, ma to znaczenie tylko dla operacji ogona O (1). Mogłoby to poprawić wydajność przy małych strunach (np. strchr("abc", 'a');Ale na pewno nie przy strunach o dowolnym większym rozmiarze.

To, czy to stwierdzenie jest prawdziwe, zależy w dużej mierze od danej mikroarchitektury. Używając kanonicznego 4-stopniowego modelu potoku RISC, jest to prawie na pewno prawda. Jednak niezwykle trudno jest stwierdzić, czy jest to prawdą w przypadku współczesnego niesprawnego superskalarnego procesora, w którym prędkość rdzenia może całkowicie przyćmić szybkość przesyłania strumieniowego pamięci. W tym przypadku jest nie tylko prawdopodobne, ale dość powszechne, że istnieje duża luka w „liczbie instrukcji, które można wycofać” w stosunku do „liczby bajtów, które mogą być przesyłane strumieniowo”, tak że masz „ liczba instrukcji, które można wycofać dla każdego bajtu, który może być przesyłany strumieniowo ”. Jeśli jest wystarczająco duży, instrukcję ctz+ shift można wykonać „za darmo”.


„W przypadku igieł o długości 1 użyj strchr.” - Pytałeś o najszybszy algorytm wyszukiwania podciągów. Znalezienie podciągu o długości 1 to tylko szczególny przypadek, który można również zoptymalizować. Jeśli zamienisz swój obecny kod przypadku specjalnego na podciągi o długości 1 ( strchr) czymś podobnym do powyższego, sprawy (prawdopodobnie, w zależności od tego, jak strchrzostanie zaimplementowane) pójdą szybciej. Powyższy algorytm jest prawie 3x szybszy niż typowa naiwna strchrimplementacja.
johne

2
OP powiedział, że łańcuch został poprawnie zakończony z wartością null, więc twoja dyskusja na ten temat char bytes[1] = {0x55};jest nieistotna. Bardzo istotny jest twój komentarz, że jest to prawdą dla każdego algorytmu odczytu słów, który nie zna wcześniej długości.
Seth Robertson

1
Problem nie dotyczy wersji, którą cytowałem, ponieważ używasz jej tylko na wyrównanych wskaźnikach - przynajmniej tak robią poprawne implementacje.
R .. GitHub PRZESTAŃ POMÓC W LODZIE

2
@R, nie ma to nic wspólnego z „wyrównanymi wskaźnikami”. Hipotetycznie, jeśli masz architekturę, która obsługuje ochronę maszyn wirtualnych z szczegółowością na poziomie bajtów, a każda mallocalokacja była „dostatecznie dopełniona” po obu stronach, a system maszyny wirtualnej wymusił szczegółową ochronę bajtów dla tej alokacji… niezależnie od tego, czy wskaźnik jest wyrównany ( zakładając trywialne 32-bitowe intnaturalne wyrównanie) jest dyskusyjne - nadal istnieje możliwość, aby ten wyrównany odczyt odczytał poza rozmiar alokacji. KAŻDY odczyt powyżej rozmiaru alokacji jest undefined behavior.
johne

5
@johne: +1 do komentarza. Koncepcyjnie masz rację, ale rzeczywistość jest taka, że ​​zabezpieczenia granularności bajtów są tak drogie zarówno w przechowywaniu, jak i egzekwowaniu, że nie istnieją i nigdy nie będą istnieć. Jeśli wiesz, że podstawowy magazyn to mapowania szczegółowości strony uzyskane z odpowiednika mmap, wyrównanie jest wystarczające.
R .. GitHub PRZESTAŃ POMÓC W LODZIE

3

Po prostu wyszukaj „najszybszy strstr”, a jeśli zobaczysz coś interesującego, zapytaj mnie.

Moim zdaniem nakładasz na siebie zbyt wiele ograniczeń (tak, wszyscy chcemy subliniowej liniowości w wyszukiwarce max), jednak potrzeba prawdziwego programisty, aby wkroczyć, do tego czasu myślę, że podejście hash jest po prostu sprytnym rozwiązaniem ( dobrze wzmocniony przez BNDM dla krótszych wzorów 2..16).

Tylko krótki przykład:

Przeprowadzenie wyszukiwania wzorca (32bytes) do STRING (206908949bytes) AS-jednej linii ... Skip-Performance (większy-the-lepiej): 3.041% 6801754 przeskakuje / iteracji Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade wydajność: 3483KB / zegar

Przeprowadzenie wyszukiwania wzorca (32bytes) do STRING (206908949bytes) AS-jednego wiersza ... Pomiń wydajność (większa-the-lepsze): 1554%, 13307181 przeskakuje / iteracji Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg Osiągi: 2434KB / zegar

Wykonywanie wyszukiwania wzorca (32 bajty) w łańcuch (206908949 bajtów) jako jeden wiersz ... Pomiń wydajność (większy tym lepszy): 129%, 160239051 pomija / iteracje Dwukierunkowe_hits / Dwukierunkowe_ zegary: 0/816 Dwa -Way wydajność: 247KB / zegar

Sanmayce,
Pozdrawiam


3

Algorytm dwukierunkowy, o którym wspominasz w swoim pytaniu (który, nawiasem mówiąc, jest niesamowity!) Został niedawno ulepszony, aby wydajnie działał na wielobajtowych słowach naraz: Optymalne dopasowywanie upakowanych ciągów .

Nie przeczytałem całego artykułu, ale wygląda na to, że polegają na kilku nowych, specjalnych instrukcjach procesora (zawartych np. W SSE 4.2), które są O (1) dla ich złożoności czasowej, chociaż jeśli nie są dostępne, mogą symuluj je w czasie O (log log w) dla słów w-bitowych, które nie brzmią zbyt źle.


3

Możesz zaimplementować, powiedzmy, 4 różne algorytmy. Co M minut (do ustalenia empirycznie) uruchom wszystkie 4 na bieżących rzeczywistych danych. Gromadzenie statystyk dotyczących N przebiegów (również do ustalenia). Następnie wykorzystaj tylko zwycięzcę przez następne M minut.

Loguj statystyki wygranych, aby móc zastąpić algorytmy, które nigdy nie wygrywają, nowymi. Skoncentruj wysiłki optymalizacyjne na najlepszej rutynie. Zwróć szczególną uwagę na statystyki po wszelkich zmianach w sprzęcie, bazie danych lub źródle danych. Jeśli to możliwe, uwzględnij te informacje w dzienniku statystyk, dzięki czemu nie będziesz musiał ich odczytywać na podstawie daty / sygnatury czasowej dziennika.



2

Możesz również chcieć mieć różne testy porównawcze z kilkoma typami ciągów, ponieważ może to mieć duży wpływ na wydajność. Algosy będą wykazywać różnicę w oparciu o wyszukiwanie w języku naturalnym (i nawet tutaj nadal mogą istnieć drobnoziarniste rozróżnienia ze względu na różne morfologie), ciągi DNA lub przypadkowe ciągi itp.

Rozmiar alfabetu będzie odgrywał rolę w wielu algach, podobnie jak rozmiar igły. Na przykład Horspool radzi sobie dobrze z tekstem w języku angielskim, ale źle z DNA z powodu różnej wielkości alfabetu, co utrudnia życie dla zasady złych znaków. Wprowadzenie przyrostka good-suix znacznie to ułatwia.


0

Nie wiem, czy to absolutnie najlepsze, ale mam dobre doświadczenia z Boyer-Moore .


Czy znasz sposób na połączenie złego stołu zmianowego Boyera-Moore'a z Two-Way? Glibc robi to w wariancie dla długich igieł (> 32 bajty), ale sprawdza tylko ostatni bajt. Problem polega na tym, że Two-Way musi przeszukiwać prawą część igły od lewej do prawej, podczas gdy złe przesunięcie Boyera-Moore'a jest najbardziej wydajne podczas wyszukiwania od prawej do lewej. Próbowałem go używać z lewą do prawej w Two-Way (awansuj przez tabelę zmianową lub normalną dwustronną prawą połówkę, w zależności od tego, która z tych opcji jest dłuższa), ale w większości przypadków uzyskałem 5-10% spowolnienie w porównaniu z normalnym Dwukierunkowym i nie mogłem znaleźć żadnych przypadków, w których poprawiłaby wydajność.
R .. GitHub PRZESTAŃ POMÓC W LODZIE

0

To nie odpowiada bezpośrednio na pytanie, ale jeśli tekst jest bardzo duży, co powiesz na podzielenie go na zachodzące na siebie sekcje (nakładanie się na długość wzoru), a następnie przeszukiwanie sekcji za pomocą wątków. Jeśli chodzi o najszybszy algorytm, myślę, że Boyer-Moore-Horspool jest jednym z najszybszych, jeśli nie najszybszym spośród wariantów Boyer-Moore. W tym temacie zamieściłem kilka wariantów Boyer-Moore (nie znam ich nazwy) Algorytm szybszy niż wyszukiwanie BMH (Boyer – Moore – Horspool) .


0

Najszybszy jest obecnie EPSM autorstwa S. Faro i OM Kulekciego. Zobacz http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm

„Dokładne dopasowanie spakowanych ciągów” zoptymalizowane pod kątem SIMD SSE4.2 (x86_64 i aarch64). Działa stabilnie i najlepiej we wszystkich rozmiarach.

Witryna, z którą się połączyłem, porównuje 199 algorytmów szybkiego wyszukiwania ciągów znaków, przy czym te zwykłe (BM, KMP, BMH) działają dość wolno. EPSM przewyższa wszystkie inne wymienione tutaj na tych platformach. To także najnowsze.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.