Есть ли существенное преимущество в производительности при использовании StringBuilder при построении нескольких строк? - PullRequest
Новая
       6

Есть ли существенное преимущество в производительности при использовании StringBuilder при построении нескольких строк?

3 голосов
/ 18 января 2020

Допустим, я создаю набор строк, где каждая строка является префиксом следующей. Например, представьте, что я пишу функцию: 

public Set<String> example(List<String> strings) {
    Set<String> result = new HashSet<>();
    String incremental = "";
    for (String s : strings) {
        incremental = incremental + ":" + s;
        result.add(incremental);
    }
    return result;
}

Стоит ли когда-нибудь переписывать ее для использования StringBuilder вместо конкатенации? Очевидно, что это позволило бы избежать создания нового StringBuilder в каждой итерации l oop, но я не уверен, будет ли это значительным преимуществом для больших списков или будут ли издержки, которых вы обычно хотите избежать при использовании StringBuilders в циклах в основном только ненужные строковые конструкции.

Ответы [ 2 ]

1 голос
/ 18 января 2020

Как правило, вы всегда хотите go для StringBuilder в al oop, поскольку алгоритмы O (n) превращаются в O (n ^ 2). Впрочем, это уже O (n ^ 2). Даже требуемое использование памяти - O (n ^ 2). Похоже, что это чрезвычайно не имеет значения, но, возможно, разница в производительности может быть в два раза. Кроме того, как вы можете видеть из комментариев, читатели ожидают StringBuilder - не удивляйте их без необходимости.

В целом, хотя некоторые могут сказать, что мера, O (n ^ 2) может взорваться в ситуациях, которые не происходит в тестировании. В любом случае, кто хочет микробенчмаркировать весь свой код? Конечно, избегайте неэффективности больших значений O

В некоторых реализациях String.substring будет разделять поддержку char[] между оригиналом и подстрокой. Однако я не верю, что в настоящее время это обычно делается. Это не мешает вам писать свой собственный маленький String класс.

0 голосов
/ 18 января 2020

Этот ответ верен только для Java 8; как указывает @ user85421, + в строках больше не компилируется в StringBuilder операции в Java 9 и более поздних версиях.

Теоретически, по крайней мере, есть еще причина использовать StringBuilder в вашем примере.

Давайте рассмотрим, как работает конкатенация строк: присвоение incremental = incremental + ":" + s; фактически создает новый StringBuilder, добавляет к нему incremental путем копирования, затем добавляет ":" к нему путем копирования, затем добавляет s к нему путем копирования, затем вызывает toString() для получения результата путем копирования и присваивает ссылку на новую строку переменной incremental. Общее количество символов, скопированных из одного места в другое, составляет (N + 1 + s.length()) * 2, где N - исходная длина incremental, поскольку каждый символ копируется в буфер StringBuilder один раз, а затем снова возвращается обратно.

Напротив, если вы используете StringBuilder явно - один и тот же StringBuilder на всех итерациях - тогда внутри l oop вы бы написали incremental.append(":").append(s);, а затем явно вызвали toString() для построения строка для добавления в набор. Общее количество копируемых здесь символов будет (1 + s.length()) * 2 + N, поскольку ":" и s должны копироваться в StringBuilder и из него, а N символы из предыдущего состояния должны копироваться только out из StringBuilder в методе toString(); их также не нужно копировать, потому что они уже были там.

Таким образом, используя StringBuilder вместо конкатенации, вы копируете N меньше символов в буфер в каждой итерации, и такое же количество символов вне буфера. Значение N возрастает с первоначально 0 до суммы длин всех строк (плюс количество двоеточий), поэтому общая экономия составляет квадратичное значение c в сумме длин строк. Это означает, что экономия может быть весьма значительной; Я оставлю это кому-то еще, чтобы сделать эмпирические измерения, чтобы увидеть, насколько это важно.

...