najbardziej wydajnym sposobem znalezienia ostatnie wystąpienie char

Question

Rozważmy tę funkcję pisałem bardzo szybko znaleźć ostatnie wystąpienie danego char w ciąg i powrócić to pozycja w tablicy znaków, że fizycznie jest ciąg:

size_t strlstchar(const char *str, const char ch) 
{ 
    char *chptr = strrchr(str, ch); 
    return chptr - str; 
} 

Po prostu napisałem to naprawdę szybko (nie skompilowałem ani nie dodałem) tylko dlatego, że mam pytania dotyczące kilku rzeczy.

Dla mnie wydaje się to najprostszym rozwiązaniem, aby dowiedzieć się, który element tablicy zawiera ostatnie wystąpienie określonego znaku, ale nie mam pojęcia, jak to działa. Zrobiłem to po dokumentacji strrchr, więc technicznie strrchr wykonuje całą pracę. Po prostu nie mogę sobie wyobrazić, że jest to najlepszy sposób (jeśli chodzi o wydajność), aby to osiągnąć, i miałam nadzieję, że ktoś mógłby dać jakiś wkład w to, co byłoby najlepszym sposobem na zrobienie tego.

Czy strrchr to skuteczny sposób na zrobienie tego? A może strrchr najlepiej zostawić do innego użytku?

Answer 1

Zastosowane podejście jest całkowicie w porządku - niestety operacje tablicowe są drogie. Strrchr w większości implementacji po prostu przechodzi przez ciąg zaczynając od końca, aż znajdzie pasujący znak. To jest czas O(n). Następnie wykonuje się odjęcie, które jest O(1). To nie jest takie złe.

Answer 2

Od docs:

zwraca wskaźnik do ostatniego wystąpienia znaku w str C strun.

Więc robi dokładnie to, co chcesz. Celem jego istnienia jest to.

Czy strrchr to skuteczny sposób na zrobienie tego?

Jest prawie na pewno napisana co najmniej tak dobrze lub lepiej, niż można to zrobić samodzielnie.

Lub czy strrchr najlepiej pozostawić do innego użytku?

Nie. Napisano dokładnie w tym celu.

Answer 3

Będzie szybciej, jeśli będziesz mógł podać długość struny, a następnie po prostu pętlę do tyłu. Kiedy znajdziesz pierwsze wystąpienie postaci, od razu powróć.

Jeśli nie znasz długości, użyj strrchr.