Witam.
Natrafiłem ostatnio na problem wyszukiwania pojedynczego znaku w stlowym stringu.
Metoda find z <string> nie zapewnia odpowiedniej szybkości. Poza tym służy ona do wyszukiwania całych sekwencji.
Proste wyszukiwanie liniowe także nie spełnia oczekiwań:
for(int i = 0; i < str.length(); ++i) {
if(str[i] == szukanyZnak) return i;
}
Tak więc, chciałbym wiedzieć, czy istnieją efektywniejsze sposoby na rozwiązanie tego prostego problemu?
Dodaję, że chodzi o bardzo długie ciągi znaków.
W std::string jest metoda do szukania indeksu pojedynczego znaku.
Nie wiem o jak dużą wydajność ci chodzi, skoro takie rozwiązanie ci nie odpowiada.
Jeżeli ten ciąg to jakieś losowe wartości to ciężko coś innego wymyślić. W niektórych sytuacjach można wykorzystać struktury danych czy optymalizacje, ale tutaj niczego nie widzę.
Możesz ew. wskaźnik do tablicy charów uzyskać, żeby nie wywoływać za każdym razem operatora indeksowania (chociaż też kompilator może zoptymalizować to na tyle, że będzie niewielka różnica). Ile mają te twoje stringi, po kilkaset mb?
Tak, jest metoda find_first_of, jednak ta także zbyt wydajna nie jest.
To nie tylko moje zdanie, polecam arta: http://www.codeproject.com/KB/stl/find_first_of.aspx
Ile mają te twoje stringi, po kilkaset mb?
Nie, maksymalnie kilkadziesiąt.
Sprawdze z tą tablicą charów, i wtedy może fukncja strchr() z C.
Ale na http://www.sgi.com/tech/stl/basic_string.html jest napisane: size_type find_first_of(charT c, size_type pos = 0) const basic_string Searches within *this, beginning at pos, for the first character that is equal to c. Używałeś tej funkcji?
W artykule dyskutują o wydajności szukania stringów w stringu. Niby ta metoda z STLa ma mieć żłożoność O((m - n) * n) gdzie m to długość stringa w którym szukamy, a n to długość szukanego stringa (oczywiście zakładając, że m > n). Tutaj n == 1, więc problemów ze złożonością nie powinno być.
Używałem i tak naprawdę wyniki były porównywalnie ze zwykłym find.
Z tego co widzę, ciężko będzie wymyślić coś lepszego od standardowych sposobów, więc chyba pozostaje mi się ich trzymać.
Być może twój program wymaga jakichś bardziej skomplikowanych struktur danych niż zwykły std::string. Musiałbyś się podzielić wiedzą nt tego co twój program ma robić. Może ktoś ma lepszy pomysł niż naiwne szukanie znaków w kółko.
Jest to najbardziej elementarny przypadek, czyli wyszukiwanie znaku w długim, losowym ciągu znaków, więc bardziej rozbudowane struktury nie wchodzą w grę. Generalnie jest to część większego programu i jednocześnie jego słaby (spowalniający) punkt.
W każdym razie dzięki za wszystkie odpowiedzi.
Jeśli chciałbyś szukać znaku w zwykłej tablicy charów, to wystarczy lekko przerobić funkcję strlen(). Funkcja strlen szuka pierwszego zera, więc jeśli chcesz wyszukać znak c, to każdy znak z tablicy najpierw musisz zxorować z wartością znaku c (wtedy znaki o wartości c zamienią się na '\0' a reszta na coś innego) - ew funkcja strlen może być na tyle elastyczna, że używa wartości szukanego znaku wprost (w tym szczególnym przypadku to zero oczywiście). Na stronie http://agner.org/optimize/ jest sporo zoptymalizowanych funkcji, nawet w asemblerze.
Np kod w C++:
// Example 13.25. Return nonzero if byte b contained in dword w
inline int dword_has_byte(int w, unsigned char b) {
w ^= b * 0x01010101;
return ((w - 0x01010101) & ~w & 0x80808080);}
Oczywiście mnożenie to można zrobić wcześniej, jednorazowo na każde wyszukiwanie znaku.