Использует strlen () в условии цикла медленнее, чем просто проверка нулевой символ?
Я считал то использование strlen является более дорогим, чем такое тестирование как это:
У нас есть строка x 100 символов в длину.
Я думаю это
for (int i = 0; i < strlen(x); i++)
является более дорогим, чем этот код:
for (int i = 0; x[i] != '\0'; i++)
Действительно ли это верно? Возможно, второй код не будет работать в некоторой ситуации так это лучше для использования первого?
Это будет лучше с ниже?
for (char *tempptr = x; *tempptr != '\0'; tempptr++)
8 ответов
for (int i=0;i<strlen(x);i++)
Этот код вызывает strlen (x) на каждой итерации. Итак, если x имеет длину 100, strlen (x) будет вызываться 100 раз. Это очень дорого. Кроме того, strlen (x) также выполняет итерацию по x каждый раз так же, как и ваш цикл for. Это делает его сложность O (n ^ 2).
for (int i=0;x[i]!='\0';i++)
Этот код не вызывает никаких функций, поэтому будет намного быстрее, чем в предыдущем примере. Поскольку цикл проходит только один раз, его сложность составляет O (n).
Если нет, то оптимизации компиляции нет. Да, потому что strlen будет перебирать каждый байт строки каждый раз, а вторая реализация будет делать это только один раз.
Я могу предположить, что в первом варианте вы найдете strlen на каждой итерации, а во втором варианте вы этого не делаете.
Попробуйте это проверить:
int a = strlen(x);
for (int i = 0; i < a; i++) {...}
Думаю, компилятор может оптимизировать (проверьте комментарий Грегори Пакоша) ваш первый цикл for так, чтобы он выглядел так:
int len = strlen(x);
for (int i = 0; i < len; i++)
Что по-прежнему O (n) .
В любом случае, я думаю, что ваш второй цикл для будет быстрее.
Да, ваш второй вариант может не сработать в 100% процентах случаев, но будет вполне. Это происходит потому, что при использовании strlen() вы должны вызывать метод каждый раз. Лучший способ был бы таким
int strLength = strlen(x);
for (int i = 0; i < strLength; i++)
Надеюсь, это поможет.
Стоит отметить, что вы можете быть открыты для проблем переполнения буфера, если вы также не проверите индекс на размер буфера, содержащего строку. В зависимости от того, что вы делаете с этим кодом, это может быть или не быть практической проблемой, но дополнительные проверки редко вредят, и это хорошая привычка.
Я бы предложил: for (i = 0; i < buf_size && x[i] != '\0'; i++)
Где:
buf_size- заранее определенный размер буфера. Еслиx- массив, то это будетsizeof(x); еслиx- указатель, то размер буфера должен быть доступен.- Я убрал объявление
iиз цикла, потому что оно действительно только для c99. Если вы компилируете только под c99, смело вставляйте его обратно.
Конечно, первый вариант займет больше времени, чем второй. На самом деле они делают не одно и то же - первый вариант вычисляет длину строки каждый раз; второй (эффективно) делает это только один раз.
Первая версия эквивалентна следующей:
for (int i=0; x[i] != 0; i++)
for (int j=0; j<i; j++)
;
Возможно, вы хотели сказать "эффективнее ли вызывать библиотечную strlen(), чем реализовывать свою собственную?". Ответ на этот вопрос, конечно, "это зависит". Ваш компилятор может иметь встроенные версии strlen(), оптимизированные сверх того, что вы ожидаете от исходного текста, вы можете быть на платформе, на которой вызовы функций стоят дорого (редкость в наше время), и т.д.
Единственный общий и правильный ответ - "профилируйте и узнайте".
Первый код проверяет длину x на каждой итерации i, и требуется O (n), чтобы найти последний 0, поэтому требуется O (n ^ 2), второй случай - O (n)