Пространственная сложность добавления Java Strings char by char - PullRequest
Новая
       58

Пространственная сложность добавления Java Strings char by char

0 голосов
/ 01 июля 2018

При построении символа Java String char с помощью цикла через «сложение» можно заметить, что временная сложность выполнения этой операции плохая: она квадратичная O(n^2) раз. Тем не менее, мне интересно, если сложность пространства «добавления» строкового char-by-char через цикл также невелика.

Вот минимальный пример программы, которая выполняет построение String с помощью добавления char-by-char с синхронизацией секундомера. Результаты, которые я получил ниже, четко показывают квадратичную кривую: 

/**Create a String of n 'A's char-by-char.
 * @param n Number of 'A's to be appended
 * @return The finished string
 */
public static String appendString(int n) {
    String str = "";
    // Timed run starts here
    long t = System.currentTimeMillis();
    // String concatenation occurs here
    for (int k = 0; k < n; k++)
        str += "A";
    t = System.currentTimeMillis() - t;
    // Timed run ends
    System.out.printf("%d\t%d\n", n, t);
    return str;
}

Хотя я могу определить временную сложность программы, мне интересно, какова пространственная сложность построения строкового типа char-by-char?

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

Примечание: Это не дубликат Сложность конкатенации строк в C ++ и Java , поскольку она не учитывает сложность пространства . Я специально прошу подробный анализ сложности пространства анализ.

Ответы [ 2 ]

0 голосов
/ 01 июля 2018

Ваш код довольно неэффективен, , потому что существует неявное StringBuilder, создаваемое для добавления одного символа в ваш цикл. Это, 

for (int k = 0; k < n; k++)
    str += "A";

эквивалентно чему-то вроде 

for (int k = 0; k < n; k++)
    str = new StringBuilder(str).append("A").toString();

Вы могли бы значительно улучшить производительность пространства (и времени), используя вместо этого один StringBuilder (и вы можете явно изменить его размер). Как, 

StringBuilder sb = new StringBuilder(n);
for (int k = 0; k < n; k++)
    sb.append("A");
String str = sb.toString();

Или , в Java 8+ вы можете использовать генератор и ограничить его до n раз и собрать его. Как, 

return Stream.generate(() -> "A").limit(n).collect(Collectors.joining());
0 голосов
/ 01 июля 2018

Используется квадратичное пространство. Или, скорее, выделено квадратичное количество пространства, потому что каждая итерация цикла (по крайней мере в коде, с которым JIT не делает что-то умное) выделяет новый массив символов: 

new char[1]
new char[2]
new char[3]
// Etc.

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

...