Почему второй код более эффективен, чем первый?

Question

Я запутался между двумя кодами, поэтому второй, который я собираюсь здесь дать, более эффективен, чем первый.

Оба кода просто обращают строку, но первый код медленнее, чемдругой, и я не могу понять, почему.

Первый код:

String reverse1(String s) {
    String answer = "";
    for(int j = s.length() - 1; j >= 0; j--) {
        answer += s.charAt(j); 
    }
    return answer;
}

Второй код:

String reverse2(String s) {
    char answer[] = new char[s.length()]; 
    for(int j = s.length() - 1; j >= 0; j--) {
        answer[s.length() - j - 1] = s.charAt(j);
    }
    return new String(answer);
}

И я не могуЧтобы понять, как второй код более эффективен, чем первый, я бы очень хотел это понять.

Answer 1

Почему второй код более эффективен, чем первый?

String является неизменным, answer += s.charAt(j); вы создаете новый экземпляр String в каждом цикле, что делает вашкод медленный

---

Вместо String предлагается использовать StringBuilder в контексте одного потока как для производительности, так и для читабельности (может быть немного медленнее, чем массив char фиксированного размера, но имеет лучшую читаемость):

String reverse1(String s) {
  StringBuilder answer = new StringBuilder("");
  for (int j = s.length() - 1; j >= 0; j--) 
       answer.append(s.charAt(j)); 
 return answer.toString();
}

Answer 2

JVM рассматривает строки как неизменные.Следовательно, каждый раз, когда вы добавляете к существующей строке, вы фактически создаете новую строку!Это означает, что новый строковый объект должен быть создан в куче для каждой итерации цикла.Создание объекта и поддержание его жизненного цикла сопряжено с накладными расходами.Добавьте к этому сборку мусора из отброшенных строк (строка, созданная в предыдущей итерации, не будет иметь ссылки на нее в следующей, и, следовательно, она будет собрана JVM).

Следует учитыватьиспользуя StringBuilder.Я провел несколько тестов, и время, затрачиваемое кодом StringBuilder, не намного меньше, чем у массива фиксированной длины.

Существуют некоторые нюансы того, как JVM обрабатывает строки.Есть такие вещи, как интернирование строк, которые JVM делает так, что ей не нужно создавать новый объект для нескольких строк с одинаковым содержимым.Возможно, вы захотите разобраться в этом.

Answer 3

В этом коде вы создаете новый объект String в каждой итерации цикла, потому что String является неизменяемым классом

String reverse1(String s) {
    String answer = "";
    for (int j = s.length() - 1; j >= 0; j--)
        answer += s.charAt(j);
    return answer;
}

В этом коде вы уже выделили память для массива char. Ваш код создаст только одинСтрока в последней строке, поэтому она более эффективна

String reverse2(String s) {
    char answer[] = new char[s.length()];
    for (int j = s.length() - 1; j >= 0; j--)
        answer[s.length() - j - 1] = s.charAt(j);
    return new String(answer);
}

Answer 4

String объект является неизменным, и каждый раз, когда вы выполняете операцию добавления, вы создаете другой объект, выделяя пространство и т. Д., Поэтому он совершенно неэффективен, когда вам нужно объединить много строк.

Ваш метод массива char хорошо соответствует вашим конкретным потребностям, но если вам нужна более общая поддержка конкатенации строк, вы можете рассмотреть StringBuilder

Answer 5

Возможно, на ваш вопрос сложно ответить точно, отчасти потому, что ответ будет зависеть от фактической реализации первой версии.Это, в свою очередь, будет зависеть от того, какую версию Java вы используете, и что решил сделать компилятор.

Если предположить, что компилятор сохраняет первую версию дословно, как вы ее написали, то да, первую версиюможет быть более неэффективным, потому что это потребовало бы выделения новой строки для каждого шага в процессе обращения.Вторая версия, напротив, просто поддерживает один массив символов.

Однако, если компилятор достаточно умен, чтобы использовать StringBuilder, тогда ответ меняется.Рассмотрим следующую первую версию:

String reverse1(String s) {
    StringBuilder answer = new StringBuilder();
    for (int j = s.length() - 1; j >= 0; j--) 
        answer.append(s.charAt(j));

    return answer;
}

Под капотом StringBuilder реализован с использованием массива символов.Таким образом, вызов StringBuilder#append чем-то похож на вторую версию, то есть он просто добавляет новые символы в конец буфера.

Итак, если ваша первая версия выполняется с использованием литерала String, то это более неэффективночем вторая версия, но с использованием StringBuilder это может быть наравне со второй версией.

Answer 6

Первый код объявляет

String answer;

Строки являются неизменяемыми.Поэтому каждая операция добавления перераспределяет всю строку, копирует ее, а затем копирует в новый символ.

Второй код объявляет

char answer[];

Массивы являются изменяемыми, поэтому каждая итерация копирует только однуперсонаж.Конечная строка создается один раз, а не один раз за итерацию цикла.

Answer 7

Строка неизменна.Всякий раз, когда вы делаете answer += s.charAt(j);, он создает новый объект.Попробуйте напечатать журналы GC, используя -XX:+PrintGCDetails, и посмотрите, не вызвана ли задержка незначительным сбором мусора.