Самый эффективный способ найти последнее появление символа
Рассмотрим эту функцию, которую я написал очень быстро, чтобы найти последнее вхождение данного символа в строку и вернуть его позицию в массиве символов, который физически является строкой:
size_t strlstchar(const char *str, const char ch)
{
char *chptr = strrchr(str, ch);
return chptr - str;
}
Я просто набрал это очень быстро здесь (еще не скомпилировал или еще что-нибудь) только потому, что у меня есть вопросы о нескольких вещах.
Мне кажется, это самое простое решение - найти, какой элемент массива содержит последний экземпляр конкретного символа, но я понятия не имею, как он работает. Я только что сделал это, следуя документации strrchr, так что технически strrchr делает всю работу. Я просто не могу представить, что это лучший способ (с точки зрения производительности) для достижения этого, и надеялся, что кто-нибудь может дать какой-то вклад в то, что будет лучшим способом сделать это.
Strrchr - эффективный способ сделать это? Или strrchr лучше оставить для другого использования?
3 ответа
Подход, который вы использовали, прекрасно подходит - к сожалению, операции с массивами стоят дорого. В большинстве реализаций Strrchr просто проходит по строке, начиная с ее конца, пока не найдет соответствующий символ. Это O(n) время. Затем вы выполняете вычитание, которое O(1), Это не так уж плохо.
Из документов:
Возвращает указатель на последнее вхождение символа в строку C str.
Так что он делает именно то, что вы хотите. Цель его существования заключается в следующем.
Strrchr - эффективный способ сделать это?
Это почти наверняка написано так же хорошо или лучше, чем вы могли бы сделать это сами.
Или strrchr лучше оставить для другого использования?
Нет, написано именно для этой цели.
Это будет быстрее, если вы можете указать длину строки, а затем просто вернуться назад. Когда вы обнаружите первое вхождение персонажа, сразу возвращайтесь.
Если вы не знаете длину, просто используйте strrchr.