Próbuję ocenić algorytmy i implementacje różnych podłańcuchów wyszukiwania (ala strstr) i szukając dobrze spreparowanych strun igłowych i stogu siana, które złapią najgorszy przypadek i ewentualne błędy na skrzynkę. Przypuszczam, że sam mógłbym je rozwiązać, ale sądzę, że ktoś musi mieć porządną kolekcję testowych siedzeń gdzieś ...Co to są dobre przypadki testowania dla algorytmów wyszukiwania podciągowego i testów obciążeniowych?
Nie odpowiada bezpośrednio na twoje pytanie, ale możesz znaleźć algorytmy w książce - Algorytmy na struny, drzewa i sekwencje: informatyka i biologia obliczeniowa - interesujące (ma wiele nowatorskich algorytmów wyszukiwania pod-ciągów). Dodatkowo jest również dobrym źródłem specjalnych i złożonych przypadków.
Dzięki, ale to naprawdę pomysły testowe/porównawcze, których szukam. Mam przyzwoite odniesienie do algorytmów tutaj: http://www-igm.univ-mlv.fr/~lecroq/string/index.html Dwudrogowy i SMOA wydaje się być jedynym "szybkim" (w dużym-O) algorytmów odpowiednich dla kodu, który nie może mieć przypadków awarii, ponieważ pozostałe są nieruchome w przestrzeni i mogą zawieść w warunkach pamięci obciążonej. Jednak naiwna implementacja jest również bardzo interesująca i wydaje się, że może być optymalna do bardzo dużych rozmiarów igieł. Jest mniej więcej dwa razy szybszy od metody Two Way na krótkie i umiarkowane łańcuchy glibc, które próbowałem. –
Dzięki za link! to naprawdę fajna kompilacja dokładnych algorytmów dopasowywania ciągów. – tathagata
Niektóre myśli i częściową odpowiedź na sobie:
Najgorszy przypadek algorytmu brute force:
a^(n+1) b w (a^n b)^m
np aaab w aabaabaabaabaabaabaab
najgorszy przypadek SMOA:
coś podobnego yxyxyxxyxyxyxx w (yxyxyxxyxyxyxy)^n. Potrzebuje dalszego udoskonalenia. Próbuję upewnić się, że każde przesunięcie jest tylko o połowę mniejsze od częściowego dopasowania, a to, że obliczanie maksymalnego przyrostka wymaga maksymalnej ilości wstecznego śledzenia. Jestem prawie pewien, że jestem na dobrej drodze, ponieważ tego typu przypadek jest jedynym sposobem, jaki dotychczas odkryłem, aby moja implementacja SMOA (która jest asymptotycznie 6n+5) działała wolniej niż dwukierunkowa metoda glibc (która jest asymptotycznie 2n-m, ale ma średnio bolesny preprocessing narzutowy).
Najgorszy przypadek na wszystko tabor hash na podstawie:
Cokolwiek sekwencja bajtów powoduje kolizje mieszania z mieszania igły. W przypadku każdego stosunkowo szybkiego skrótu i danej igły, powinno być łatwe skonstruowanie stogu siana, którego mieszanka koliduje z hashem igły w każdym punkcie. Jednakże wydaje się trudne jednoczesne tworzenie długich częściowych dopasowań, które są jedynym sposobem na zachowanie najgorszego przypadku. Oczywiście w najgorszym przypadku igła musi mieć pewną okresowość i sposób naśladowania hasza poprzez dostosowanie tylko ostatnich znaków.
Najgorszy przypadek dwukierunkowy:
Wydaje się być bardzo krótka igła z nietrywialnej rozkładu MS - coś bac - gdzie stogu zawiera powtórzone fałszywych alarmów w prawym pół składnik igły - coś podobnego dacdacdacdacdacdacdac . Jedynym sposobem, w jaki ten algorytm może być powolny (poza tym, że autorzy glibc źle go wykorzystują ...) jest to, że zewnętrzna pętla wykonuje iteracje wiele razy i wielokrotnie ponoszą ten narzut (i sprawia, że narzut na instalację jest znaczący).
Inne algorytmy:
Jestem naprawdę interesuje tylko algorytmów, które są O(1) w przestrzeni i mają niski narzut przebiegu wyprzedzającego, więc nie spojrzał na swoich najgorszych przypadkach tak dużo. Przynajmniej Boyer-Moore (bez modyfikacji, aby uczynić go O(n)) ma nietrywialny najgorszy przypadek, w którym staje się O(nm).
procedurę, która może dać ciekawe statystyki, choć nie mam czasu, aby przetestować teraz:
Losuj na długości łańcucha, następnie losowo na zawartość ciąg tej długości, następnie losowo ponad Offset/długość podłańcuch (prawdopodobnie coś nie w łańcuchu), następnie losowo przeczesuje nad podłańcuchem (prawdopodobnie wcale), powtórzenie.
Można wygenerować ciągi pojemnik (. Resp zawierał wartości testowe) rekurencyjnie przez:
Wychodząc z pustym ciągiem, generować wszystkie ciągi podane przez powiększania ciąg obecnie w zbiorze dodając znak ze związku alfabet po lewej lub po prawej (oba).
Alfabet do generowania ciągów kontenerów jest wybierany przez Ciebie.
Testujesz 2 alfabetów dla zawartych ciągów. Jeden to ten, który tworzy struny kontenerowe, drugi to jego dopełnienie.
Jaki jest twój końcowy cel tutaj? Aby dowiedzieć się więcej o algorytmach? A może masz aplikację z niezwykłymi igłami/stogami siana? – Cascabel
W krótkim czasie, aby poznać algorytmy. W dłuższej perspektywie mam implementację biblioteki C zorientowaną na bardzo małe rozmiary z ponadprzeciętną wydajnością, która używa naiwnego podejścia do strstr, i chciałbym rozważyć zastąpienie go jednym z O (n) czasu/O (1) algorytmy przestrzenne. SMOA wygląda obiecująco, ale chcę sprawdzić, czy stała 6 w górnej granicy porównań 6n + 5 jest problematyczna w praktyce (moje wstępne testy pokazują, że jest ona znacznie niższa na zdalnie rozsądnych danych i porównywalna pod względem wydajności do glibc bez wszystkich specjalnych obudowa dla krótkich/długich igieł). –